我一直在使用一些非常非常大的数据集,通常是数十亿个元素,这些数据都保存在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)
虽然这在理论上在小数据集上工作得很好,但您可以猜到有一个小问题:
我已经做了功课,充其量找到了一些研究论文,或者一些晦涩的库,但这其中的一部分目标是理解什么方法有效以及为什么。
所以我呼吁Python用户,你们知道什么算法可以帮助我有效地估计基数吗?所谓复杂性,我的意思是我不太关心运行时间复杂性,但我更关注空间复杂性。如果它极大地提高了性能,我不介意牺牲一点准确性(所以我不一定需要知道唯一的确切数量,即使这是理想的,但可能不是一个可行的方法)。我想说5%是可以接受的。我正在寻找一些专门为这个项目在Python中的东西。
感谢您能提供的任何帮助!
正如一些人所指出的,我可以使用Hadoop/ MR,但对于这个特定的项目,我们不想走MR的路,而是想探索在一台机器上高效地完成这项工作的算法,因为这可以应用于其他几个不同的项目。
发布于 2012-04-16 04:03:05
我推荐使用Hash Sketches,即(Super)Log Sketches或Hyper Log sketches。
您可以检查并使用和改进我制作的简单python实现:https://github.com/goncalvesnelson/Log-Log-Sketch
发布于 2012-04-16 04:12:47
我建议您尝试使用bloom filter。即使有如此大量的数据,您也可以在适度的系统要求下实现极低的错误率。假设您将使用(大致)最优k=ln(2)*(布隆过滤器大小,单位为位)/(100亿),您可以计算布隆过滤器大小,单位为-((100亿)*ln(期望误报率))/ln(2)^2。
例如,在内存不足2 get的情况下,您可以获得0.1%的错误率。这一切的一个非常快速和极其简单的实现是http://mike.axiak.net/python-bloom-filter/docs/html/
https://stackoverflow.com/questions/10164608
复制相似问题