вычитание списков в python, оптимизация скорости

Question

Чтобы найти подстановку двух списков в Python, я использую:

names_of_files_not_dowloaded = [item for item in total_files if item not in names_of_files_downloaded]

Работает.

размеры списков:

общее количество файлов 56373 элемента

список загруженных файлов 28464 элемента

это длится 34 секунды.Почему-то у меня есть интуиция, что 34 секунды это слишком долго.Есть ли способ сделать это вычитание более эффективно?

спасибо

РЕДАКТИРОВАТЬ: элемент похож на 'AB12345'

В списках НЕ ИМЕЕТСЯ ПОВТОРЯЮЩИЙ ЭЛЕМЕНТ, ОНИУЖЕ НАБОРЫ

Answer 1

Просто сделайте files_downloaded набором вместо списка.Для списков требуется полная итерация списка для проверки членства, каждый раз, когда вы хотите выполнить проверку .Наборы, однако, намного эффективнее для поиска по .

Просто используйте:

downloaded_set = set(files_downloaded)
list_of_files_not_dowloaded = [item for item in total_files if item not in downloaded_set]

Это будет иметь начальную стоимость, чтобы поместить список в набор,но проверки членства после этого будут намного быстрее.

---

@juanpa.arrivillaga также упомянул в комментариях, что еще одной причиной падения производительности было in выполнение проверок на равенство строк, тогда как хэши сравниваютсяпри использовании Sets, а последнее намного дешевле.

Похоже, если я читаю право на источник, Списки CPython используют прямую проверку равенства для сравнения при проверке членства ,Предположительно, наборы используют хэши, и они кэшируются во время создания набора.

Answer 2

Если вас не волнует порядок элементов и в ваших списках нет дубликатов, вы можете просто использовать:

diff = set(total_files) - set(files_downloaded)

Если вам нужен вывод в виде списка:

diff = list(set(total_files) - set(files_downloaded))

set переопределяет метод __sub__() и использует его как разность наборов, а это то, что вы ищете.

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

Answer 3

total_files_set = set(total_files)
files_downloaded_set = set(files_downloaded)
files_not_dowloaded_set = total_files_set - files_downloaded_set 
list_of_files_not_dowloaded = list(files_not_dowloaded_set)

Или, если вы хотите в одну строку:

list_of_files_not_dowloaded = list(set(total_files) - set(files_downloaded))

Чтобы узнать больше обо всех операциях с использованием наборов, вы можете проверить это здесь

РЕДАКТИРОВАТЬ :
Я пробовал синхронизировать оба метода, используя 2 случайных списка

• Для подмножества с 50 000 элементов и надмножества с 100 000 элементов

timeit.timeit('l = list(set(l1)-set(l2))', 
setup='import random; l1 = random.sample(range(1000000), 100000); l2 = random.sample(range(1000000), 50000)', 
number = 10)

Выход:

0,39393879500130424

timeit.timeit('l = [item for item in l1 if item not in l2]', \
setup='import random; l1 = random.sample(range(1000000), 10000); l2 = random.sample(range(1000000), 5000)', \
number = 1)

Выход:

98.58012624000003

Если выслучается, уже есть оба набора, вместо того, чтобы преобразовать из списка:

timeit.timeit('l = list(s2-s1)', 
setup='import random; s1 = set(random.sample(range(1000000), 100000)); s2 = set(random.sample(range(1000000), 50000))', 
number = 10)

Вывод:

0.06160322100004123