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

Question

Я хотел бы пересечь два списка в 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)

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

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

Answer 1

Ни один из них. Лучший способ - использовать наборы.

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

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

Answer 2

Ваше решение имеет сложность 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 процентов быстрее, чем другие решения на моей машине.

Answer 3

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

result = set(list1).intersection(list2)

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

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

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

result = np.intersection1d(list1, list2, assume_unique=True)