Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.

Главная особенность этих многочленов состоит в том, что любую булеву функцию можно представить полиномом Жегалкина, причем единственным образом.

Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.

Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.

Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».

В моей первой статье на Хабре я хотел бы поделиться некоторыми соображениями и замечаниями по работе с Hibernate, касающихся сессий и транзакций. Я остановился на некоторых нюансах, которые возникают при начале освоения этой темы. Признаюсь, сам пока Junior-программист, с Hibernate работал не постоянно, поэтому, как всегда, возможны ошибки, коль заметите оные, буду благодарен за поправки.

Библиотека Hibernate является самой популярной ORM-билиотекой и реализацией Java Persistence API. Часто используется как ORM-провайдер в обычных Java-приложениях, контейнерах сервлетов, в частности, в сервере приложений JBoss (и его потомке WildFly).

Начнём, пожалуй.

Не так давно на Хабре была статья про codebattle от hexlet.io. Ну и затянуло же нас с друзьями, это как наркотик! Вроде пытаешься на работу отвлечься, а руки прям сами тянутся зайти на сайт, и все мысли — об оптимизации решений.

И вот однажды попалась мне задачка, звучала она так: «The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». А если по-русски, то так: «десятичное число 585 в двоичном виде выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-ый подобный палиндром». Она совсем не сложная и решена была быстро.

function is_palindrome($num) {
   return $num == strrev($num);
}
function solution($num) {
   $count = $i = 0;
   while($count<$num) {
      $i++;
      // Проверяем по порядку все числа, являются ли они палиндром в десятичном и двоичном виде
      if (is_palindrome($i) && is_palindrome(decbin($i))){
         $count++;
      }
   }
   return $i;
}

Но вот незадача. Примерно в то время на сайт напал хабраэффект, и тесты ни в какую не хотели проходить, отваливались по timeout. В местном чате началось обсуждение по оптимизации решения, но никто дельного совета так и не дал. Потом сайт отпустило, все тесты прошли, но желание оптимизировать осталось…

Привет, Хабр!

У команды Хекслета немало опыта проведения технических собеседований. Мы делились опытом и советами в вебинаре «Собеседования: взгляд со стороны работодателя». А сегодня публикуем перевод статьи с советами от компании, которая помогает людям готовиться к собеседованиям.

От себя хочу добавить, что не смотря на полезность этих советов, если описанный здесь человек — это не вы, то не нужно стараться эмулировать его.

Много свободного времени только у студентов. Если вы не студент, то должны появиться очень веские причины для того, чтобы начать изучать новый язык программирования. Особенно это касается Java-программистов, потому что этот язык является лидером в своём сегменте. Тем не менее причины для изучения нового языка есть.

Java еще не умерла — и люди начинают это понимать.

Добро пожаловать в ведение по Java 8. Этот материал шаг за шагом познакомит вас со всеми новыми фичами языка. Вы научитесь использовать методы интерфейсов по умолчанию (default interface methods), лямбда-выражения (lambda expressions), ссылки на методы (method references) и повторяемые аннотации (repeatable annotations). Все это будет сопровождаться короткими и простыми примерами кода. В конце статьи вы познакомитесь с наиболее свежими изменениями в API, касающихся потоков, функциональных интерфейсов, расширений для ассоциативных массивов, а также с изменениями в API работы с датами.

Речь пойдёт о простой структуре данных — системе непересекающихся множеств. Вкратце: даны непересекающиеся множества (например, компоненты связности графа) и по двум элементам x и y можно: 1) узнать, находятся ли x и y в одном множестве; 2) объединить множества, содержащие x и y. Сама структура очень проста в реализации и описывалась много раз в различных местах (например, есть хорошая статья на хабре и ещё кое-где). Но это один из тех удивительных алгоритмов, написать который ничего не стоит, а вот разобраться, почему он работает эффективно совсем нелегко. Я постараюсь изложить относительно простое доказательство точной оценки на время работы этой структуры данных, придуманное Зейделем и Шариром в 2005 (оно отличается от того ужаса, который многие могли видеть в других местах). Конечно, сама структура тоже будет описана, а попутно разберёмся причём здесь обратная функция Аккермана, о которой многие знают только, что она оооочень медленно растёт.

