Самый быстрый способ получить уникальные значения из двух списков

Question

Есть два списка, в которых очень много элементов - 1 000 000 и больше в каждом.

a = ['a1', 'a2' , ... , 'a999999']
b = ['a1', 'b2', 'a3', ...., 'a999999']

Необходимо получить значения из списка b, которых нет в списке a.

c = []
for value in b:
    if value not in a:
        c.append(value)

Есть ли способ ускорить сравнение, если учесть, что значений в списках много миллионов?

Answer 1

Можно отсортировать один массив за nlog(n), и, проходя циклом по неотсортированному массиву сравнивать с отсортированным, ища в последнем doubling или бинарным поиском. Получится nlog(n) на сортировку 1 массива + m*log(n) на поиск = (m+1) * log(n) сложность, что меньше квадрата, но не факт что быстрее :))

Answer 2

Можно воспользоваться операцией симметричной разности для двух множеств

    (set(a) - set(b)) + (set(b) - set(a))

БЛОГ НА HUSL

Самый быстрый способ получить уникальные значения из двух списков

Ответы (2 шт):