Najlepszy sposób na znalezienie przecięcia wielu zestawów?


266

Mam listę zestawów:

setlist = [s1,s2,s3...]

Chcę s1 ∩ s2 ∩ s3 ...

Mogę napisać funkcję, aby to zrobić, wykonując serię par s1.intersection(s2)itp.

Czy istnieje zalecany, lepszy lub wbudowany sposób?

Odpowiedzi:


454

Począwszy od wersji 2.6 języka Python, możesz używać wielu argumentów set.intersection(), na przykład

u = set.intersection(s1, s2, s3)

Jeśli zestawy znajdują się na liście, oznacza to:

u = set.intersection(*setlist)

gdzie *a_listjest rozwinięcie listy

Zauważ, że nieset.intersection jest to metoda statyczna, ale używa ona notacji funkcjonalnej do zastosowania przecięcia pierwszego zestawu z resztą listy. Więc jeśli lista argumentów jest pusta, to się nie powiedzie.


65

Począwszy od wersji 2.6, set.intersectionprzyjmuje dowolnie wiele iteracji.

>>> s1 = set([1, 2, 3])
>>> s2 = set([2, 3, 4])
>>> s3 = set([2, 4, 6])
>>> s1 & s2 & s3
set([2])
>>> s1.intersection(s2, s3)
set([2])
>>> sets = [s1, s2, s3]
>>> set.intersection(*sets)
set([2])

24

Najwyraźniej set.intersectionjest to, czego chcesz tutaj, ale jeśli kiedykolwiek potrzebujesz uogólnienia „weź sumę wszystkich tych”, „weź produkt wszystkich tych”, „weź xor wszystkich tych”, to czego szukasz, to reducefunkcjonować:

from operator import and_
from functools import reduce
print(reduce(and_, [{1,2,3},{2,3,4},{3,4,5}])) # = {3}

lub

print(reduce((lambda x,y: x&y), [{1,2,3},{2,3,4},{3,4,5}])) # = {3}

12

Jeśli nie masz języka Python 2.6 lub nowszego, alternatywą jest napisanie wyraźnej pętli for:

def set_list_intersection(set_list):
  if not set_list:
    return set()
  result = set_list[0]
  for s in set_list[1:]:
    result &= s
  return result

set_list = [set([1, 2]), set([1, 3]), set([1, 4])]
print set_list_intersection(set_list)
# Output: set([1])

Możesz także użyć reduce:

set_list = [set([1, 2]), set([1, 3]), set([1, 4])]
print reduce(lambda s1, s2: s1 & s2, set_list)
# Output: set([1])

Jednak wielu programistów Python nie lubi tego, w tym sam Guido :

Około 12 lat temu Python nabył lambda, redukcję (), filtr () i mapę () dzięki uprzejmości (chyba) hakera Lisp, który tęsknił za nimi i przesłał działające poprawki. Ale pomimo wartości PR uważam, że te funkcje należy wyciąć z Python 3000.

Więc teraz zmniejsz (). Jest to właściwie ten, którego zawsze nienawidziłem najbardziej, ponieważ oprócz kilku przykładów obejmujących + lub *, prawie za każdym razem, gdy widzę wywołanie redukcyjne () z nietrywialnym argumentem funkcji, muszę chwycić pióro i papier, aby wykreślić, co faktycznie jest wprowadzane do tej funkcji, zanim zrozumiem, co powinna zrobić funkcja redukująca (). Tak więc, moim zdaniem, zastosowanie funkcji zmniejszania () jest w zasadzie ograniczone do operatorów asocjacyjnych, a we wszystkich innych przypadkach lepiej jest wyraźnie napisać pętlę akumulacji.


8
Zauważ, że Guido twierdzi, że użycie reducejest „ograniczone do operatorów asocjacyjnych”, co ma zastosowanie w tym przypadku. reducebardzo często trudno to rozgryźć, ale &nie jest tak źle.
Mike Graham


Sprawdź python.org/doc/essays/list2str, aby uzyskać przydatne optymalizacje obejmujące redukcję. Zasadniczo można go całkiem dobrze używać do budowania list, zestawów, ciągów znaków itp. Warto również zajrzeć na github.com/EntilZha/PyFunctional
Andreas

Pamiętaj, że możesz zoptymalizować, przerywając pętlę, gdy resultjest pusta.
bfontaine

1

Oto oferuję ogólną funkcję do przecinania wielu zestawów, próbując skorzystać z najlepszej dostępnej metody:

def multiple_set_intersection(*sets):
    """Return multiple set intersection."""
    try:
        return set.intersection(*sets)
    except TypeError: # this is Python < 2.6 or no arguments
        pass

    try: a_set= sets[0]
    except IndexError: # no arguments
        return set() # return empty set

    return reduce(a_set.intersection, sets[1:])

Guido może nie lubić reduce, ale lubię to :)


Powinieneś sprawdzić długość setszamiast próbować uzyskać dostęp sets[0]i złapać IndexError.
bfontaine

To nie jest zwykły czek; a_setjest używany przy ostatnim zwrocie.
tzot

Nie można zrobić return reduce(sets[0], sets[1:]) if sets else set()?
bfontaine

Ha tak, dziękuję. Kod powinien ulec zmianie, ponieważ można polegać na try/, exceptjeśli możesz. Jest to zapach kodu, jest nieefektywny i może ukrywać inne problemy.
bfontaine

0

Jean-François Fabre set.intesection (* list_of_sets) odpowiedź jest zdecydowanie najbardziej pyhonickim i słusznie jest odpowiedzią zaakceptowaną.

W przypadku tych, którzy chcą użyć funkcji zmniejsz, będą również działać następujące czynności:

reduce(set.intersection, list_of_sets)

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.