В преддверии Java-конференции Joker 2015, которая начнется уже завтра, я публикую большое интервью с Алексеем Шипилёвым, инженером команды Java Performance Team из Oracle, одним из самых крутых и известных во всем мире специалистов по производительности. Ну и конечно, прекрасным спикером.

С Алексеем мы подробно поговорили:

• про грядущие изменения в классе String;
• про то, кто же на самом деле разрабатывает OpenSource;
• про системных разработчиков и их карьеру;
• про обмен технологиями, «научную» и «продуктовую» разработку;
• про сложность низкоуровневых задач;
• про развитие Java-сообщества и бенчмарк-войны;
• про mutable vs immutable;
• про Unsafe;
• про JMH, бенчмарки и узкую специализацию.

Вот видео нашего разговора. Больше часа длиной, можно слушать в дороге.



Ниже под катом — расшифровка нашей беседы для тех, кто видео не очень.

Прочитав эту статью, я вспомнил, как писал внешнюю сортировку, которая использовала O(1) внешней памяти. Функция получала бинарый файл и максимальный размер памяти, которую она могла выделить под массив:

void ext_sort(const std::string filename, const size_t memory)

Я использовал алгоритм из Effective Performance of External Sorting with No Additional Disk Space:

1. Разделим файл на блоки, которые помещаются в доступную память. Обозначим эти блоки Block_1, Block_2, …, Block_(S-1), Block_S. Установим P = 1.
2. Читаем Block_P в память.
3. Отсортируем данные в памяти и запишем назад в Block_P. Установим P = P + 1, и если P ≤ S, то читаем Block_P в память и повторяем этот шаг. Другими словами, отсортируем каждый блок файла.
4. Разделим каждый блок на меньшие блоки B_1 и B_2. Каждый из таких блоков занимает половину доступной памяти.
5. Читаем блок B_1 блока Block_1 в первую половину доступной памяти. Установим Q = 2.
6. Читаем блок B_1 блока Block_Q во вторую половину доступной памяти.
7. Объеденим массивы в памяти с помощью in-place слияния, запишем вторую половину памяти в блок B_1 блока Block_Q и установим Q = Q + 1, если Q ≤ S, читаем блок B_1 блока Block_Q во вторую половину доступной памяти и повторяем этот шаг.
8. Записываем первую половину доступной памяти в блок B_1 блока Block_1. Так как мы всегда оставляли в памяти меньшую половину элементов и провели слияние со всеми блоками, то в этой части памяти хранятся M минимальных элементы всего файла.
9. Читаем блок B_2 блока Block_S во вторую половину доступной памяти. Установим Q = S −1.
10. Читаем блок B_2 блока Block_Q в первую половину доступной памяти.
11. Объеденим массивы в памяти с помощью in-place слияния, запишем первую половину доступной памяти в блок B_2 блока Block_Q и установим Q = Q −1. Если Q ≥ 1 читаем блок B_2 блока Block_Q в первую половину доступной памяти и повторяем этот шаг.
12. Записываем вторую половину доступной памяти в блок B_2 блока Block_S. Аналогично шагу 8, тут хранятся максимальные элементы всего файла.
13. Начиная от блока B_2 блока Block_1 и до блока B_1 блока Block_S, определим новые блоки в файле и снова пронумеруем их Block_1 to Block_S. Разделим каждый блок на блоки B_1 и B_2. Установим P = 1.
14. Читаем B_1 и B_2 блока Block_P в память. Объеденим массивы в памяти. запишем отсортированный массив назад в Block_P и установим P = P +1. Если P ≤ S, повторяем этот шаг.
15. Если S > 1, возвращаемся к шагу 5. Каждый раз мы выделяем M минимальных и максимальных элементов, записываем их в начало и конец файла соответственно, а потом делаем то же самое с оставшимися элементами, пока не дойдем до середины файла.

