Информатика зачастую становится местом действия компромиссов. Когда мы рассуждали о сортировке в третьей главе, мы отмечали компромисс между временем, потраченным на сортировку, и временем, которое впоследствии понадобится, чтобы отыскать нужное. А в разговоре о кешировании в главе 4 мы изучали выбор в пользу сохранения места – кеш для кеша для кеша – ради экономии времени.

Время и пространство – основа всех известных компромиссов в информатике, но последние исследования рандомизированных алгоритмов предлагают нам рассмотреть еще одну переменную – достоверность. Как выразился Майкл Миценмахер из Гарварда, «что мы хотим сделать, так это придумать ответ, который сэкономит вам время и пространство и использует третью переменную – вероятность ошибки». Когда ему предложили привести пример такого компромисса, он ни секунды не сомневался. «Коллега только что предложил игру, в которой нужно выпивать каждый раз, как этот термин появляется на одном из моих слайдов. Вы что-нибудь слышали о фильтрах Блума?»

Чтобы понять суть идеи фильтра Блума, Миценмахер предлагает рассмотреть поисковую систему Google, которая сканирует весь интернет и индексирует каждую страницу. Интернет составляет более триллиона URL-адресов, а средний URL длиной примерно в 77 знаков. Когда поисковый механизм считывает какой-то URL, как он может понять, была ли эта страница ранее обработана или нет? Чтобы просто хранить список всех уже посещенных страниц, требуется огромное пространство, и повторный поиск по этому списку (пусть даже полностью отсортированному) – это кошмар! В данной ситуации можно сказать, что лечение хуже самой болезни. Другими словами, каждый раз проверять, не была ли эта страница уже проиндексирована, будет гораздо более затратным по времени, чем просто индексировать случайную страницу дважды.

Но что, если нам всего-то и нужно знать, что этот URL новый для нас? Вот тут на сцену и выходит фильтр Блума. Названный по имени его создателя, Бёртона Блума, этот фильтр работает по принципу, схожему с тестом Миллера – Рабина: URL подставляется в ряд уравнений, которые, по сути, проверяют «свидетелей» его новизны (вместо того чтобы объявить «n не является простым числом», эти уравнения говорят «я не видел n раньше»). Если вас устроит коэффициент погрешности 1–2 %, хранение полученных результатов в такой вероятностной структуре данных, как фильтр Блума, позволит вам сэкономить очень много времени и пространства. И польза подобных фильтров не ограничивается только поисковыми системами: фильтры Блума интегрированы в большинство современных браузеров для сверки URL-адресов со списком известных вредоносных сайтов, они также являются важной частью пиринговых платежных систем вроде Bitcoin.

По словам Миценмахера, «идея ошибочного компромисса пространства – думаю, основная проблема в том, что люди не связывают это с вычислениями. Они полагают, что компьютер должен просто выдать ответ. Поэтому, когда на лекции, посвященной алгоритмам, вы слышите: "У вас должен получиться один ответ; но этот ответ может быть неправильным", – мне нравится думать, что это заставляет их [студентов] собраться. Думаю, люди просто не осознают, насколько часто они сталкиваются с этим в своей жизни, и не могут принять это».