@Dmitriy Kiriyenko

Сумма двух - разбор полётов

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

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

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

Вторым в задаче отметился Иван Трусов, и отметился превосходно. Его решение во-первых, на чистом 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 - довольно лаконичный язык программирования. Элегантные однострочники от Ивана Трусова и компактны и читаемы.

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