Преимущество такого алгоритма, кроме отсутствия буфера на диске, это то, что с диска мы читаем данные относительно большими порциями, что ускоряет алгоритм.

Реализуем алгоритм на C++.

Если вы программист (или чего хуже архитектор), то можете ли вы ответить на такой простой вопрос: как писать НЕ тестируемый код? Призадумались? Если с трудом можете назвать хотя бы 3 способа добиться не тестируемого кода, то статья для вас.

Многие скажут: а зачем мне знать, как писать не тестируемый код, плохому хочешь меня научить? Отвечаю: если знать типичные паттерны не тестируемого кода, то, если они есть, можно легко увидеть их в своем проекте. А, как известно, признание проблемы — уже половина пути к лечению. Также в статье дается ответ, как собственно осуществляется такое лечение. Прошу под кат.

Что это и зачем оно надо: Как известно, главное преимущество Java мира в том в нем существует огромное количество open-source проектов на на все случаи жизни, однако найти нужный на github'e не так просто, так как описание проекта часто мало информативно, зачастую сложно даже понять этот проект для Android'a или нет. В этой статье я автоматически и полуавтоматически собрал Java проекты, убрал старые и проекты только для Android'a, выбрал 350 набравших больше всего звезд, разделил по категориям и перевел описания.

Если вы хотите убедиться что базы данных пишут не только на C, найти проекты для работы с большими данными или нейронными сетями, пишите свой язык программирования для JVM и хотите посмотреть как это уже сделано или же просто хотите узнать какие новые возможности можно найти в Java мире open-source то это статья вам, думаю, может пригодится.


Другие статьи серии: часть 1. JPA и Hibernate в вопросах и ответах

Update: Внимание, актуальная версия со много большим количеством ссылок, находиться теперь в моем github'e проекте useful-java-links, по этой ссылке.

На сегодняшний день, когда информация стала доступна как никогда и получить новые знания проще простого, у нас появилась другая проблема: как фокусироваться и структурировать новые знания, если отсутствуют внешние ограничения вроде экзамена или необходимости подготовки к уроку?
И снова нас спасают разработчики и интернет, где появляется все больше открытых университетов, онлай-курсов, лекций и сервисов организации своего обучения.
Я решила собрать в одном месте ссылки на ресурсы дистанционного обучения и другие полезные сервисы на английском и русском языках, большинство из которых бесплатны. Не было цели охватить все, но если вы считаете, что в список нужно что-то добавить –, пожалуйста, напишите в комментариях.

Один из часто рассматриваемых паттернов — паттерн Builder. В основном рассматриваются варианты реализации «классического» варианта этого паттерна:

MyClass my = MyClass.builder().first(1).second(2.0).third("3").build();

Паттерн прост и понятен как табурет, но чувствуется какая-то недосказанность — то минимальный вариант объявляется антипаттерном, то более сложные случаи игнорируются. Хотелось бы исправить этот момент, рассмотрев предельные случаи и определив минимальную и максимальную границы сложности этого паттерна.

Итак, расссмотрим их:

Предыстория

Уже довольно давно я работаю в проекте, в котором используется система сборки Maven. По началу, когда проект был ещё не таких размеров как сейчас, время его полной компиляции было относительно разумным и не вызывало нареканий. Но со временем код разросся, количество подпроектов резко увеличилось и среднее время полной компиляции выросло до 6 — 10 минут. Что служило постоянным источником упрёков со стороны разработчиков.

Следует так же отметить. что мы не использовали параллельную сборку, т.к. это регулярно вызывало различные проблемы. То артефакты в локальном хранилище побьются, то просто соберёт не в том порядке и в финальный WAR артефакт попадёт старый, неперекомпилированный код. Конечно некоторые разработчики использовали параллельную сборку на свой страх и риск. Но рано или поздно попадали в ситуацию, когда не могли разобраться что происходит. И простая перекомпиляция в один поток сразу помогала.

Так продолжалось довольно долго, пока я не наткнулся на довольно любопытный сайт компании Takari, на котором предлагаются способы по усовершенствованию методов работы с Maven.

