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

EN

我一直在使用一些非常非常大的数据集，通常是数十亿个元素，这些数据都保存在memcached云中，并定期转储到文件中，对于我的一项任务，我会尝试计算这些数据集的基数。

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

下面是将我的dataset模拟为内存中版本的东西(感谢用于字符串生成的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%。这是以固定的时间间隔动态生成的，并根据许多因素( example)
• Dataset大小为100亿的一天中的时间)而变化。以64进制编码的每个项目是20字节，乘以100亿平均是几百千兆字节。不幸的是，我无法访问内存那么大的机器!

我已经做了功课，充其量找到了一些研究论文，或者一些晦涩的库，但这其中的一部分目标是理解什么方法有效以及为什么。

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

感谢您能提供的任何帮助！

正如一些人所指出的，我可以使用Hadoop/ MR，但对于这个特定的项目，我们不想走MR的路，而是想探索在一台机器上高效地完成这项工作的算法，因为这可以应用于其他几个不同的项目。