Проверьте, имеют ли списки общие элементы в python

короткий ответ: используйте not set(a).isdisjoint(b), это вообще самый быстрый.

есть четыре распространенных способа проверить, если два списка a и b поделиться какие-либо предметы. Первый вариант-преобразовать оба в наборы и проверить их пересечение, как таковое:

bool(set(a) & set(b))

, потому что наборы хранятся с помощью хэш-таблицы в Python, поиск их O(1) (см. здесь для получения дополнительной информации о сложности операторов в Python). Теоретически, это O(n+m) в среднем n и m объекты в списки a и b. Но 1) он должен сначала создать наборы из списков, которые могут занять не ничтожное количество времени, и 2) он предполагает, что конфликты хэширования редки среди ваших данных.

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

any(i in a for i in b)

это позволяет осуществлять поиск на месте, поэтому новая память не выделяется промежуточные переменные. Он также выручает на первой находке. но in оператор всегда O(n) списки (см. здесь).

другой предложенный вариант-это гибридная итерация по одному из списков, преобразование другого в набор и проверка на членство в этом наборе, например:

a = set(a); any(i in a for i in b)

четвертый подход заключается в использовании isdisjoint() метод (замороженных) наборов (см. здесь), для пример:

not set(a).isdisjoint(b)

если элементы, которые вы ищете, находятся в начале массива (например, он отсортирован), выражение генератора предпочтительно, так как метод пересечения множеств должен выделять новую память для промежуточных переменных:

from timeit import timeit
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000)
26.077727576019242
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000)
0.16220548999262974

вот график времени выполнения для этого примера в функции размера списка:

обратите внимание, что обе оси являются логарифмическими. Это представляет собой лучший случай для выражение генератора. Как видно, то isdisjoint() метод лучше для очень малых размеров списка, в то время как выражение генератора лучше для больших размеров списка.

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

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
13.739536046981812
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
0.08102107048034668

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

вот два анализа с использованием случайных чисел (вместо фальсификации установки в пользу той или иной техники):

высокая вероятность обмена: элементы случайным образом берутся из [1, 2*len(a)]. Низкий шанс обмена: элементы случайным образом берутся из [1, 1000*len(a)].

до сих пор этот анализ предполагал, что оба списка имеют одинаковый размер. В случае двух списков разных размеров, например a гораздо меньше, isdisjoint() всегда быстрее:

убедитесь, что a список меньше, в противном случае производительность снижается. В этом эксперименте a размер списка был установлен постоянный к 5.

в итоге:

• если списки очень малы (not set(a).isdisjoint(b) всегда самый быстрый.
• если элементы в списках отсортированы или имеют регулярную структуру, которую вы можно воспользоваться, генератором выражения any(i in a for i in b) является самым быстрым на больших размерах списка;