Python: более быстрый способ фильтрации списка, используя его понимание - PullRequest
Новая
       6

Python: более быстрый способ фильтрации списка, используя его понимание

0 голосов
/ 15 февраля 2019

Рассмотрим следующую проблему: я хочу сохранить элементы списка list1, который принадлежит list2.Так что я могу сделать что-то вроде этого: 

filtered_list = [w for w in list1 if w in list2]

Мне нужно повторить эту же процедуру для разных примеров list1 (около 20000 разных примеров) и «постоянного» (замороженного) list2.

Как я могу ускорить процесс?

Мне также известны следующие свойства:

1) list1 содержит повторяющиеся элементы, и он не отсортирован и имеет около 10000(десять тысяч) элементов.

2) list2 - это гигантский отсортированный список (около 200000 - двести тысяч) записей в Python), и каждый элемент уникален.

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

Кроме того, я не возражаю, если Filter_list имеет такой же порядок элементов списка list1.Так что, возможно, я могу проверить только неповторенную версию list1 и после удаления элементов в list1, которые не принадлежат списку 2, я могу вернуть повторяющиеся элементы.

Есть ли быстрый способ сделать это в Python3

1 Ответ

0 голосов
/ 15 февраля 2019

Преобразование list2 в set: 

# do once
set2 = set(list2)

# then every time
filtered_list = [w for w in list1 if w in set2]

x in list2 является последовательным;x in set2 использует тот же механизм, что и словари, что приводит к очень быстрому поиску.

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

filtered_set = set1 & set2

, но с дубликатами вы застряли с итерацией по list1, как указано выше.

(Как вы сказали, вы можете даже увидеть элементы, которые вы должны удалить, используя set1 - set2, нотогда вы все равно застряли бы в цикле для удаления - не должно быть никакой разницы в производительности между хранителями фильтрации и фильтрацией мусора, вам все равно придется перебирать list1, так что это не победит метод выше.)

РЕДАКТИРОВАТЬ в ответ на комментарий: Преобразование list1 в Counter может может (РЕДАКТИРОВАТЬ: или нет; тестирование необходимо!) Ускорить его , если вы можете использоватьобычно это так (т.е. у вас никогда нет списка, вы всегда просто имеете дело с Counter).Но если вам придется предварительно обрабатывать list1 в counter1 каждый раз, когда вы выполняете вышеуказанную операцию, опять же, это не выигрыш - создание Counter снова будет включать цикл.

...