Я хочу проверить, присутствует ли какой-либо из элементов одного списка в другом. Я могу сделать это просто с помощью приведенного ниже кода, но подозреваю, что для этого может существовать функция библиотеки. Если нет, есть ли более питонический метод достижения того же результата.
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
....:
list
python
intersection
fmark
источник
источник
len(...) > 0
потому чтоbool(set([]))
дает False. И, конечно, если вы сохраните свои списки в виде наборов, вы сэкономите накладные расходы на создание наборов.True
от1
иFalse
от0
.not set([1]).isdisjoint([True])
получаетTrue
, то же самое с другими решениями.Ответы:
Короткий ответ : пользуйтесь
not set(a).isdisjoint(b)
, он вообще самый быстрый.Есть четыре распространенных способа проверить наличие двух списков
a
иb
поделиться какими-либо элементами. Первый вариант - преобразовать оба в множества и проверить их пересечение как таковое:Поскольку наборы хранятся с использованием хэш-таблицы в Python, поиск по ним осуществляется
O(1)
(см. Здесь для получения дополнительной информации о сложности операторов в Python). Теоретически, этоO(n+m)
в среднемn
иm
объекты в спискахa
иb
. Но 1) он должен сначала создать наборы из списков, что может занять немалое количество времени, и 2) он предполагает, что коллизии хеширования среди ваших данных редки.Второй способ сделать это - использовать выражение-генератор, выполняющее итерацию по спискам, например:
Это позволяет выполнять поиск на месте, поэтому для промежуточных переменных не выделяется новая память. Он также выручает при первой находке. Но
in
оператор всегдаO(n)
в списках (см. Здесь ).Другой предлагаемый вариант - это гибрид для перебора одного из списков, преобразования другого в набор и проверки членства в этом наборе, например:
Четвертый подход - воспользоваться преимуществом
isdisjoint()
метода (замороженных) множеств (см. Здесь ), например:Если элементы, которые вы ищете, находятся рядом с началом массива (например, он отсортирован), выражение генератора предпочтительнее, так как метод пересечения множеств должен выделить новую память для промежуточных переменных:
Вот график времени выполнения этого примера в зависимости от размера списка:
Обратите внимание, что обе оси логарифмические. Это лучший случай для выражения генератора. Как видно, этот
isdisjoint()
метод лучше подходит для списков очень малых размеров, тогда как выражение генератора лучше для списков большего размера.С другой стороны, поскольку поиск начинается с начала для гибридного выражения и выражения генератора, если общий элемент систематически находится в конце массива (или оба списка не имеют общих значений), то подходы несвязанного и установленного пересечения будут намного быстрее, чем выражение генератора и гибридный подход.
Интересно отметить, что выражение генератора работает медленнее для списков большего размера. Это только для 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)
будет самым быстрым для списков больших размеров;not set(a).isdisjoint(b)
, которое всегда быстрее, чемbool(set(a) & set(b))
.a = set(a); any(i in a for i in b)
обычно медленнее, чем другие методы.В большинстве случаев использование этого
isdisjoint()
метода является лучшим подходом, поскольку выражение генератора будет выполняться намного дольше, так как это очень неэффективно, когда никакие элементы не являются общими.источник
any
завершается при первом значении, отличном от False. Используя список, в котором единственное совпадающее значение находится в конце, мы получаем следующее: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 итерациями.not set(a).isdisjoint(b)
чтобы проверить, разделяют ли два списка один член.set(a).isdisjoint(b)
возвращается,True
если два списка не имеют общего члена. Ответ надо редактировать?Примечание: приведенное выше предполагает, что в качестве ответа вы хотите использовать логическое значение. Если все, что вам нужно, это выражение для использования в
if
инструкции, просто используйтеif set(a) & set(b):
источник
O(n + m)
. Я предполагаю, что наборы реализуются с использованием хеш-таблиц, и поэтомуin
оператор может работатьO(1)
вовремя (за исключением вырожденных случаев). Это верно? Если это так, учитывая, что хеш-таблицы имеют худшую производительность поискаO(n)
, означает ли это, что в отличном от худшего случая она будет иметьO(n * m)
производительность?O(n)
производительность поиска , - тривиальная задача ;) см. Pastebin.com/Kn3kAW7u Только для lafs.Это асимптотически оптимально (наихудший случай O (n + m)) и может быть лучше, чем подход пересечения из-за
any
короткого замыкания.Например:
вернет True, как только доберется до
3 in sb
РЕДАКТИРОВАТЬ: Еще один вариант (с благодарностью Дэйву Кирби):
Это зависит от
imap
итератора, который реализован на C, а не от генератора. Он также используетсяsb.__contains__
в качестве функции сопоставления. Я не знаю, насколько это влияет на производительность. Это все равно будет короткое замыкание.источник
any(itertools.imap(sb.__contains__, a))
который должен быть еще быстрее, поскольку он позволяет избежать использования лямбда-функции.Вы также можете использовать
any
с пониманием списка:источник
[]
), и он будет работать быстрее и использовать меньше памяти, но время все равно будет O (n * m).В python 2.6 или новее вы можете:
источник
Вы можете использовать любое встроенное выражение генератора функции / wa:
Как указали Джон и Ли, это дает неверные результаты, когда для каждого i, совместно используемого двумя списками, bool (i) == False. Так должно быть:
источник
bool(x)
False. В примере Ли Райана x равно 0. Единственное исправление - это то,any(True for i in a if i in b)
что лучше написано, как уже было показаноany(i in b for i in a)
.x
на пересечении такие, какиеbool(x)
естьFalse
.Этот вопрос довольно старый, но я заметил, что, пока люди спорили о наборах и списках, никто не подумал использовать их вместе. Следуя примеру Соравукса,
Худший случай для списков:
И лучший вариант для списков:
Таким образом, даже быстрее, чем итерация по двум спискам, выполняется итерация по списку, чтобы увидеть, входит ли он в набор, что имеет смысл, поскольку проверка того, находится ли число в наборе, занимает постоянное время, а проверка путем итерации по списку занимает время, пропорциональное длине список.
Таким образом, я пришел к выводу, что нужно перебирать список и проверять, входит ли он в набор .
источник
isdisjoint()
метода на (замороженном) наборе, указанном @Toughy, еще лучше: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.00913715362548828если вам все равно, какой может быть перекрывающийся элемент, вы можете просто проверить
len
объединенный список и списки, объединенные как набор. Если есть перекрывающиеся элементы, набор будет короче:len(set(a+b+c))==len(a+b+c)
возвращает True, если нет перекрытия.источник
Я добавлю еще один с функциональным стилем программирования:
Объяснение:
возвращает список логических значений, в которых
b
находятся элементыa
. Затем этот список передается вany
, который просто возвращает,True
если есть какие-либо элементыTrue
.источник