在具有500e6行的hdf5 pytable中查找副本

Question

问题

我有一个大的(> 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,迭代排序的值并对重复进行邻居测试是相当简单的.

这种方法可能会稍微调整一下,但我正在测试一些可能提供更自然解决方案的替代方案.

Answer 1

我想到了两种明显的技术：散列和排序。

A) 定义一个哈希函数，将 ID 和 Counter 组合成一个紧凑的值。

B) 计算每个哈希码出现的频率

C）从您的数据中选择所有具有哈希冲突的数据（这应该是一个“小得多”的数据集）

D) 对该数据集进行排序以查找重复项。

A) 中的哈希函数需要选择适合主存的大小，同时提供足够的选择性。为此，可以使用两个大小为 2^30 左右的位集。您可以承受 5-10% 的冲突，这仍然会减少数据集大小，足以允许随后在内存中进行快速排序。

这本质上是一个布隆过滤器。