Проверьте, разделяют ли списки какие-либо элементы в python

Question

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

In [78]: a = [1, 2, 3, 4, 5]

In [79]: b = [8, 7, 6]

In [80]: c = [8, 7, 6, 5]

In [81]: def lists_overlap(a, b):
   ....:     for i in a:
   ....:         if i in b:
   ....:             return True
   ....:     return False
   ....: 

In [82]: lists_overlap(a, b)
Out[82]: False

In [83]: lists_overlap(a, c)
Out[83]: True

In [84]: def lists_overlap2(a, b):
   ....:     return len(set(a).intersection(set(b))) > 0
   ....: 

Answer 1

Краткий ответ : используйте 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.

В итоге:

• Если списки очень малы (<10 элементов), <code>not set(a).isdisjoint(b) всегда самый быстрый.
• Если элементы в списках отсортированы или имеют регулярную структуру, которой вы можете воспользоваться, выражение генератора any(i in a for i in b) является самым быстрым в больших размерах списка;
• Проверьте пересечение множества с помощью not set(a).isdisjoint(b), которое всегда быстрее, чем bool(set(a) & set(b)).
• Гибрид "перебирает список, проверка на множестве" a = set(a); any(i in a for i in b), как правило, медленнее, чем другие методы.
• Генераторное выражение и гибрид намного медленнее, чем два других подхода, когда дело доходит до списков без совместного использования элементов.

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

Answer 2

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

Примечание: приведенное выше предполагает, что вы хотите логическое значение в качестве ответа.Если все, что вам нужно, это выражение для использования в операторе if, просто используйте if set(a) & set(b):

Answer 3

def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

Это асимптотически оптимально (наихудший случай O (n + m)) и может быть лучше, чем подход пересечения из-за короткого замыкания any.

например:.

lists_overlap([3,4,5], [1,2,3])

вернет True, как только доберется до 3 in sb

РЕДАКТИРОВАТЬ: Еще один вариант (с благодарностью Дэйва Кирби):

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

Это основано на итераторе imap, который реализован на C, а не на генераторе. Он также использует sb.__contains__ в качестве функции отображения. Я не знаю, насколько это влияет на производительность. Это все еще будет короткое замыкание.

Answer 4

Вы также можете использовать any с пониманием списка:

any([item in a for item in b])

Answer 5

В Python 2.6 или более поздней версии вы можете сделать:

return not frozenset(a).isdisjoint(frozenset(b))

Answer 6

Вы можете использовать выражение любой встроенной функции / генератора:

def list_overlap(a,b): 
     return any(i for i in a if i in b)

Как указали Джон и Ли, это дает неверные результаты, когда для каждого i, совместно используемого двумя списками, bool (i) == ЛожьДолжно быть:

return any(i in b for i in a)

Answer 7

Я добавлю еще один с функциональным стилем программирования:

any(map(lambda x: x in a, b))

Объяснение:

map(lambda x: x in a, b)

возвращает список логических значений, где элементыb находятся в a.Этот список затем передается в any, который просто возвращает True, если какие-либо элементы True.

Answer 8

Если вам все равно, каким может быть перекрывающийся элемент, вы можете просто проверить len объединенного списка и списки, объединенные в набор. Если есть перекрывающиеся элементы, набор будет короче:

len(set(a+b+c))==len(a+b+c) возвращает True, если нет перекрытия.

Answer 9

Этот вопрос довольно старый, но я заметил, что в то время как люди спорили наборы против списков, никто не думал об их использовании вместе. Следуя примеру Соравукса,

Худший случай для списков:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
100.91506409645081
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
19.746716022491455
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
0.092626094818115234

И лучший вариант для списков:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=list(range(10000))", number=100000)
154.69790101051331
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000)
0.082653045654296875
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000)
0.08434605598449707

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

Таким образом, мой вывод таков: перебирает список и проверяет, есть ли он в наборе .