В конце июня донецкая делегация приняла участие в очередном DOU хакатоне, который проходил в городе Харькове. Наш город был представлен четырьмя программистами.

Александр, Андрей и Ден выдали на-гора CL realtime server -- аналог Apple Game Kit. В те 24 часа, которые были отпущены на проект, ребята успели создать клиентские библиотеки под iOS и под мак. В планах - охватить андроид и другие популярные платформы. Ребята выбрали, в качестве основы проекта, сервер clws

Павел Митин написал минималистичный аутентификационный гем для Ruby On Rails, который применяется до момента запуска проекта в продакшен.

Принимающая сторона сделала все, чтобы у гостей и участников остались только положительные воспоминания. Одно только присутствие в здании восточного ресторана чего стоит! Победили в соревнованиии замечательная пара (муж и жена), которые написали mongo-подобную базу данных на основе файловой системы в пользовательском пространстве [https://github.com/silver-/mongo-fuse]

Несомненно хакатон удался: от марафонского кодирования, до задушевных песен под гитару и спортивных баталий. Если вы еще ни разу не участвывали в хакатоне, обязательно это сделайте!

Кто знает - напоминаю, кто не знает - сообщаю: валидация в ActiveRecord на уникальность не гарантирует уникальности. Как она работает - делает запрос в базу данных на предмет "а есть ли уже запись с таким значением", а при получении отрицательного ответа - ничтоже сумняшеся начинает сохранять. Если в этот момент в базе запись-таки появится - будет нарушение уникальности.

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

Гарантию уникальности даст индекс с проверкой уникальности. Но он не дёргает ошибку валидации.

Я тут немного поговнокодил и сделал drop-in решение, простое, как стол - если сохранение падает по причине нарушенного database constraint, перевалидировать и вернуть false. Таким образом, код пойдёт по ветке контроллера для ошибок валидации, и ошибка нарушенной уникальности отобразится обычными средствами на форме.

Я не проверяю, что вы выставили и валидацию, и индекс. За этим нужно следить самому.

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

Пользуйтесь!

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

Надо сказать, задачка была так себе, но в то же время, подумать было о чём.

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

Традиционно отличился Андрей "новичок в программировании" Кутейко andy128k в нескольких номинациях:

• "Первая ласточка" - его решение на питоне пришло первым.
• "Илита" - решение на Lisp.
• "Мыслитель" - есть решение для поиска N чисел.
• "По перед батька в пекло" - в Питоне есть необычная оптимизация для более эффективного (особенно по памяти) slice.
• "Не используй микроскоп" и "Шаман" - отдельное спасибо за решение на языке J.

Евгений Шелест предложил итеративное решение для поиска двух со сложностью O(log(N)). Дмитрий Кириенко, конечно же, не мог остаться в стороне и предложил решение на Руби (совпадающее c Common Lisp решением Андрея на 100%) и на MySQL - там эта задача наименее надумана - поиск пропущенных идентификаторов. На MySQL, правда, вышло O(N) или даже хуже, но там вообще не до жиру. Антон Ильин, тоже предложил своё решение.

На десяти тысячах впереди всех питон, за ним лисп, два итеративных решения на Руби. MySQL - без комментариев.

Владимр Львович заставил нас взглянуть на проблему с другой стороны - а не получится ли понизить общую сложность до O(log(N)) при помощи бинарного поиска по файлу. К сожалению, его бинарный поиск не терминирован и в итоге выходит на линейную сложность, а как его терминировать я пока понять не могу. Может, что и никак. И за чертой контрольного срока предоставил своё решение, но решение это такое, что ему можно это простить.

Замеры производительности:

Несколько выводов.

1. Безусловным победителем был объявлен Андрей Кутейко, понять бы ещё, что из этого вытекает. Надеемся, он хотя бы получил удовольствие =)
2. Иногда обобщение приводит к улучшению кода. Решения для двух чисел намного более уродливые, чем решения для N.
3. Соблюдая первое правило алгоритмиста - "Can we do better?" и благодаря Владимиру Львовичу мы взглянули на проблему с неожиданной стороны. Я ещё не уверен, что там нет полноценного логарифмического решения.
4. Используйте правильный инструмент. Предназначенный для обработки данных и особенно массивов, J, явил нам довольно красивое и аккуратное решение, которое в языках более общего назначения как минимум занимает больше букв.
5. Очень сложно программировать в SQL.

Приз зрительский симпатий вручается Владимиру Львовичу, решение которого прошло за чертой смерти, но объективно было лучшим. Победа в следующих номинациях:

• "А у вас была логарифмическая линейка?" - его решение единственное имеет честную логарифмическую сложность.
• "Свой среди чужих" - заметьте, решение написано на Руби, причём, с глубоким пониманием того, как работает, к примеру, класс "File".
• "Обойдусь без записной книжки" - решение потребляет константную дополнительную память.
• "Сынки" - посмотрите на производительность.
• "Это же элементарно, Ватсон!" - решение не требует указания количества пропущенных чисел. Недостаток - не находит числа, пропущенные в конце. Но тут или то, или то.
• "Правый хвост длиннее" - интересный и математически обоснованный подход к проблеме бинарного поиска. Почитайте историю комментирования гиста - это довольно интересно.
• "Чем докажешь" - оказаться правым в споре с Андреем Кутейко о программировании.

Ждите новых разминок!

Дима и Леша.

Не знаю, для скольких это будет сюрпризом, но хэш-таблица, в отличие от, например, сбалансированного дерева, имеет вероятностное поведение. Она задумана как контейнер с операциями записать-прочитать-удалить по O(1) каждая, но на практике это не так.

На практике это Θ(1), то есть, в среднем и сбалансированном анализе это константа. В худшем случае это O(N).

Однако же, быстрая сортировка, применяемая в хвост и в гриву в библиотечных функциях (например, в bash-функции sort, в Array#sort в Руби, тысячи их), имеет сходные характеристики - несмотря на то, что он в большинстве случаев O(N*log(N)), в худших случаях он O(n^2), что ставит его на одну доску с пузырьком и делает асимптотически хуже той же сортировки слиянием. Но ведь в большинстве случаев используется именно он! А дело в том, что худшие случаи редки, а в сбалансированном случае он не только имеет хорошую алгоритмическую сложность, но и правильно расходует память и имеет чрезвычайно низкий коэффициент при этой самой "тэте".

Теперь посмотрим на хэш-таблицы. Мы привыкли думать о операции вставки в хэш-таблицу как O(1), но это не так, поскольку на каком-то этапе нужно перевыделить память и в ходе этого выполняется rehash. Именно поэтому в приложениях, в требованиях к которым числится гарантированное время отклика, использование хэш-таблиц как структур хранения данных противопоказанно, или хотя бы требует осторожности, поскольку на очередной вставке всё может тупо подлагнуть и довольно сильно.

Однако же, давайте представим, что у нас не приложение, а вычислительный скрипт. Нам не важно время одной операции. Давайте посмотрим, как часто выполняется rehash. Вот принятие решения, делать или не делать rehash: https://github.com/ruby/ruby/blob/trunk/st.c#L487. _Если среднее число записей в одной корзинке больше магического числа 5_. Новый же размер определяется ближайшими простыми числами к степеням двойки. То есть, при вставке N элементов, будет выполнено O(log(N)) операций rehash. А каждый rehash (например, i-тый по счёту rehash) будет выполнен не на N элементах, а на простом числе, ближайшем к 2^i. В итоге, имеем сумму геометрической прогрессии с шагом 2, заканчивающейся на N/2. То есть, асимптотически, N.

Итого на N операций вставки имеем (N*O(1) + O(N)) вычислительную сложность.

Теперь с чтением из хэша. Тут сложнее и здесь асимптотически действительно всё плохо, потому что именно здесь вступает в силу то самое вероятностное поведение. Если, к примеру, реализовать хэш-функцию, как return 666, будем иметь ярко выраженную O(N) сложность на произвольный доступ. К счастью, так хэш-функцию никто не реализует.

Руби 1.8, 1.9 и 2.0 используют так называемый Murmur hash (https://github.com/ruby/ruby/blob/trunk/st.c#L1252). Этот алгоритм проходит "пыточный тест Боба Дженкинса" и не даёт коллизий на 4-х байтных ключах даже худшем случае. 4-х байтные ключи - это целые числа до двух миллиардов по модулю. В целом же, для любой разумной практической реализации верен тот факт, что коллизий немного. Конечно же, даже очень большое поле возможных хэшей для не очень большого подмножества значений будет давать коллизию с весьма высокой вероятностью. Так называемый парадокс дней рождения. Но одна коллизия - это в среднем пять операций (помните магическое число). А 1000 коллизий в Murmur hash случится и вовсе с вероятностью в миллиард раз меньшей, чем вероятность попадения метеора в ваш офис, если вероятность одной будет составлять аж 95%.

Таким образом, с любой разумной вероятностью стоимость извлечения из хэш-таблицы по ключу - константа. Редкие случаи коллизий во-первых, порождают, конечно, O(N), но Θ(1), а во-вторых невероятно редки.

Подвожу итог.

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

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

Последовавшая за этим дискуссия и всплеск решений были довольно интересны.

Первым обнаружился Артём Цаплин. Его решение - бинарный поиск с двух концов в упорядоченном массиве. Решение хорошее, но сортировку Артём применил свою, причём, это была сортировка вставкой, что тут же вывело его решение на квадратичную сложность.

Вторым в задаче отметился Иван Трусов, и отметился превосходно. Его решение во-первых, на чистом bash, а во-вторых довольно красивое. Он сортирует массив по хитрому критерию - так, чтобы числа, предположительно формирующие сумму, оказались рядом. Он перевёл своё решение на понятный нам руби - прочитайте, не пожалеете. Сложность очевидно равна сложности библиотечной сортировки - для быстрой сортировки это квадрат, но сбалансированная сложность N*log(N).

Два решения Романа Болгова на javascript продолжают триумфальное разбирательство сообщества с задачей. Первое - использование хитрой структуры данных, известной как двоичное дерево поиска. Второе - использование хэш-таблицы для поиска пар чисел. Решение с хэш-таблицей - первое, которое имеет линейную сбалансированную сложность (в худшем случае мешают унизительные подробности реализации хэш-таблиц). Подробнее о хэш-таблицах, почему их применение, на мой взгляд, легитимно в этой задаче, и почему они всё же в худшем случае не дают нам O(N), можно прочитать в кратком обзоре Хеши: в поисках правды. Решения весьма шустрые, в чём я подозреваю собственно, nodejs.

Далее в задаче обнаружился Артём Дударев с решением на python, использующем hash set. Решение, надо сказать, самое шустрое из предложенных. Заслуга в этом очень быстрых питоновских хэшей (которые по скорости заметно обгоняют рубишные, впрочем, настолько же уступая им по использованию памяти.

Алексей Левжинский тоже предложил два абсолютно идентичных решения - с хэшом и с разреженным массивом в качестве структуры данных. Здесь интересно то, что массив действительно единственная структура данных с честным константным произвольным доступом. В Ruby 2.0 хэши до 20 элементов будут внутри представлены массивом. Конечно, в решении Алексея совершенно сумашедший оверхед по памяти, но алгоритмически он прав.

Два решения от Владимира Львовича - сортировка и бинарный поиск второго слагаемого, и укладка в хэш и поиск по хэш-таблице второго слагаемого - завершили парад предложенных решений.

Замеры производительности:

                        100000
================================
ruby tsaplin.rb          2.058
./trusov-coolsort.sh     0.359
ruby trusov_coolsort.rb  0.360
./trusov-hash.rb         0.330
node bolgovr_hash.js     0.322
node bolgovr_tree.js     0.343
python dudarev.py        0.232
ruby jinnsky_hash.rb     0.292
ruby jinnsky_array_rb    0.260
ruby raven29_binary.rb   0.459
ruby raven29_hash.rb     0.344

За неимением времени производительность измерялась так: на том же тестовом файле прогнал по 100 раз с разными искомыми числами и в результат пошли худшие случаи.

Номинации:

• Скор на ответ - Артём Цаплин.
• Самое быстрое решение - Артём Дударев.
• Порадовал - Иван Борисович Трусов - за bash.
• Почему бы и нет? - Роман Болгов - за дерево.
• Молодым везде у нас дорога - Алексей Левжинский. Его решение на руби алгоритмически такое же, как и у всех, но заметно быстрее многих.
• Тиграм не докладывают мяса - Андрей Кутейко. За дискуссию про хэши.
• Давайте сделаем это правильно - Владимир Львович Коварский. За самотестирующийся скрипт. Дима и Андрей прошлый раз все свои решения сопровождали встроенными тестами, но послание воспринял только Владимир Львович.

Несколько выводов:

• Разминки - замечательная штука. Перед публикацией было найдено только два из предложенных решений и сообщество нашло еще три других.
• Уже к середине недели задача была порвана в клочья и мы рассуждали о тонкостях использования структур данных.
• Язык реализиции слабо влияет на проиводительность. Никакие микрооптимизации не сделают сортировку вставкой быстрее поиска по хэш-таблице, а решения одинаковые концептуально, будут очень близки по скорости работы.
• Очень много нового можно узнать, копнув где угодно. Час внутри реализации рубишных хэшей дали ответы на множество незаданных вопросов.
• Bash - довольно лаконичный язык программирования. Элегантные однострочники от Ивана Трусова и компактны и читаемы.

Спасибо всем кто участвовал.