Самыми интересными там являются три вещи:

• Concurrent Safe Local Repository
• Takari Smart Builder
• The Takari Lifecycle

Так же на GitHub у них выложен Maven Wrapper (аналог враппера из Gradle).

Забегая вперёд отмечу, что описываемые здесь инструменты не только решают проблему некорректной работы Maven, но и дают существенный прирост скорости сборки.

Знаете ли вы JPA? А Hibernate? А если проверить?




Данная статья будет полезна и для тех кто только собирается изучать JPA и Hibernate (В этом случае рекомендую сразу открывать ответы), и для тех кто уже хорошо знает JPA и Hibernate (В этом случае статья позволит проверить свои знания и освежить особенности технологий). Особенно статья будет полезна тем кто собирается пройти техническое интервью, где возможно будут задавать вопросы по JPA и Hibernate (или сам собирается провести техническое интервью).

В Java в вершине иерархии классов лежит класс java.lang.Object. Лежит и лежит, долгое время я им совсем не интересовался.

На собеседованиях часто спрашивают, какие в нем есть методы, поэтому они как-то сами собой выучились. Пришло время посмотреть на этот класс более внимательно. Первый вопрос, который у меня возник, есть ли вообще в исходниках Java класс java.lang.Object. Он же ведь необычный, он вполне может быть жестко зашит в реализацию, как самый верхний.

Однако, такой класс есть и я приведу тут исходники java/lang/Object.java, опустив javadoc, и попытаюсь пролить свет на некоторые моменты связанные с реализацией jvm:

Конечно, можно быть успешным программистом и без сакрального знания структур данных, однако они совершенно незаменимы в некоторых приложениях. Например, когда нужно вычислить кратчайший путь между двумя точками на карте, или найти имя в телефонной книжке, содержащей, скажем, миллион записей. Не говоря уже о том, что структуры данных постоянно используются в спортивном программировании. Рассмотрим некоторые из них более подробно.

И снова день добрый. Пост в продолжение публикации «Spring + Java EE + Persistence, без XML. Часть 1».

1. Введение

1.1 Подгружаем проект

Если вы хотите с этой части начать, либо не осталось проекта сделанного в предыдущей части, можете скачать его с github.
Схема простая:

• Заходите из консоли в папку с проектами IDEA
• git clone github.com/MaxPovver/ForHabrahabr.git
• cd ForHabrahabr/
• git checkout withauth
• Готово, теперь можете грузить проект в студию так же как описано в первой части.

1.2 Что мы будем делать в этой части?

В этой части мы рассмотрим как хранятся отношения многие-ко-многим на уровне объектов сущностей;
доделаем распределения прав пользователям;
сделаем простейший REST-controller;
сделаем регистрацию новых пользователей (только для админа);
и все это без XML.

Мне часто приходилось сталкиваться с тем, что люди прекрасно понимают, что такое транзакции в базе данных и для чего они нужны, но при этом не всегда умеют ими правильно пользоваться. Безусловно, для достижения 80-го уровня сакрального знания нужно иметь не один год опыта и прочесть множество толстенных книг по SQL. Поэтому в этой статье я даже не буду пытаться описать всё, что может быть связано с транзакциями в MS SQL. Я хочу затронуть один простой, но очень важный вопрос, который разработчики часто упускают из вида – уровни изоляции транзакций.
Несмотря на то, что тема очень проста, во многих источниках она освящается плохо – информации либо очень мало, либо очень много. Т.е. прочитав 5-6 кратких теоретических определений невозможно их применить на практике. Для уверенного понимания предмета статьи нужно обращаться к специализированной литературе, но там информации на столько много, что далеко не каждый может уделить необходимое время для её усваивания.
Сегодня я хочу поделиться своим простым рецептом, который помог мне раз и на всегда запомнить особенности уровней изоляции транзакций и по сей день помогает без проблем принимать взвешенные решения о выборе необходимого уровня.

Введение

Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

F_n= F_n-1+ F_n-2

и F₁= F₂=1.