Я играю на работе с очень большими наборами данных, обычно несколькими миллиардами элементов, которые все поддерживаются в memcached облако и периодически сбрасывается в файлы, и для одной из моих задач я пытаюсь подсчитать мощность этого набора.
В каком-то контексте каждый элемент содержит IP-адрес и некоторые другие атрибуты, идентифицирующие человека и закодированные в base64, размер элемента - 20 байт. Уменьшение размера элемента путем удаления некоторых полей не представляется возможным.
Вот что-то, что эмулирует мой набор данных как версию в памяти (спасибо этот пост для генерации строки):
import base64, os
dataset_size = 10000000000 # that 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]
Мой первый подход состоял в том, чтобы использовать hashset следующим образом:
uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)
Хотя это теоретически отлично работает на небольшом наборе данных, как вы можете догадаться, есть икота:
- Я не могу делать никаких предположений о уникальности моих данных. У меня могло бы быть 50% моего набора данных, который уникален, или я мог бы иметь 100% точно также. Это генерируется динамически с регулярными временными интервалами и варьируется в зависимости от множества факторов (например, времени дня).
- Размер набора данных в 10 миллиардов. Каждый элемент, закодированный в базе 64, составляет 20 байт, раз 10 миллиардов - это несколько сотен гигабайт в среднем. К сожалению, у меня нет доступа к машине с такой большой памятью!
Я сделал домашнее задание и нашел в лучшем случае некоторые исследовательские статьи или некоторые неясные библиотеки, но частью этой цели является понимание того, какой подход работает и почему.
Итак, я обращаюсь к вам с пользователями Python, знаете ли вы какой-либо алгоритм, который поможет мне эффективно оценить мощность? По сложности я имею в виду, что меня не волнует сложность времени выполнения, но я больше ориентируюсь на космическую сложность. Я не против жертвовать некоторой точностью, если это значительно повышает производительность (поэтому мне не обязательно знать точное количество уникальных, даже если это было бы идеальным, но, вероятно, не жизнеспособным подходом). Я бы сказал, что до 5% будет приемлемым. Я ищу что-то специально в Python для этого проекта.
Спасибо за любую помощь, которую вы можете предоставить!
Как отмечали некоторые люди, я мог бы использовать Hadoop/MR, но для этих конкретных проектов мы не хотим идти MR и хотели бы изучить алгоритмы, чтобы сделать это на одной машине эффективно, поскольку это может быть применяется к нескольким другим различным проектам.
