Python：用BigInts遍历Big Array，找到第一个重复项并打印出重复值的索引

Question

对于我大学的 Cryptographie 课程，我需要比较许多保存在数组中的 SHA 哈希。我需要比较数组索引的值。

数组中有重复项 - 我已经通过比较一组数组的长度和数组本身的长度来检查这一点。

现在我需要有重复值的索引。我找到了很多检查重复项的解决方案，但仅适用于短数组。我的数组长度为 300 万，每个索引中的值都在这个长度附近：864205495604807476120572616017955259175325408501.

我写了一个嵌套循环（来自 Java 并试图学习 python）。这是我的代码：

counter_outer = 0
while counter_outer < len(hash_value_array):
    counter_inner = counter_outer + 1
    while counter_inner < len(hash_value_array):
        if hash_value_array[counter_outer] == hash_value_array[counter_inner]:
            print(f"*****FOUND MATCH *****")
            print(f"Message [{counter_outer}] Hashvalue has same Value as Message [{counter_inner}]")
            safe_index1 = counter_outer
            safe_index2 = counter_inner
            counter_outer = len(hash_value_array)
            break
        else:
            print("------NO Match-----")
        counter_inner += 1
    counter_outer += 1

如您所想...这需要很长时间。

对我来说重要的是，我需要重复项所在的索引 - 而不是值。因此，例如，如果索引 100 中有一个 898，索引 1000001 中有一个 898，我只需要输出：100, 1000001

有什么建议吗？

Answer 1

您可以按照 Python 中的这些行做一些事情：

假设这个包含 5 个签名的列表（它们可以是整数或字符串，但我有字符串）：

li=['864205495604807476120572616017955259175325408501',
'864205495604807476120572616017955259175325408502',
'864205495604807476120572616017955259175325408503',
'864205495604807476120572616017955259175325408501',
'864205495604807476120572616017955259175325408502']

您可以创建一个列表字典，每个列表都是重复项的索引：

idx={}
for i, sig in enumerate(li):
    idx.setdefault(sig, []).append(i)

如果您创建 li 3,000,000 个条目，在我的计算机上运行大约需要 550 毫秒，在您的计算机上可能也差不多。

然后您可以像这样找到重复项：

for sig, v in idx.items():
    if len(v)>1:
        print(f'{sig}: {v}')

打印：

864205495604807476120572616017955259175325408501: [0, 3]
864205495604807476120572616017955259175325408502: [1, 4]

如果你只想要第一个副本，你可以像这样修改第一个循环：

idx={}
for i, sig in enumerate(li):
    if sig in idx:
        print(f'Duplicate {sig} at {idx[sig]} and {i}')
        break 
    else:
        idx[sig]=i

打印：

Duplicate 864205495604807476120572616017955259175325408501 at 0 and 3

但说实话 - 我不明白为什么这样快得多。

你的超级慢，因为它有 O n**2 嵌套 while 循环的复杂性。您正在为每个元素遍历整个数组。我在这里向您展示的方法只是在整个列表上循环一次 -- 而不是 300 万次！

Python：用BigInts遍历Big Array，找到第一个重复项并打印出重复值的索引

Python: Iterate through Big Array with BigInts, find first duplicate and printout the indexes of the duplicate Values

python

arrays

loops

list

duplicates