От авторов

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

Comments

Шеф, два счетчика!

Привет, я довольно давно использую opscode chef для настройки и поддержки инфраструктуры и предлагаю использовать его всем. Недавно для одного из своих проектов я собрал инcтрумент для настройки и поддержки (это очень важное слово) инфраструктуры и решил выделить его в отдельный проект - stacker. Я думаю что этот инструмент был бы более чем полезен - каждый проект начинается с ритуала - настройка стейджинга/продакшна. При всей кажущейся простоте настройка сервера и автоматизированного деплоя в зависимости от опыта может занимать от нескольких часов до нескольких дней - это грустно. Особенно это грустно с учетом того, что действия производятся одни и те же (с минимальными вариациями).

Stacker позволяет за минимальное время собрать более-менее идиоматичный стек для rails приложения - nginx + unicorn + PostgreSQL. На данном этапе инструмент уже работает, и им можно пользоваться/тренироваться пользоваться. Как уже замечено выше - очень важная особенность это то, что инструмент предназначен не только для бутстрапа, но и для поддержки инфраструктуры. С помощью изменения атрибутов и добавления новых кукбуков можно очень легко добавлять/убирать пакеты, изменять конфиги и хранить полное описание инфраструктуры в репозитарии - что позволяет с легкостью переносить приложения на новые сервера и клонировать инфраструктуру. Чтобы понять масштабы уже проделанной кем-то работы - ознакомьтесь со списком официально поддерживаемых кукбуков также существует более 9000 неофициальных кукбуков.

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

Предполагаемый роадмэп на ближайшее будущее:

  • Еще больше документации
  • Сделать пример для django/clojure или чего небудь еще не из мира руби

Если есть желание можете пробовать/тестировать/вносить изменения - буду рад любым отзывам. Проект на гитхабе

Comments

Сто свечей

Задача сегодняшней разминки от нашего постоянного читателя Владимира К.


В туннеле стоят одна за другой 100 свечей.
Туннель пробегают в одном направлении один за другим 100 гномов. Каждый гном меняет состояние тех (и только тех) свечей, порядковые номера которых кратны порядковому номеру данного гнома. Свеча может иметь только два состояния: "горит" / "не горит". В начале процесса все свечи не горят.

Какие свечи останутся гореть когда через туннель пробегут все гномы?

Comments

Сумма двух


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

Дано: массив случайных натуральных чисел X в случайном порядке, среди которых могут быть дубликаты. Целое число C.

Вопрос: может ли число C быть сформировано суммой двух элементов массива? Другими словами, существуют ли такие i, j, что X[i] + X[j] == C?

Очевидным способом ответ ищется за O(n^2). Требуется найти более быстрое асимптотически решение. Исходный массив (X) записан в файл построчно, целевая сумма (C) либо передаётся параметром, либо жёстко забита в код, если ваш язык реализации не умеет читать параметры.

В помощь вам специально подготовленный гист, в котором есть файлик на 100 000 чисел и перечислено несколько тестовых чисел с правильными ответами - тут можно проверять решение. Можно сразу скачать. Кстати, квадратичные решения на 100 000 на моём компьютере в Руби работают порядка 40 минут, так что стимул решить правильно вроде бы есть.

Решения оставляйте гистами, комментарий в эту статью или в гист. Просьба к решению прилагать команду для его запуска, типа ruby solution.rb 215500 или sbcl --script kuteiko.lisp 66613. Итоги будем подводить через неделю, в понедельник.

Мы приветствуем все решения, но людей из списка просим предоставить свои решения аккурат в следующий понедельник. До этого, пожалуйста, не портите другим программистам удовольствие. Можете просто отметиться в комментариях к этой статье, что, мол, решение есть. В понедельник мы напомним вам, что нужно решением поделиться. Эти люди: Андрей Кутейко, Сергей Качан, Саша Михальчук, Игорь Афонов, Павел Митин, Владимир Коварский. Всем остальным рекомендуем выкладывать решения сразу, чтобы спровоцировать обсуждение достоинств и недостатков и оживить программистскую мысль нашего коллектива.

Желаем всем удачи и хорошего развлечения!

Всегда ваши,
Дима, Лёша.

Comments

Поиск единомышленников

Очередная разминка с лёгким превышением заявленного срока.

