Самый эффективный способ перекрестного сравнения миллионов хеш-значений в списке
У меня есть список из 9 миллионов хеш-значений. Мне нужно сравнить каждое значение (hash0) в списке с остальными значениями:
for i, hash0 in enumerate(hashes_list):
for hash1 in hashes_list[i:]:
if hash0 -hash1 < threshold:
#do something
Приведенное выше решение имеет квадратичную сложность, и его выполнение занимает вечность (даже на сервере). Каков эффективный способ сопоставления этих 9 миллионов хэшей?
Вот пример значений hashes_list:
8c59ac5169e673a6
ab9f545497b05683
9590ee98373e1e19
c1274a5e1e150e7f
938f7c782dc6241b
Я попытался взять первые три шестнадцатеричных символа хеш-ключа в виде строки и выполнить первое сравнение на основе этих первых, но это совсем не оптимизировало время. Что касается хеширования, то они являются результатом перцептивного хеширования изображений jpg (type=imagehash.ImageHash)
Ответы 2
Предполагая, что вычитание - это просто обычное вычитание, попробуйте сначала отсортировать, сортировка может иметь временную сложность 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» без дополнительной проверки.
Поскольку вы не хотите сравнивать точные совпадения ваших значений, это легко исключает использование наборов или диктов -
но вы, безусловно, можете извлечь выгоду из использования лучшей структуры данных, которая больше подходит для этой цели.
Если сравнение значений, которое вам нужно, является числовым, как кажется в вашем коде, это выглядит как простая сортировка списка (а сортировка 9 миллионов значений вполне осуществима), и сравнения соседей в результате может быть достаточно, чтобы уменьшить вашу сложность с O( n**2) до O(n).
На ум приходят две вещи. Сначала распараллелите свой скрипт. Во-вторых, попытайтесь найти способ уменьшить значения для сравнения, т. е. не тратить время на сравнение значений хеш-функции, которые явно не совпадают. В базе данных это можно сделать с помощью индексов. Например, скажем, это строки, сравнивайте строки только с другими строками, начинающимися с той же буквы. Но для этого нужно знать, как вы на самом деле сравниваете эти хэш-значения. Можешь подробнее объяснить, что ты делаешь в очереди
if hash0 -hash1 < threshold:? Какие типы данных являются вашими переменными hash0 и threshold?