Быстрый способ найти количество элементов в пересечении списков (Python)

Question

Быстрый способ найти количество элементов в пересечении списков (Python)

Есть ли более быстрый способ вычислить это значение в Python:

len([x for x in my_list if x in other_list])

Я попытался использовать наборы, так как элементы списков уникальны, но я не заметил никакой разницы.

len(set(my_list).intersection(set(other_list)))

Я работаю с большими списками, поэтому даже малейшее улучшение считается.
Спасибо

663 5

python optimization

5 ответов:

Comments

Ничего не найдено.

Jon Clements · Accepted Answer · 2015-03-23 02:41:01

Простой способ-найти список наименьшей длины... чем использовать это с set.intersection..., например:
a = range(100)
b = range(50)

fst, snd = (a, b) if len(a) < len(b) else (b, a)
len(set(fst).intersection(snd))

CoryKramer · Accepted Answer · 2015-03-23 01:47:24

Я думаю, что такое выражение генератора будет быстрым
sum(1 for i in my_list if i in other_list)
В противном случае пересечение set происходит примерно с той же скоростью, что и пересечение
len(set(my_list).intersection(other_list))

mhawke · Accepted Answer · 2015-03-23 02:28:47

Из https://wiki.python.org/moin/TimeComplexity , пересечение множества для двух множеств s и t имеет временную сложность:

Среднее-O (min (len (s), len (t))

Худший - O(len (s) * len (t))

len([x for x in my_list if x in other_list]) имеет сложность O (n^2), которая эквивалентна наихудшему случаю для set.intersection().

Если вы используете set.intersection(), вам нужно сначала преобразовать один из списков в набор:

Так что len(set(my_list).intersection(other_list)) должно в среднем будет быстрее, чем вложенный список понимание.

Saksham Varma · Accepted Answer · 2015-03-23 02:51:11

Можно попробовать использовать функцию filter. Поскольку вы упомянули, что работаете с огромными списками, ifilterмодуля itertools будет хорошим вариантом:
from itertools import ifilter
my_set = set(range(100))
other_set = set(range(50))
for item in ifilter(lambda x: x in other_set, my_set):
    print item

JuniorCompressor · Accepted Answer · 2015-03-23 22:59:10

Идея состоит в том, чтобы сначала отсортировать два списка, а затем пересечь их, как мы хотим объединить их, чтобы найти элементы в первом списке, принадлежащие также второму списку. Таким образом, мы имеем алгоритм O(n logn).
def mycount(l, m):
    l.sort()
    m.sort()
    i, j, counter = 0, 0, 0
    while i < len(l) and j < len(m):
        if l[i] == m[j]:
            counter += 1
            i += 1
        elif l[i] < m[j]:
            i += 1
        else:
            j += 1
    return counter
Из локальных тестов это в 100 раз быстрее, чем len([x for x in a if x in b]) при работе со списками элементов 10000.

Редактировать:

Учитывая, что элементы списка уникальны, общие элементы будут иметь частоту два в объединении двух списков. Также они будем вместе, когда разберемся с этим союзом. Таким образом, справедливо и следующее:
def mycount(l, m):
    s = sorted(l + m)
    return sum(s[i] == s[i + 1] for i in xrange(len(s) - 1))
Аналогично, мы можем использовать счетчик:
from collections import Counter
def mycount(l, m):
    c = Counter(l)
    c.update(m)
    return sum(v == 2 for v in c.itervalues())