Linear counting: как да оценим броя на уникалните стойности

Как бихме могли да преброим уникалните стойности в някакъв набор от данни, ако данните са наистина много? Например може да имаме услуга, която мери броя на уникалните потребители на някакъв голям уебсайт или дори на цял .com/.bg/.whatever домейн или нещо такова.

Наивен подход

Ок, няма какво да се мисли, просто минаваме през данните и всяка стойност запазваме точно веднъж в някоя подходяща структура от данни. На Python бихме могли да го напишем приблизително така (кодът е излишно многословен, нарочно е такъв):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Работи. Добре, но какво ще стане, ако данните са 36-символни уникални идентификатори v4 и ако уникалните идентификатори са например десет милиона? Е… програмата пак ще пресметне правилната стойност, но колко памет ще заеме? Можем да го пресметнем. За простота ще предполагаме, че uuid наистина се запазва като низ от 36 символа. Едно uuid следователно заема 36 байта, десет милиона идентификатора заемат 360 MB.

Не е съвсем малко, нека си признаем. Ако уникалните идентификатори бяха сто милиона, щяхме да стигнем до порядъка на гигабайти заета памет. И при това още пресмятаме само това, което заемат самите данни. Добави някакъв overhead, който заема например Python/JavaScript, и можеш да стигнеш до порядъка на гигабайти и с десет милиона идентификатора:

Не искаш това. Как да излезем от положението?

Можем да опитаме да съхраняваме самите идентификатори по-ефективно, можем вместо Python да използваме C, с което значително ще намалим изискванията към паметта, но пак няма да е достатъчно и такава програма пак би заемала невероятно количество място. Остава да си зададем въпроса: наистина ли трябва да знаем съвсем точно дали уникалните стойности са точно 9 563 618? Би ли се случило нещо, ако работехме с броя 9 547 666? Ако отговорът ти е, че би се случило и че го искаш точно, заповядай. В противен случай нека покажем подходи, с които броят на уникалните стойности в набор от данни може да се оцени възможно най-точно, най-бързо и с минимални изисквания към паметта.

Хеш функциите — нашето спасение

Ще разглеждаме хеш функция, която приема на вход низ и връща на изхода някакво n-битово число. Ако си свикнал по-скоро с хеш функции, които „връщат низ“, просто си представи, че този низ после се преобразува в число, няма нищо сложно. Броят на битовете показва колко голямо е числото. 8-битова функция връща число, което заема осем бита, а в осем бита могат да се запазят 2⁸ различни стойности, обикновено цели числа от 0 до 255. По-нататък ще работим с 24-битова хеш функция. Такава функция връща 2²⁴ различни стойности, което е 16 777 216.

Вместо да запазваме самите стойности, ще запазваме техните 24-битови хешове. За запазването на десет милиона 24-битови хеша ни трябват 30 MB. Това е с цял порядък по-добре от предишните 360 MB. Кодът би могъл да изглежда така:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

Функцията hash е вградена функция на Python и връща цяло число, функцията nhash показва наивна реализация на n-битова хеш функция; не е важно да разбереш как работи, защото така или иначе не работи правилно — резултатът ѝ не заема 24 бита, но сега това няма значение, важен ми е принципът.

След това следва функцията count_unique_using_nhash, която брои уникалните стойности. Минава през всички стойности, пресмята хеша им и го запазва в променливата found, ако тази стойност още не е там.

Проблемът на този подход е, че хеш функцията може да върне за различни низове една и съща контролна сума (checksum) — може да настъпи колизия. Колкото повече такива колизии настъпят, толкова по-неточен резултат получаваме. Функцията count_unique_using_nhash почти винаги ще върне по-малък брой уникални стойности от действителния.

И коя хеш функция да изберем? Не е толкова важно, но по принцип се препоръчва някакъв вариант на MurmurHash.

Битови карти

Обърна ли внимание, когато учеше програмиране на C? Ако да, познаваш битовите карти. Как могат да се използват те?

Идеята ще скицираме с масив. Ние всъщност не е нужно да пазим пресметнатите контролни суми, можем да създадем масив с дължина 2²⁴ и да инициализираме всички елементи с нула. После, когато срещнем някаква контролна сума — а тя е число! — записваме в този масив на индекс checksum единица, с което отбелязваме, че вече сме намерили тази контролна сума. Броят на уникалните елементи ще е приблизително равен на броя на единиците в този масив. Кодът би могъл да изглежда така:

def count_unique_using_array(values):
    # списък с дължина 2^24, инициализиран с нули
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Използването на масив обаче е в този случай много скъпо откъм памет, защото във всяка клетка трябва да запазим винаги или единица, или нула. Вместо това можем да използваме битово поле. За да разбереш, цяло число (integer) може да се запази например в 32 бита. Ако преобразуваме числото 354 в двоична бройна система, получаваме 101100010. Като 32-битов integer числото 354 би било запазено в компютъра (за подробностите не ни пука, нали?) така:

00000000 00000000 00000001 01100010

Това е доста приятен формат, който бихме могли да използваме, нали? Във функцията си искаме да запазваме само единици и нули, а току-що разбрахме, че обикновеното число всъщност не е нищо друго освен купчина нули и единици (като всичко в компютъра…). С други думи, с помощта на побитови операции можем да запазим единица така, че тя наистина да заема един бит.

Връщаме се към нашата функция с масива. Ако я пренапишем с битови полета, за 24-битова хеш функция ще ни стигне битово поле с големина 2²⁴ бита, а това са 2 MiB. Това е сериозно подобрение!

