交叉比较列表中数百万个哈希值的最有效方法

Question

我有一个包含900万个哈希值的列表。我需要将列表中的每个值(hash0(与其他值进行比较：

for i, hash0 in enumerate(hashes_list):
for hash1 in hashes_list[i:]:
if hash0 -hash1 < threshold:
#do something

上面的这个解决方案具有二次复杂性，运行起来需要很长时间(甚至在服务器中(。交叉匹配这900万个哈希的有效方法是什么？

以下是hashes_list值的示例：

8c59ac5169e673a6
ab9f545497b05683 
9590ee98373e1e19 
c1274a5e1e150e7f
938f7c782dc6241b

Answer 1

假设减法只是一个常规减法，请先尝试排序，排序可以是O(nLn(n((的时间复杂度，这比n^2 好一点

这样，您就可以用两个指针迭代一次，找到彼此接近的哈希组。这将是n*k的复杂性，其中n是哈希数，k是匹配的平均数。

伪代码看起来有点像

sort(hashes_list) #large to small
count = size(hashes_list)
i = 0
while i < count:
j = i + 1
while hashes_list[i] - hashes_list[j] < threshold:
#do something
j += 1
i += 1

在某些情况下，您可以跳过检查。例如，如果0-10都在阈值内，则1-10也将是#做某事；只需要在没有另一个检查的情况下为每个调用

Answer 2

由于您不想比较值的精确匹配，因此排除了使用集合或dicts-的可能性

但是，使用更适合该目的的更好的数据结构肯定会让您受益。

如果你需要的值比较是数字的，就像你的代码中看起来的那样，它看起来就像是简单地对列表进行排序(对900万个值进行排序是非常可行的(，并且比较结果中的邻居就足以将你的复杂性从O(n**2(降低到O(n(。