Есть ли параллельный способ сравнить два больших списка целых чисел?

Question

У меня есть список из 8 миллионов уникальных целых чисел, представляющих идентификаторы, скажем, книг.Дело в том, что этот список меняется каждый семестр (стертые идентификаторы, новые идентификаторы).Использование только понимания списка для получения нового списка «новых идентификаторов» или «стертых идентификаторов» занимает вечность.

Я попытался выполнить две операции, чтобы найти два ранее описанных элемента (стертые идентификаторы, новые идентификаторы)

l1 = [1,2,3,4,5]
l2 = [0,2,3,4,6,7]

new_ids = [x for x in l2 if x not in l1]
erased_ids = [x for x in l1 if x not in l2]

Существует ли параллельный способ обработки этих сравнений для повышения производительности?

Answer 1

Вы можете попытаться сделать это с помощью многопроцессорной обработки, но это не очень вам поможет, так как это только сократит время для вычисления ответа пополам.Вы сказали, что это навсегда, а навсегда / 2 еще навсегда.Вам нужен другой алгоритм.Попробуйте установить

set1 = set(l1)
set2 = set(l2)

new_ids = list(set2 - set1)
erased_ids = list(set1 - set2)

Ваш алгоритм работает в O (n ^ 2).Это потому, что [x for x in l2 if x not in l1] проверяет все l1 для x, для каждого x в l2.Если l1 и l2 имеют 8m элементов, для этого требуется 8000000 ^ 2 = 160000000000000 проверок.

Вместо этого набор - это структура данных (которая использует внутреннее хеширование), которая может проверять членство элемента в одной операции, или O (1).Теоретически, проверка того, находится ли число x в наборе, занимает столько же времени, независимо от того, имеет ли набор один элемент или 8 миллионов.Это не относится к списку.

Наборы также могут быть вычтены.set2 - set1 означает «вещи в set2, которых нет в set1».Это делается за O (n) время, я предполагаю, выполнив n O (1) проверок на членство.

Построение наборов на первом месте - это также O (n) время, так как добавление к наборуO (1) операция, и вы должны сделать это с n элементами.

Следовательно, весь этот алгоритм выполняется за O (n) времени.