Алгоритмы против грубой силы

[kaipa]

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

Comments

[antilamer.livejournal.com]

Насчёт 1..1000 - на собеседовании я бы вывел формулу, но на практике написал бы программу :) слишком велик риск ошибиться на единичку.

[ushastyi.livejournal.com]

Я когда писал это, тоже так подумал, но формулу можно даже посчитать в уме, в отличие от программы :)