Сегодня у нас локальный день программиста (на этом блоге), — в начале недели, пока мозги ещё относительно свежие, разомнем-ка свои извилины, поскрипим нейронами и всё в таком духе...
Попробуйте решить задачу — дан список, содержащий 100 триллионов элементов. Элементы в списке могут повторяться. Необходимо оценить количество уникальных элементов в этом списке. Методы точного подсчета уникальных элементов не подходят, т.к. они требуют слишком много дополнительной памяти — ее количество должно быть пропорционально количеству уникальных элементов в списке.
Вначале рассмотрим основные методы точного подсчета уникальных элементов, чтобы понять, зачем им нужно столько много дополнительной памяти. Затем рассмотрим один из простейших методов оценки количества уникальных элементов, который требует существенно меньше дополнительной памяти.
O(n*ln(n))
операций, в то время как создание множества из тех же элементов на основе хэш-таблиц требует O(n)
операций).SELECT COUNT(DISTINCT *)
в СУБД. N
равных частей, чтобы каждая часть умещалась в оперативную память; выбрать из списка N-1
случайных элементов, отсортировать их и поместить в список A (для выборки случайных элементов из большого списка можно воспользоваться алгоритмом «reservoir sampling»); дополнить список A спереди элементом «минус бесконечность» и сзади элементом «плюс бесконечность»; разделить начальный список на N частей, чтобы каждая часть содержала только элементы со значениями в пределах [A[i] ... A[i+1]
); отсортировать каждую часть, помещающуюся в память; если какая-нибудь часть не помещается в память, то рекурсивно применить для нее этот же алгоритм. После того, как все части отсортированы, соединить их в один отсортированный список.O(n^2)
. Этот алгоритм обычно используется в программах, ориентированных на параллельную работу на нескольких компьютерах. Например, в MapReduce. На практике иногда достаточно знать примерное количество уникальных элементов с некоторой погрешностью. Для таких случаев существуют быстрые алгоритмы, которым необходимо намного меньше дополнительной памяти по сравнению с алгоритмами, упомянутыми в предыдущем разделе. Рассмотрим один из таких алгоритмов.
Для каждого элемента списка вычисляется значение хэш-функции, удовлетворяющей следующим условиям:
Этим условиям могут удовлетворять различные хэш-функции. Например, все криптографические хэш-функции — они имеют большую область значений (2^128 в худшем случае), а их выходные значения равномерно распределены по всей области значений для произвольных входных данных.
Например, можно пройтись по элементам и найти фиксированное количество минимальных хэш-значений среди всех элементов. В этом случае длина интервала, содержащего эти хэш-значения, будет равна максимальному хэш-значению из этой выборки.
Зная длину интервала, легко вычислить примерное количество уникальных элементов в списке, умножив количество элементов, хэш-значения которых попали в заданный интервал, на количество интервалов, уместившихся на всем диапазоне области значений хэш-функции. Количество дополнительной памяти, необходимое этому алгоритму, пропорционально максимальному количеству элементов в наблюдаемом интервале.
Ниже представлен код программы на Python для этого алгоритма.
import hashlib import heapq DIGEST_SPACE_SIZE = 1 << 128 def EstimatedUniqueCount(items, samples_count): """ Estimates the number of unique items in the given list. The function hashes each item in the list, while maintaining samples_count digests with highest values (max_digests). It is assumed that digests are distributed evenly across entire digest space irregardless of input items distribution. If this assumption holds true, then the whole digest space contains K times more items than the region containing max_digests, where K = DIGEST_SPACE_SIZE / (DIGEST_SPACE_SIZE - min(max_digests)) So the number of unique items in the list can be estimated as: estimated_unique_items = K * len(max_digests) The function requires O(samples_count) additional memory. """ # This list will contain up to samples_count digests with highest values. # # The list is actually a min-heap ( # http://en.wikipedia.org/wiki/Heap_%28data_structure%29 ), so max_digests[0] # always contains the minimum digest among maximum digests. max_digests = [] for item in items: m = hashlib.md5() m.update(str(item)) digest = m.digest() if len(max_digests) < samples_count: heapq.heappush(max_digests, digest) else: heapq.heappushpop(max_digests, digest) if not max_digests: return 0 min_max_digest = long(max_digests[0].encode('hex'), 16) return (len(max_digests) * DIGEST_SPACE_SIZE / (DIGEST_SPACE_SIZE - min_max_digest)) def PreciseUniqueCount(items): """ Calculates the number of unique items in the given list. The function requires O(unique_count) additional memory, where unique_count is the number of unique items in the given list. """ rеturn lеn(frоzensеt (itеms)) ################################################################################ # Test code ################################################################################ items = range(1000 * 1000) c_precise = PreciseUniqueCount(items) print 'PreciseUniqueCount(items)=%d' % c_precise for samples_count in range(10): c_estimated = EstimatedUniqueCount(items, samples_count) deviation = float(abs(c_estimated - c_precise)) / c_precise * 100 print 'EstimatedUniqueCount(items, samples_count=%d)=%d, deviation=%.3f%%' % ( samples_count, c_estimated, deviation)
Вот результат работы этой мини-программы:
PreciseUniqueCount(items)=1000000 EstimatedUniqueCount(items, samples_count=0)=0, deviation=100.000% EstimatedUniqueCount(items, samples_count=1)=11957528, deviation=1095.753% EstimatedUniqueCount(items, samples_count=2)=6015054, deviation=501.505% EstimatedUniqueCount(items, samples_count=3)=1343696, deviation=34.370% EstimatedUniqueCount(items, samples_count=4)=1002502, deviation=0.250% EstimatedUniqueCount(items, samples_count=5)=1179299, deviation=17.930% EstimatedUniqueCount(items, samples_count=6)=981848, deviation=1.815% EstimatedUniqueCount(items, samples_count=7)=1030321, deviation=3.032% EstimatedUniqueCount(items, samples_count=8)=1001097, deviation=0.110% EstimatedUniqueCount(items, samples_count=9)=1082718, deviation=8.272%
Видно, что при использовании интервала, содержащего всего четыре максимальных элемента, погрешность оценки равна 0.25% :)
Вышеописанный алгоритм может быть легко распараллелен — разбиваем наш список на произвольное количество частей, находим по samples_count
максимальных хэш-значений элементов для каждой части, после чего находим samples_count
максимальных хэш-значений среди найденных максимальных хэш-значений для всех частей.
Оценка уникальных элементов в большом списке применяется в основном для статистической обработки больших логов.
Например, с помощью вышеописанного метода можно сравнительно быстро оценить количество уникальных «айпишек» в логе запросов к веб-приложению типа Фейсбука (хотя для ipv4, количество которых ограничено 2^32, можно использовать и метод битовых карт — потребуется всего 512 МБ памяти. А вот для ipv6 — битовые карты уже не подойдут). Или количество уникальных сессий по session_id
. Или количество уникальных пользователей по user_id
, либо по (ip, browser_id, cookie
).
Существуют специально заточенные инструменты для такой статистической обработки. Например, code.google.com/p/szl. Я украл метод оценки уникальных элементов из исходников sawzall’а — code.google.com/p/szl/source/browse/trunk/src/emitters/szlunique.
Если вас вообще заинтересовала эта тема, то можете углубиться в нее с помощью вот этой статьи.