Эффективность пересечения списка Python: генератор или фильтр()?

Я хотел бы пересечь два списка в Python (2.7). Мне нужно, чтобы результат был повторяемым:

list1 = [1,2,3,4]
list2 = [3,4,5,6]
result = (3,4) # any kind of iterable

Предоставление полной итерации будет выполнено в первую очередь после пересечения, что из следующего более эффективно?

Использование генератора:

result = (x for x in list1 if x in list2)

Использование фильтра():

result = filter(lambda x: x in list2, list1)

Другие предложения?

Заранее спасибо,
Амнон


python python-2.7 list intersect intersection
person Amnon Grossman    schedule 16.06.2011    source источник

Ответы (4)


arrow_upward
24
arrow_downward

Ни то, ни другое. Лучше всего использовать наборы.

list1 = [1,2,3,4]
list2 = [3,4,5,6]
result = set(list1).intersection(list2)

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

person Daniel Roseman    schedule 16.06.2011
comment
интересно, set(list1).intersection(list2) быстрее, чем set(list1) & set(list2), я думаю, это потому, что создание двух наборов дороже, чем загрузка и вызов .intersection() хм.. - person mouad; 16.06.2011
comment
@mouad На моей машине set(list1) & set(list2) работает быстрее, чем .intersection(). Но разница не очень существенная. - person pemistahl; 16.02.2013
comment
это требует сортировки списков? - person Youda008; 15.11.2016
comment
@ Youda008 Списки не нужно сортировать. Наборы реализуются путем хэширования, поэтому поиск выполняется за амортизированное время O(1) независимо от местоположения в исходном списке. - person musicman523; 08.07.2017

arrow_upward
8
arrow_downward

Сложность вашего решения равна O(m*n), где m и n — соответствующие длины двух списков. Вы можете повысить сложность до O(m+n), используя набор для одного из списков:

s = set(list1)
result = [x for x in list2 if x in s]

В случаях, когда скорость важнее удобочитаемости (то есть почти никогда), вы также можете использовать

result = filter(set(a).__contains__, b)

что примерно на 20 процентов быстрее, чем другие решения на моей машине.

person Sven Marnach    schedule 16.06.2011

arrow_upward
4
arrow_downward

Я попытался сравнить скорость 3 методов пересечения списков:

import random

a = [random.randint(0, 1000) for _ in range(1000)]
b = [random.randint(0, 1000) for _ in range(1000)]

Решение 1: понимание списка

Прошедшее время: 8,95265507698059

import time
start = time.time()
for _ in range(1000):
    result = [x for x in a if x in b]
elapse = time.time() - start
print(elapse)

Решение 2: установить

Прошедшее время: 0,09089064598083496

start = time.time()
for _ in range(1000):
    result = set.intersection(set(a), set(b))
elapse = time.time() - start
print(elapse)

Решение 3: numpy.intersect1d

Прошедшее время: 0,323300838470459

start = time.time()
for _ in range(1000):
    result = np.intersect1d(a, b)
elapse = time.time() - start
print(elapse)

Вывод

Я думаю, что использование set.intersection - самый быстрый способ.

person Xin Wang    schedule 17.11.2019

arrow_upward
1
arrow_downward

для списков наиболее эффективным способом является использование:

result = set(list1).intersection(list2)

как уже упоминалось, но для массивов numpy функция intersection1d более эффективна:

import numpy as np
result = np.intersection1d(list1, list2)

Особенно, когда вы знаете, что в списках нет повторяющихся значений, вы можете использовать его как:

result = np.intersection1d(list1, list2, assume_unique=True)
person ses    schedule 14.07.2017