Два пропущенных числа

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

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

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

Традиционно отличился Андрей "новичок в программировании" Кутейко 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".
• "Обойдусь без записной книжки" - решение потребляет константную дополнительную память.
• "Сынки" - посмотрите на производительность.
• "Это же элементарно, Ватсон!" - решение не требует указания количества пропущенных чисел. Недостаток - не находит числа, пропущенные в конце. Но тут или то, или то.
• "Правый хвост длиннее" - интересный и математически обоснованный подход к проблеме бинарного поиска. Почитайте историю комментирования гиста - это довольно интересно.
• "Чем докажешь" - оказаться правым в споре с Андреем Кутейко о программировании.

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

Дима и Леша.