Алгоритмы против грубой силы
В последнее время есть тенденция решать многие вычислительные задачи грубой силой. Этому способствует развитие Amazon EC2, Google AppEngine, Hadoop и т.д. Часто приходится слышать "зальем эту задачу на хадуповский кластер, и дело в шляпе". Мне такой подход категорически не нравится, предпочитаю лишний раз подумать и сделать эффективнее. Тем приятнее встречать, когда людям удаются за счет хитрого алгоритма на порядки ускорить задачу, обычно решаемую грубой силой:
A Mac Mini running GraphChi can analyze Twitter's social graph from 2010-which contains 40 million users and 1.2 billion connections-in 59 minutes. The previous published result on this problem took 400 minutes using a cluster of about 1,000 computers
В подробностях алгоритма разбираться лень, некоторые детали есть в этой статье, но суть в том, что удалось уложить социальный граф на диск так, чтобы обрабатывать его последовательно. А последовательные блоки с диска читаются с максимальной скоростью. Идея сродни фрактальным индексам TokuDB, Log-Structured Merge Trees и системе физической организации данных в Вертике. Да, конечно, можно использовать SSD или RAM, и тогда нет разницы, последовательное чтение или случайное, но это та же грубая сила: SSD пока что в несколько раз дороже старого доброго винчестера.
P.S. А напоследок, классический вопрос на собеседовании, первая задача из Project Euler: просуммировать числа от 1 до 1000, делящиеся без остатка на 3 или 5. Большинство начинают писать программу, хотя достаточно вспомнить школьную математику.
A Mac Mini running GraphChi can analyze Twitter's social graph from 2010-which contains 40 million users and 1.2 billion connections-in 59 minutes. The previous published result on this problem took 400 minutes using a cluster of about 1,000 computers
В подробностях алгоритма разбираться лень, некоторые детали есть в этой статье, но суть в том, что удалось уложить социальный граф на диск так, чтобы обрабатывать его последовательно. А последовательные блоки с диска читаются с максимальной скоростью. Идея сродни фрактальным индексам TokuDB, Log-Structured Merge Trees и системе физической организации данных в Вертике. Да, конечно, можно использовать SSD или RAM, и тогда нет разницы, последовательное чтение или случайное, но это та же грубая сила: SSD пока что в несколько раз дороже старого доброго винчестера.
P.S. А напоследок, классический вопрос на собеседовании, первая задача из Project Euler: просуммировать числа от 1 до 1000, делящиеся без остатка на 3 или 5. Большинство начинают писать программу, хотя достаточно вспомнить школьную математику.