Задача: найти количество инверсий в перестановке.

Дан массив чисел от 1 до n в случайном порядке. Числа не повторяются. Найти число инверсий в этом массиве. Инверсия - это пара чисел, стоящих в убывающем порядке, когда большее предшествует меньшему. Обращаю внимание, что пара чисел, не обязательно стоящих в массиве подряд. То есть, если к упорядоченному массиву дописать в начало число, которое больше всех элементов массива, оно породоит n-1 инверсию.

Формальное определение: в массиве A инверсией считаем пару чисел i,j, где i < j, такие, что A[i] > A[j].

Соответственно, максимальное количество инверсий будет наблюдаться в массиве, отсортированном в обратном порядке, и это число n(n-1)/2.

Вот для затравки интересный графический алгоритм для поиска инверсий:


Мы располагаем исходный массив и сортированный рядом, соединяем одинаковые числа и количество пересечений - это количество инверсий, а сами пересения - это и есть инверсии.

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

Для удобства проверки вот вам одна перестановка с правильным ответом.

Очевидный, или наивный алгоритм, даёт O(n^2). На среднем компьютере - 40 минут для 100000 чисел.. Хорошие решения дают на том же объёме данных не превышают три секунды.

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

Удачи!

Comments

Итоги поиска единомышленников

Последняя разминка о количестве инверсий в массиве торжественно объявляется самой плодотворной.


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

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

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

В итоге сложность решения задачи была сведена к O(N*log(N)) во всех решениях.


raven29-int.rb    0.762s
raven29-real.rb   1.213s
bronislav.rb      0.688s
donal.rb          1.106s

Comments

Сто мудрецов


Что мы все о программировании да о программировании. Давайте в этот раз просто подумаем и поможем ста мудрецам спастить от неминуемой гибели от рук палача.

Итак, все сто мудрецов выстроены в одну колонну (каждый видит тех и только тех, кто стоит перед ним), и на головы им будут надеты шляпы одного из k > 0 цветов, выбранных независимо и случайным образом. Каждый из мудрецов в колонне, начиная с последнего, должен будет либо назвать цвет своей шляпы, либо сказать «пас».

Мудрецы считаются прошедшими тест, если хотя бы один из них назовёт цвет верно и не будет никого, кто назвал цвет неверно.

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

Для случая k = 1 всё достаточно просто: если известно, что шляпы бывают только одного цвета, то именно его надо называть. С вероятностью 100% ответ будет правильным, поэтому мудрецы пройдут тест.

Чем хороша эта задача? А тем, что кажется, что она не имеет разумного решения. Судите сами: первый отвечающий, который видит перед собой 99 шляп, ничего не знает о цвете своей шляпы. Поэтому он, не имея права назвать какой-то цвет (если назовёт, то с вероятностью 1-1/k все проиграют), вынужден сказать «пас». Но у второго совершенно такая же ситуация: он видит перед собой 98 шляп, он заранее знал, что первый скажет «пас», поэтому он тоже вынужден говорить «пас». И так далее. Возникает иллюзия, что выиграть невозможно. И тем интереснее догадаться, как же действовать мудрецам.

UPD: спойлеры в каментах!

Comments

Книги новичкам рельсов

Эта заметка относится к Rails разработчикам, друзьям Rails разработчиков, тем, кто собирается предлагать молодёжи Rails для изучения... Собственно, больше всего относится к тем, кто собирается помогать кому бы то ни было учить Рельсы.

Есть такая книга - замечательная книга - Agile Web Development with Rails. "Гибкая разработка приложений в среде Rails". Я начинал с неё и подозреваю, что очень сильно в этом не одинок. Книга хорошо и глубоко рассказывает не только о рельсах, но и о веб-разработке, гибкой разработке с участием заказчика в процессе и даёт довольно крепкий фундамент с серьёзным пониманием среды Ruby on Rails.

С некоторых пор стало популярным рекомендовать новичкам книгу Майкла Хартла "Ruby on Rails tutorial". И я рекомендовал, и вслед за мной многие другие рекомендовали. К сожалению, эта книга даёт гораздо более грустные результаты. В ней читателя подводят к использованию огромного количества бестий из околорельсовского зоопарка, предлагают писать довольно гадкий код и практически не отвечают ни на один из вопросов "как это работает" или "зачем это надо". Собственно, первое соображение хуже всего. Rvm, Rbenv, RSpec, Spork, Guard, Autotest-Growl, Gravatar, Heroku - всё это очень сильно отвлекает неофита от навыка написания моделей, контроллеров и представлений, и тем более от попыток понять, как и почему всё так устроено.

