python - 你如何在 Python 中有效地计算非常大的数据集的基数？

Question

我一直在处理一些非常非常大的数据集，通常有数十亿个元素，它们都保存在 memcached 中。云并定期转储到文件中，对于我的一项任务，我正在尝试计算该集合的基数。

对于某些上下文，每个项目都包含一个 IP 和一些其他标识人的属性，并以 base64 编码，项目大小为 20 字节。通过删除某些字段来减小项目的大小是不可能的。

这是将我的数据集模拟为内存版本的东西(感谢 this post 用于字符串生成):

import base64, os

dataset_size = 10000000000 # that's 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]

我的第一种方法是使用这样的哈希集:

uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)

虽然这在理论上适用于小型数据集，但您可以猜到其中存在问题:

• 我无法对我的数据的唯一性做出任何假设。我的数据集可以有 50% 是唯一的，也可以有 100%。这是按固定时间间隔动态生成的，并根据许多因素(例如一天中的时间)而变化
• 数据集大小为 100 亿。以 base 64 编码的每个项目都是 20 个字节，乘以 100 亿平均是几百千兆字节。不幸的是，我无法使用具有那么多 RAM 的机器!

我已经完成了我的功课，充其量只能找到一些研究论文或一些晦涩的图书馆，但这样做的部分目的是了解哪种方法有效以及为什么有效。

所以我呼吁各位 Python 用户，你们知道有什么算法可以帮助我有效地估计基数吗？我所说的复杂性是指我不太关心运行时复杂性，但我更关注空间复杂性。如果它极大地提高了性能，我不介意牺牲一点准确性(所以我不一定需要知道唯一值的确切数量，即使那是理想的，但可能不是一种可行的方法)。我会说最多 5% 是可以接受的。我正在为这个项目寻找专门用 Python 编写的东西。

感谢您提供的任何帮助!

正如一些人指出的那样，我可以使用 Hadoop/MR，但对于这个特定项目，我们不想采用 MR 方式，并且希望探索算法以在一台机器上高效地执行此操作，因为这可能是应用于其他几个不同的项目。

Answer 1

我建议使用 Hash Sketches，即 (Super)Log Log sketches 或 Hyper Log Sketches。

您可以检查并可能使用和改进我制作的简单 python 实现: https://github.com/goncalvesnelson/Log-Log-Sketch