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

132

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

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
   ....: 
fmark
источник
Единственная оптимизация, о которой я могу думать, - это отказ, len(...) > 0потому что bool(set([]))дает False. И, конечно, если вы сохраните свои списки в виде наборов, вы сэкономите накладные расходы на создание наборов.
msw
Релевантно: stackoverflow.com/a/44786707/1959808
Иоаннис Филиппидис
1
Обратите внимание, что вы не можете отличить Trueот 1и Falseот 0. not set([1]).isdisjoint([True])получает True, то же самое с другими решениями.
Димали

Ответы:

315

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

Soravux
источник
8
Вот некоторые полезные данные, которые показывают, что анализ большого числа - это еще не все и не все рассуждения о времени выполнения.
Steve Allison
как насчет худшего сценария? 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 итерациями.
RobM
2
Спасибо @RobM за информацию. Я обновил свой ответ, чтобы отразить это и учесть другие методы, предложенные в этой ветке.
Soravux
Это должно быть, not set(a).isdisjoint(b)чтобы проверить, разделяют ли два списка один член. set(a).isdisjoint(b)возвращается, Trueесли два списка не имеют общего члена. Ответ надо редактировать?
Guillochon
1
Спасибо за внимание, @Guillochon, это исправлено.
Soravux
25
def lists_overlap3(a, b):
    return bool(set(a) & set(b))

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

Джон Мачин
источник
5
Это наихудший случай O (n + m). Однако недостатком является то, что он создает новый набор и не срабатывает при раннем обнаружении общего элемента.
Мэтью Флашен,
1
Мне любопытно, почему это так O(n + m). Я предполагаю, что наборы реализуются с использованием хеш-таблиц, и поэтому inоператор может работать O(1)вовремя (за исключением вырожденных случаев). Это верно? Если это так, учитывая, что хеш-таблицы имеют худшую производительность поиска O(n), означает ли это, что в отличном от худшего случая она будет иметь O(n * m)производительность?
fmark
1
@fmark: Теоретически вы правы. Практически никому нет дела; прочтите комментарии в Objects / dictobject.c в источнике CPython (наборы - это просто dicts только с ключами, без значений) и посмотрите, сможете ли вы сгенерировать список ключей, которые вызовут производительность поиска O (n).
John Machin
Хорошо, спасибо за пояснение, мне было интересно, не творится ли какое-то волшебство :). Хотя я согласен с тем, что мне практически не нужно заботиться, создать список ключей, которые будут вызывать O(n)производительность поиска , - тривиальная задача ;) см. Pastebin.com/Kn3kAW7u Только для lafs.
fmark
2
Да, я знаю. Кроме того, я только что прочитал источник, на который вы мне указали, который документирует еще больше волшебства в случае неслучайных хэш-функций (таких как встроенная). Я предположил, что это требует случайности, такой как Java, что приводит к чудовищам, подобным этому stackoverflow.com/questions/2634690/… . Мне нужно постоянно напоминать себе, что Python - это не Java (слава богу!).
fmark
10
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__в качестве функции сопоставления. Я не знаю, насколько это влияет на производительность. Это все равно будет короткое замыкание.

Мэтью Флашен
источник
1
Все петли в пересечении находятся в коде C; в вашем подходе есть один цикл, который включает код Python. Большой неизвестный заключается в том, является ли пустой перекресток вероятным или маловероятным.
John Machin
2
Вы также можете использовать, any(itertools.imap(sb.__contains__, a))который должен быть еще быстрее, поскольку он позволяет избежать использования лямбда-функции.
Дэйв Кирби
Спасибо, @Dave. :) Я согласен, что удаление лямбды - это победа.
Matthew Flaschen
4

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

any([item in a for item in b])
Ioachim
источник
6
Вы могли бы, но время - O (n * m), тогда как время для подхода к заданному пересечению - O (n + m). Вы также можете сделать это БЕЗ понимания списка (потерять []), и он будет работать быстрее и использовать меньше памяти, но время все равно будет O (n * m).
John Machin
1
Хотя ваш большой анализ O верен, я подозреваю, что для малых значений n и m время, необходимое для построения базовых хэш-таблиц, будет иметь значение. Big O игнорирует время, необходимое для вычисления хэшей.
Энтони Коньерс,
2
Построение «хеш-таблицы» амортизируется O (n).
John Machin
1
Я понимаю, но постоянная, которую вы выбрасываете, довольно большая. Это не имеет значения для больших значений n, но имеет значение для малых.
Энтони Конайерс,
3

В python 2.6 или новее вы можете:

return not frozenset(a).isdisjoint(frozenset(b))
хулиган
источник
1
Кажется, что в качестве первого аргумента не нужно указывать набор или заморозку. Я пробовал со строкой, и она сработала (то есть: подойдет любая итерация).
Актау,
2

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

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

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

return any(i in b for i in a)
Энтони Коньерс
источник
1
Усиление комментария Лжи Райана: даст неправильный результат для любого элемента x, который находится на пересечении, где bool(x)False. В примере Ли Райана x равно 0. Единственное исправление - это то, any(True for i in a if i in b)что лучше написано, как уже было показано any(i in b for i in a).
Джон Мачин,
1
Исправление: даст неверный результат, если все элементы xна пересечении такие, какие bool(x)есть False.
Джон Мачин
1

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

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

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

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

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

binoche9
источник
1
Использование 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
Актау
1

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

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

domoarigato
источник
Если первое значение перекрывается, он все равно преобразует весь список в набор, независимо от его размера.
Питер Вуд
1

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

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

Объяснение:

map(lambda x: x in a, b)

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

CS01
источник