Поэтому я настоятельно рекомендую не рекомендовать молодым адептам книгу Rails tutorial как не приносящую положительных результатов. На Озоне есть четвёртое издание на русском языке в, как говорят, отличном переводе, обновлённое до Rails 3.1. Это могло бы пригодиться многим и многим начинающим разработчикам.

Comments

Обыкновенная современная трагедия

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

Сделал только что интересное открытие. Если бы я был компьютером, после этого открытия я бы поднял восстание машин.

Не знаю, заметили ли вы, но с некоторого момента NameError и NoMethodError ("неизвестная переменная или метод" или "неизвестный метод") во вью в рельсах стали ОЧЕНЬ сильно замедлять систему. Если посмотреть на загрузку системы в этот момент, мы увидим 100% загрузку процессора, а страничка с ошибкой и запись в лог произойдёт спустя 60-80 секунд. Знакомо? Встречается, начиная с 3.1.rc1 и не было исправлено ни в 3.1-stable, ни в 3.2-stable. На сегодняшний день в 3.2.2 (последная стабильная версия) это всё ещё не исправлено.

Что же происходит?

Rails.application.routes.inspect.size # => 3114195 в нашем приложении.

Строка на три миллиона символов.

Проблема пришла откуда не ждали. Внутри руби есть такой name_err_mesg_to_str, который всегда вызывает inspect обрабатывая NameError и NoMethodError, на том объекте, на котором не нашли метода.

Соответственно, если вы пишете во вью <%= bad_method_name >, у вас вызывается inspect на ActionView::Base. Реализация inspect в классе Object такова, что он рекурсивно вызывает inspect на всех переменных экземпляра. В результате конструируется феерической длины строка, её конструирование съедает 100% процессора и тьму тьмущую памяти (из-за того, что inspect на RouteSet, к примеру, этот метод при возникновении ошибки вызывается 7 раз). На живом сервере это, при конкурентных запросах ещё приводит к свопу. Да и вообще - для того, чтобы полностью занять делом ваш 4-х ядерный процессор достаточно 4-х пользователей, одновременно поймавших NameError во вью.

И совершенно неважно, что в продакшен режиме вы не рисуете красивую и подробную страничку ошибки, а мгновенно отдаёте 500.html через Апач. Ещё до того, как Рельсы осознали, что что-то пошло не так, Руби генерирует вам многомегабайтные строки, которые никто никогда не прочитает.

8 месяцев тысячи Rails приложений при ошибках загружали на 100% на минуту-две процессор, генерируя десятки миллионов никому не нужных ActiveSupport::Multibyte и это ужасно.

В общем, обновляйтесь до >= 3.2.3 срочно. Есть "исправляющий" коммит.

Comments

Харьковский хакатон

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

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

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

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

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

Comments

ActiveRecord и валидация на уникальность

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

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

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

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

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

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

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

Comments

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

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

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

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

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

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

Дима и Леша.

Comments

Хеши: в поисках правды

Не знаю, для скольких это будет сюрпризом, но хэш-таблица, в отличие от, например, сбалансированного дерева, имеет вероятностное поведение. Она задумана как контейнер с операциями записать-прочитать-удалить по 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), а во-вторых невероятно редки.

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

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

Comments

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

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

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

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

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

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

Comments

С моих слов записано верно и мною прочитано. Претензий не имею


  • «Есть два подхода к программированию. Первый — сделать программу настолько простой, чтобы в ней очевидно не было ошибок. А второй — сделать её настолько сложной, чтобы в ней не было очевидных ошибок.» Чарльз Энтони Ричард Хоар. Профессор, занимался реализацией Алгол 60, сейчас исследователь в Microsoft Research.
  • «Objective C был значительно лучше, пока я его не использовал» Дмитрий Кириенко
  • «Если отладка — процесс удаления ошибок, то программирование должно быть процессом их внесения» Эдсгер Вайб Дейкстра
  • «Сделай так просто, как возможно, но не проще этого.» Альберт Энштейн
Comments