Возможно, самая кофейная улица Москвы

Участок Маросейки-Покровки от Китай-Города до Бульварного, наверное, самый кофейный в Москве. Я честно не ожидал такого многообразия. Насчитал сегодня три "Шоколадницы" (и четвертая есть дальше за Бульварным) -- абсолютный рекордсмен, Кофе-Хаус, Старбакс, одна-две несетевые кофейни и "Кофемания" на бульваре. Длина улицы -- метров 500-600. Днем там не очень много народу, не офисная часть, и темп не по-московски неторопливый. Народ в Старбаксе сидит, читает книжки, играет в лото. На улице по узким тратуарам или просто по проезжей части кто-то куда-то идет. Белых воротничков нет, скорее джинсы или что-нибудь вычурное. Сама улица негромко ворчит вокруг. В какой-то момент даже кажется, что это не Москва, благо эта часть города почти не испорчена новоделом, во всяком случае с фасадов. Несколько церквей гармонично вписываются в плотностоящий ряд невысоких домов XIX века. Посольство Белоруси. Звон колоколов храма Николы в Кленниках. Метро.

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

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