Оценка количества уникальных элементов в большом списке

Оценка количества уникальных элементов в большом списке

× Версия для печати

Сегодня у нас локальный день программиста (на этом блоге), — в начале недели, пока мозги ещё относительно свежие, разомнем-ка свои извилины, поскрипим нейронами и всё в таком духе...

Попробуйте решить задачу — дан список, содержащий 100 триллионов элементов. Элементы в списке могут повторяться. Необходимо оценить количество уникальных элементов в этом списке. Методы точного подсчета уникальных элементов не подходят, т.к. они требуют слишком много дополнительной памяти — ее количество должно быть пропорционально количеству уникальных элементов в списке.

Вначале рассмотрим основные методы точного подсчета уникальных элементов, чтобы понять, зачем им нужно столько много дополнительной памяти. Затем рассмотрим один из простейших методов оценки количества уникальных элементов, который требует существенно меньше дополнительной памяти.

Основные методы точного подсчета уникальных элементов в списке

Метод множеств. Записываем все элементы в структуру данных типа «множество», пропуская дупликаты, после чего подсчитываем количество элементов в множестве. Очевидно, этот метод требует много памяти. Также скорость работы этого метода мгновенно падает в 10000 раз, как только уникальные элементы множества перестают помещаться в оперативную память.
Метод битовых карт. Этот метод подходит лишь для элементов, чьи значения могут быть представлены целыми числами в ограниченном диапазоне. Если мы знаем максимально возможное значение элемента в списке (Nmax), то мы можем создать битовую карту, содержащую Nmax-битов. Затем проходимся по всем элементам списка, устанавливая соответствующий бит в карте для каждого элемента. После этого подсчитываем количество установленных битов.
Хотя этот метод требует меньше памяти, чем метод множеств — в лучшем случае требуется всего лишь один бит на каждый уникальный элемент, методу битовых карт может потребоваться слишком много памяти для больших Nmax. Он также начинает тормозить, когда битовая карта перестает помещаться в оперативной памяти.
Метод сортировки. Сортируем все элементы, после чего проходимся по отсортированному списку, подсчитывая лишь уникальные элементы и пропуская дубликаты.
С первого взгляда этот метод кажется тормозным — ведь все знают, что любая сортировка сравнением работает медленнее, чем создание хэш-таблицы или битовой карты (сортировка сравнением для n элементов в лучшем случае требует O(n*ln(n)) операций, в то время как создание множества из тех же элементов на основе хэш-таблиц требует O(n) операций).

Но у метода подсчета уникальных элементов с помощью сортировки есть два важных преимущества:

Существуют эффективные методы сортировки, способные быстро сортировать списки элементов, не умещающиеся в оперативную память. Вот два основных алгоритма быстрой сортировки списков, не умещающихся в оперативную память:

Разбить список на части, умещающиеся в оперативной памяти; быстро отсортировать эти части, после чего соединить отсортированные части в один отсортированный список, используя n-way merge. Очевидно, что различные части списка могут быть отсортированы параллельно. Это позволяет существенно уменьшить суммарное время, необходимое на сортировку. Основное преимущество этого алгоритма — его вычислительная сложность не зависит от порядка элементов в списке. Этот алгоритм обычно используется программах, ориентированных на работу на одном компьютере. Например, для реализации SELECT COUNT(DISTINCT *) в СУБД.
Мысленно разделить список на N равных частей, чтобы каждая часть умещалась в оперативную память; выбрать из списка N-1 случайных элементов, отсортировать их и поместить в список A (для выборки случайных элементов из большого списка можно воспользоваться алгоритмом «reservoir sampling»); дополнить список A спереди элементом «минус бесконечность» и сзади элементом «плюс бесконечность»; разделить начальный список на N частей, чтобы каждая часть содержала только элементы со значениями в пределах [A[i] ... A[i+1] ); отсортировать каждую часть, помещающуюся в память; если какая-нибудь часть не помещается в память, то рекурсивно применить для нее этот же алгоритм. После того, как все части отсортированы, соединить их в один отсортированный список.

Данный алгоритм сортировки на практике работает быстрее первого алгоритма, т.к. в нем почти все операции могут быть выполнены параллельно. Но у него есть один недостаток — его вычислительная сложность зависит от качества выборки случайных элементов. В худшем случае его скорость может упасть до O(n^2) . Этот алгоритм обычно используется в программах, ориентированных на параллельную работу на нескольких компьютерах. Например, в MapReduce.

При подсчете элементы в отсортированном списке посещаются последовательно. Это в 10000 раз быстрее, чем поиск случайного бита в битовой карте или поиск случайного элемента во множестве, если соответствующие структуры данных не помещаются в оперативную память. К тому же подсчет уникальных элементов в отсортированном списке может быть элементарно распараллелен.

Несмотря на существенное преимущество в скорости при подсчете большого количества уникальных элементов, метод сортировки все равно требует большое количество дополнительной памяти, которое пропорционально количеству элементов в списке.

Методы оценки количества уникальных элементов в большом списке

На практике иногда достаточно знать примерное количество уникальных элементов с некоторой погрешностью. Для таких случаев существуют быстрые алгоритмы, которым необходимо намного меньше дополнительной памяти по сравнению с алгоритмами, упомянутыми в предыдущем разделе. Рассмотрим один из таких алгоритмов.

Для каждого элемента списка вычисляется значение хэш-функции, удовлетворяющей следующим условиям:

Количество различных значений хэш-функции должно превышать ожидаемое количество уникальных элементов, чтобы минимизировать количество хэш-коллизий, когда различные элементы имеют одинаковое значение хэш-функции. В идеальном случае все элементы должны иметь различные значения хэш-функции. Это условие необходимо для того, чтобы количество уникальных элементов в списке могло быть оценено, как количество уникальных хэш-значений.
Хэш-значения для элементов из списка должны быть равномерно распределены по области значений хэш-функции. Это условие необходимо, чтобы суммарное количество уникальных хэш-значений для элементов можно было оценить, подсчитав лишь количество уникальных хэш-значений, попавших в заданный интервал. Тогда суммарное количество уникальных хэш-значений может быть вычислено как количество хэш-значений в заданном интервале, переменоженное на количество таких интервалов, помещающихся в области значений хэш-функции.

Этим условиям могут удовлетворять различные хэш-функции. Например, все криптографические хэш-функции — они имеют большую область значений (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.

Если вас вообще заинтересовала эта тема, то можете углубиться в нее с помощью вот этой статьи.