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

Ответ 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 элементов), 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() является наилучшим подходом, поскольку выражение генератора займет гораздо больше времени, поскольку оно очень неэффективно, когда ни один элемент не разделяется.

Ответ 2

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

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

Ответ 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

EDIT: Еще одна вариация (благодаря Дэйву Кирби):

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

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

Ответ 4

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

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

Ответ 5

В python 2.6 или новее вы можете сделать:

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

Ответ 6

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

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

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

return any(i in b for i in a)

Ответ 7

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

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

>>> 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

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

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

Ответ 8

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

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

Ответ 9

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

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

Объяснение:

map(lambda x: x in a, b)

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