Page 264 - Bkhargava_-_Grokaem_algoritmy

Фильтры Блума и Hyperloglog 263

\-1\2/l\4\s]

~\J//

1S

Пример:

>>> arrl = [1, 2, 3, 4, 5]
>>> reduce(lambda х,у: х+у, arrl)
15

В данном случае все элементы в массиве просто суммируются: 1 + 2 + 3 +
4 + 5 = 15! Я не буду рассматривать свертку более подробно, потому что
в Интернете хватает руководств по этой теме.
MapReduce использует эти две простые концепции для выполнения запро­
сов на нескольких машинах. При использовании большого набора данных
(миллиарды записей) MapReduce выдаст ответ за минуты, тогда как тра­
диционной базе данных на это потребуются многие часы.

Фильтры Блума и Hyperloglog

Представьте себя на месте сайта Reddit. Когда пользователь публикует
ссылку, нужно проверить, публиковалась ли эта ссылка ранее. Истории,
которые еще не публиковались, считаются более ценными.
Или представьте себя на месте поискового бота Google. Обрабатывать веб­
страницу нужно только в том случае, если она еще не обрабатывалась ранее.
Итак, нужно проверить, обрабатывалась ли страница ранее.
Или представьте себя на месте bit.ly - сервиса сокращения URL. Пользо­
ватели не должны перенаправляться на вредоносные сайты. У вас имеется
набор URL-aдpecoв, которые считаются вредоносными. Теперь нужно вы­
яснить, не направляется ли пользователь на URL-aдpec из этого набора.

Во всех этих примерах возникает одна проблема. Имеется очень большой
набор данных.

www.trk.kg