Page 267 - Bkhargava_-_Grokaem_algoritmy

266 Глава 11. Что дальше?

проверяете, присутствует ли условие в журнале, и если нет, добавляете его.
Даже для одного дня этот журнал получится гигантским.

HyperLogLog аппроксимирует количество уникальных элементов в множе­
стве. Как и фильтры Блума, он не дает точного ответа, но выдает достаточно
близкий результат с использованием малой части памяти, которую обычно
занимает такая задача.
Если вы используете большие объемы данных и вас устраивают прибли­
женные ответы - воспользуйтесь вероятностными алгоритмами!

Алгоритмы SHA

Помните процедуру хеширования из главы 5? На всякий случай освежу
вашу память : имеется ключ, вы хотите поместить связанное с ним значение
в массив.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
о 1 l .о 4 5 6 1 11 З 10 11 1l 1.0 1" 15 16 Н 111 1З 1.0 ll ll. l.O 1.4 1.5 1.6 1.1 1.1\ 1.З 30 .01 .01.

Элемент, в котором размещается значение, определяется хеш-функцией.

клю­
клю- ЧМ НА
ч~к~~ БУК&У клю- клю-
Б , ," аБ• ЧМ НА ЧМ НА
•А• КЛЮЧИ НА 6УК&У &УК&У
аЮ• ,аЯ•1
1 j ./'БУКl\У а&• ~
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
О 1 l 3 4 5 6 1 11 З 10 11 11. 1.0 14 15 16 Н 111 1З lO 1.1 ll. l3 1.4 1.5 1.6 l1 1.1\ lЗ 30 31 .01.

Значение сохраняется в соответствующей позиции массива.

1 0.6=1 f

~ПЕЛЬСИНЫ .:J'

www.trk.kg