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

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 something”而无需再次检查

Answer 2

由于您不想比较值的精确匹配，因此很容易排除使用集合或字典的可能性 -

但是您当然可以从使用更适合该目的的更好的数据结构中受益。

如果您需要的值比较是数字，就像您的代码中显示的那样，看起来只是对列表进行排序（并且对 900 万个值进行排序是非常可行的），并且比较结果中的邻居就足以减少你的复杂度从 O(n**2) 到 O(n)。

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

Most efficient way to cross compare millions of hash values in a list

python

hash

list

time-complexity