问题
我有一个很大的数据集(> 500e6行),已将其放入pytables数据库中。
假设第一列是ID,第二列是每个ID的计数器。每个ID计数器组合必须是唯一的。我要查找的500e6行中有一个非唯一行。
首先,我已经做了类似的事情:
index1 = db.cols.id.create_index()
index2 = db.cols.counts.create_index()
for row in db:
query = '(id == %d) & (counts == %d)' % (row['id'], row['counts'])
result = th.readWhere(query)
if len(result) > 1:
print row
我承认这是一种蛮力方法。有什么改进建议吗?
更新
当前的蛮力运行时间是8421分钟。
解决方案
感谢大家的意见和建议。我设法使用以下方法将运行时缩短至2364.7秒:
ex = tb.Expr('(x * 65536) + y', uservars = {"x":th.cols.id, "y":th.cols.counts})
ex = tb.Expr(expr)
ex.setOutput(th.cols.hash)
ex.eval()
indexrows = th.cols.hash.create_csindex(filters=filters)
ref = None
dups = []
for row in th.itersorted(sortby=th.cols.hash):
if row['hash'] == ref:
dups.append(row['hash'] )
ref = row['hash']
print("ids: ", np.right_shift(np.array(dups, dtype=np.int64), 16))
print("counts: ", np.array(dups, dtype=np.int64) & 65536-1)
我的最大值小于2 ^ 16,因此可以生成完美的哈希。我实际上是将两列打包为32位int。
一旦生成了csindex,遍历排序后的值并对重复项进行邻居测试就变得相当简单了。
可以稍微调整一下此方法,但是我正在测试一些可能提供更自然解决方案的替代方法。
最佳答案
我想到了两种显而易见的技术:哈希和排序。
A)定义一个哈希函数,将ID和Counter组合为单个紧凑值。
B)计算每个哈希码出现的频率
C)从您的数据中选择所有具有哈希冲突的数据(这应该是“小得多”的数据集)
D)对该数据集进行排序以查找重复项。
需要选择A)中的哈希函数,使其适合主存储器,同时提供足够的选择性。为此,可能使用两个2 ^ 30左右大小的位集。您可以承受5-10%的冲突,这仍应减少数据集的大小,以允许事后进行快速的内存内排序。
本质上,这是一个布隆过滤器。
关于python - 在具有500e6行的hdf5 pytable中查找重复项,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/20743135/