При използване на 32-битова хеш функция, която има 2³² различни изходни стойности, което е 4 294 967 296, ще ни трябва битово поле с големина половин гигабайт. Това не е никак зле, като се има предвид, че с него можем да броим уникални стойности до порядъка на милиарди.

Linear Counting

Вече споменах, че при използване на хеш функция получаваме само оценка на броя на уникалните стойности. Тази оценка е толкова по-неточна, колкото повече броят на уникалните стойности се приближава до броя на различните изходни стойности на хеш функцията. Логично е, че ако имаме набор от данни, в който има пет милиарда уникални стойности, с 24-битова хеш функция просто няма да го преброим.

Оценката, която пресмятаме с хеш функции, обаче може да се уточни допълнително. За това се използва проста идея — колкото повече уникални стойности има в набора от данни, толкова по-вероятно е с времето да възникват колизии. (Колизия = два различни входа имат един и същ изход от хеш функцията, една и съща контролна сума.) Сега ще пресмятаме малко, затова въвеждаме няколко променливи:

• Ще работим с n-битова хеш функция h.
• Броят на всички възможни изходи на функцията h е следователно равен на 2n. Този брой означаваме с буквата m, т.е. m=2n.
• Битовото поле, в което ще запазваме кои контролни суми сме намерили, означаваме с главната буква A. Полето A има дължина m.
• Ако минем с нашия алгоритъм през целия набор от данни, някои стойности в битовото поле ще са равни на нула, а някои на единица. Най-вече ще ни интересува отношението „брой нули, разделен на дължината на полето“, което ни дава относителния дял на нулите в битовото поле. В началото този дял е равен на 1, защото полето е инициализирано с нули. Ако беше 50 на 50, делът щеше да е равен на една втора и т.н. Тази стойност означаваме с Z и я пресмятаме като Z = брой нули / m.

Сега колкото по-голяма е стойността на Z, толкова по-голяма е сигурността, че оценката ни за броя на уникалните стойности е точна. Ако например минем през празен набор от данни, в битовото поле ще останат само нули и стойността на Z ще е равна на едно — имаме пълна сигурност, че в нашия набор от данни има толкова уникални елементи, колкото са единиците в битовото поле — нула.

Ако стойността на Z е равна на 0,99, това означава, че битовото поле е запълнено с единици само на една стотна. 99% от полето съдържа нули. Това още е добре, вероятно по време на пресмятането не са настъпили твърде много колизии и поправката ще е никаква или съвсем малка. Ако обаче стойността на Z е равна на 0,05, само 5% от полето е останало нулево и вероятно по време на пресмятането сме се натъкнали на много и много колизии — ще е нужна голяма поправка.

Как обаче да пресметнем тази поправка? Ще си помогнем с логаритъма, функция, която има този вид:

Ние се интересуваме от червената част на интервала (0; 1]. Ако нанасяме на оста x стойността Z, постигаме това, че колкото по-голямо е Z, толкова повече стойността на y се приближава до нула. И обратно — колкото по-малко е Z, толкова по-малка ще е стойността на y. Окончателната оценка пресмятаме, като умножим това число по -m. Забележи, че за достатъчно ниска стойност на Z получаваме число, което е дори по-малко от -1, и ако умножим тази стойност по -m, получаваме оценка, по-голяма от m: оценили сме, че броят на уникалните стойности е по-голям от броя на всички възможни контролни суми, които могат да излязат от хеш функцията h.

Цялата формула за пресмятане на броя p на уникалните стойности би изглеждала така:

$$p=-m\cdot \ln Z$$

Реализацията (без битови полета, само с обикновени масиви) би могла да изглежда така:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log тук е натурален логаритъм с основа e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

Във функцията linear_counting първо пресмятаме първата оценка с помощта на предишния алгоритъм, който използва n-битова хеш функция. После пресмятаме дела на нулите в масива и извършваме поправката по формулата. Логаритъмът в кода е натурален логаритъм. Променливата nonunique_values съдържа number_of_unique_values уникални низове, в този пример в списъка nonunique_values има следователно десет хиляди уникални стойности. Странният код на шестия ред прави така, че в масива да има повече еднакви стойности: просто в края на списъка прикачваме същия списък от стойности и всяка стойност е в масива два пъти. И след това пресмятаме. В идеалния случай функцията трябва да върне, че списъкът съдържа десет хиляди уникални стойности. Изход:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Тъй като всеки път се генерира различен списък nonunique_values, резултатите ще се различават при всяко извикване. Използвахме 16-битова хеш функция. Виждаме, че първата оценка от функцията count_unique_using_array е била, че списъкът съдържа 9289 уникални стойности. Тази оценка уточнихме с корекцията на 10 017, което вече е доста прилично: нашата оценка е по-голяма само с 0,17%, докато преди беше по-малка със 7,11% — това е доста.

Ако вземем „по-голяма“ хеш функция, например 24-битова, ще получим по-точен резултат:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

Още първоначалната оценка беше ОК, уточняването я доведе до точно десет хиляди. За пример можем да опитаме един милион уникални идентификатора, т.е. number_of_unique_values = 1000000. С 24-битовата хеш функция стигаме до тези резултати:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Става. При това, ако го реализираме като битово поле, полето би трябвало да изяде само споменатите два мегабайта (+ каквото изяде езикът). Според мен е доста добре. But we can do better! Much better. Но чак следващия път.

Междувременно можеш да прочетеш статията A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Или можеш да продължиш със следващата част от поредицата: алгоритъмът min-value.