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

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(n Ln(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 也会在阈值内，并且只需为每个调用“#do some”而无需再次检查