Sprawdź, czy wszystkie elementy na liście są identyczne

389

Potrzebuję następującej funkcji:

Dane wejściowe : alist

Wyjście :

  • True jeżeli wszystkie elementy na liście danych wejściowych oceniają się jako równe za pomocą standardowego operatora równości;
  • False Inaczej.

Wydajność : oczywiście wolę nie ponosić niepotrzebnego obciążenia.

Myślę, że najlepiej byłoby:

  • iteruj po liście
  • porównaj sąsiednie elementy
  • i ANDwszystkie wynikowe wartości boolowskie

Ale nie jestem pewien, jaki jest najbardziej Pythoniczny sposób na zrobienie tego.


Brak funkcji zwarcia boli tylko na długim wejściu (ponad ~ 50 elementów), które mają nierówne elementy na początku. Jeśli zdarza się to wystarczająco często (jak często zależy od długości list), wymagane jest zwarcie. Najlepszym algorytmem zwarciowym wydaje się być @KennyTM checkEqual1. Płacą jednak za to znaczne koszty:

  • do 20x w wydajności prawie identyczne listy
  • do 2,5x wydajności na krótkich listach

Jeśli długie sygnały wejściowe z wczesnymi nierównymi elementami nie występują (lub występują dość rzadko), zwarcie nie jest wymagane. Zdecydowanie najszybsze jest rozwiązanie @Ivo van der Wijk.

max
źródło
3
Równa jak w a == blub identyczna jak w a is b?
kennytm
1
Czy rozwiązanie powinno obsługiwać puste listy? Jeśli tak, co należy zwrócić?
Doug
1
Równa jak w a == b. Powinien obsługiwać pustą listę i zwracać wartość True.
maks.
2
Chociaż wiem, że jest on wolniejszy niż niektóre inne rekomendacje, jestem zaskoczony, functools.reduce(operator.eq, a)że nie został zasugerowany.
user2846495

Odpowiedzi:

420

Ogólna metoda:

def checkEqual1(iterator):
    iterator = iter(iterator)
    try:
        first = next(iterator)
    except StopIteration:
        return True
    return all(first == rest for rest in iterator)

Jednowarstwowy:

def checkEqual2(iterator):
   return len(set(iterator)) <= 1

Również jednowarstwowy:

def checkEqual3(lst):
   return lst[1:] == lst[:-1]

Różnica między 3 wersjami polega na tym, że:

  1. W checkEqual2treści musi być hashable.
  2. checkEqual1i checkEqual2może używać dowolnych iteratorów, ale checkEqual3musi pobierać dane wejściowe sekwencji, zwykle konkretne pojemniki, takie jak lista lub krotka.
  3. checkEqual1 zatrzymuje się, gdy tylko zostanie znaleziona różnica.
  4. Ponieważ checkEqual1zawiera więcej kodu Python, jest mniej wydajny, gdy wiele elementów jest na początku równych.
  5. Ponieważ checkEqual2i checkEqual3zawsze wykonuj operacje kopiowania O (N), potrwają dłużej, jeśli większość danych wejściowych zwróci False.
  6. Dla checkEqual2i checkEqual3trudniej jest dostosować porównanie od a == bdo a is b.

timeit wynik, dla Python 2.7 i (tylko s1, s4, s7, s9 powinny zwracać wartość True)

s1 = [1] * 5000
s2 = [1] * 4999 + [2]
s3 = [2] + [1]*4999
s4 = [set([9])] * 5000
s5 = [set([9])] * 4999 + [set([10])]
s6 = [set([10])] + [set([9])] * 4999
s7 = [1,1]
s8 = [1,2]
s9 = []

dostajemy

      | checkEqual1 | checkEqual2 | checkEqual3  | checkEqualIvo | checkEqual6502 |
|-----|-------------|-------------|--------------|---------------|----------------|
| s1  | 1.19   msec | 348    usec | 183     usec | 51.6    usec  | 121     usec   |
| s2  | 1.17   msec | 376    usec | 185     usec | 50.9    usec  | 118     usec   |
| s3  | 4.17   usec | 348    usec | 120     usec | 264     usec  | 61.3    usec   |
|     |             |             |              |               |                |
| s4  | 1.73   msec |             | 182     usec | 50.5    usec  | 121     usec   |
| s5  | 1.71   msec |             | 181     usec | 50.6    usec  | 125     usec   |
| s6  | 4.29   usec |             | 122     usec | 423     usec  | 61.1    usec   |
|     |             |             |              |               |                |
| s7  | 3.1    usec | 1.4    usec | 1.24    usec | 0.932   usec  | 1.92    usec   |
| s8  | 4.07   usec | 1.54   usec | 1.28    usec | 0.997   usec  | 1.79    usec   |
| s9  | 5.91   usec | 1.25   usec | 0.749   usec | 0.407   usec  | 0.386   usec   |

Uwaga:

# http://stackoverflow.com/q/3844948/
def checkEqualIvo(lst):
    return not lst or lst.count(lst[0]) == len(lst)

# http://stackoverflow.com/q/3844931/
def checkEqual6502(lst):
    return not lst or [lst[0]]*len(lst) == lst
kennytm
źródło
1
Dziękuję, to jest naprawdę pomocne wyjaśnienie alternatyw. Czy możesz dokładnie sprawdzić swoją tabelę wydajności - czy to wszystko w ms, a liczby są w prawidłowych komórkach?
maks.
7
@max: Tak. Zauważ, że 1 ms = 1000 usec.
kennytm
1
Nie zapomnij o analizie zużycia pamięci dla bardzo dużych tablic, natywnego rozwiązania, które optymalizuje połączenia z obj.__eq__czasem lhs is rhsi optymalizacje poza kolejnością, aby umożliwić szybsze sortowanie zwartych list.
Glenn Maynard
3
Ivo van der Wijk ma lepsze rozwiązanie dla sekwencji, które są około 5 razy szybsze niż ustawione i O (1) w pamięci.
aaronasterling
2
Jest też itertoolsprzepis, który dodałem jako odpowiedź. Może warto wrzucić to do swojej macierzy czasu :-).
mgilson,
298

Rozwiązaniem szybszym niż użycie set () działającego na sekwencjach (nie iterowalnych) jest po prostu policzenie pierwszego elementu. Zakłada się, że lista nie jest pusta (ale sprawdzenie tego jest trywialne i sam decydujesz, jaki wynik powinien znaleźć się na pustej liście)

x.count(x[0]) == len(x)

kilka prostych testów:

>>> timeit.timeit('len(set(s1))<=1', 's1=[1]*5000', number=10000)
1.4383411407470703
>>> timeit.timeit('len(set(s1))<=1', 's1=[1]*4999+[2]', number=10000)
1.4765670299530029
>>> timeit.timeit('s1.count(s1[0])==len(s1)', 's1=[1]*5000', number=10000)
0.26274609565734863
>>> timeit.timeit('s1.count(s1[0])==len(s1)', 's1=[1]*4999+[2]', number=10000)
0.25654196739196777
Ivo van der Wijk
źródło
5
OMG, to 6 razy szybsze niż ustawione rozwiązanie! (280 milionów elementów / s w porównaniu z 45 milionami elementów / s na moim laptopie). Dlaczego??? I czy jest jakiś sposób, aby go zmodyfikować, aby powodował zwarcie (chyba nie ...)
maks.
1
Sądzę, że list.count ma wysoce zoptymalizowaną implementację C, a długość listy jest przechowywana wewnętrznie, więc len () jest również tani. Nie ma sposobu na zwarcie liczenia (), ponieważ trzeba naprawdę sprawdzić wszystkie elementy, aby uzyskać prawidłową liczbę.
Ivo van der Wijk
Czy mogę to zmienić na: x.count(next(x)) == len(x)aby działał dla dowolnego kontenera x? Ahh .. nm, właśnie zobaczyłem, że .count jest dostępny tylko dla sekwencji. Dlaczego nie jest zaimplementowany dla innych wbudowanych kontenerów? Czy liczenie w słowniku jest z natury mniej znaczące niż w przypadku listy?
maks.
4
Iterator może nie mieć długości. Np. Może być nieskończony lub po prostu generowany dynamicznie. Można go znaleźć tylko przez przekonwertowanie go na listę, która odbiera większość zalet iteratorów
Ivo van der Wijk,
Przepraszam, miałem na myśli to, dlaczego countnie jest zaimplementowane lendla iteratorów , a nie dlaczego nie jest dostępne dla iteratorów. Odpowiedź jest prawdopodobnie taka, że ​​to tylko przeoczenie. Jest to jednak dla nas nieistotne, ponieważ domyślna .count()sekwencja jest bardzo wolna (czysty python). Powodem, dla którego twoje rozwiązanie jest tak szybkie, jest to, że polega ono na C-implementacji countdostarczonej przez list. Tak więc przypuszczam, że cokolwiek by się powtórzyło zaimplementowanie countmetody w C, skorzysta z twojego podejścia.
maks.
163

Najprostszy i najbardziej elegancki sposób wygląda następująco:

all(x==myList[0] for x in myList)

(Tak, to działa nawet z pustą listą! To dlatego, że jest to jeden z niewielu przypadków, w których python ma leniwą semantykę.)

Jeśli chodzi o wydajność, to zawiedzie jak najwcześniej, więc jest asymptotycznie optymalna.

ninjagecko
źródło
To działa, ale jest nieco (1,5x) wolniejsze niż @KennyTM checkEqual1. Nie jestem pewien dlaczego.
maksymalnie
4
max: Prawdopodobnie dlatego, że nie zadałem sobie trudu optymalizacji first=myList[0] all(x==first for x in myList), być może
ninjagecko,
Myślę, że moja lista [0] jest oceniana przy każdej iteracji. >>> timeit.timeit ('all ([y == x [0] for y in x])', 'x = [1] * 4000', number = 10000) 2.707076672740641 >>> timeit.timeit ('x0 = x [0]; wszystkie ([y == x0 dla y w x]) ',' x = [1] * 4000 ', liczba = 10000) 2.0908854261426484
Matt Liberty
1
Powinienem oczywiście wyjaśnić, że optymalizacja first=myList[0]wyrzuci znak IndexErrorna pustą listę, więc komentatorzy, którzy mówili o tej optymalizacji, o której wspomniałem, będą musieli poradzić sobie z sytuacją skrajną pustej listy. Jednak oryginał jest w porządku ( x==myList[0]jest w porządku, allponieważ nigdy nie jest oceniany, jeśli lista jest pusta).
ninjagecko
1
Jest to wyraźnie właściwa droga do tego. Jeśli chcesz prędkości w każdym przypadku, użyj czegoś takiego jak numpy.
Henry Gomersall
45

Zestaw pracy porównawczej:

len(set(the_list)) == 1

Użycie setusuwa wszystkie zduplikowane elementy.

cbalawat
źródło
26

Możesz przekonwertować listę na zestaw. Zestaw nie może mieć duplikatów. Jeśli więc wszystkie elementy na oryginalnej liście są identyczne, zestaw będzie miał tylko jeden element.

if len(sets.Set(input_list)) == 1
// input_list has all identical elements.
kodaddict
źródło
jest to miłe, ale nie powoduje zwarcia i musisz obliczyć długość wynikowej listy.
aaronasterling
15
dlaczego nie len(set(input_list)) == 1?
Nick Dandoulakis,
2
@codaddict. Oznacza to, że nawet jeśli dwa pierwsze elementy są odrębne, nadal zakończy się całe wyszukiwanie. wykorzystuje także dodatkową przestrzeń O (k), gdzie k jest liczbą odrębnych elementów na liście.
aaronasterling
1
@max. ponieważ budowanie zestawu odbywa się w C i masz złą implementację. Powinieneś to zrobić przynajmniej w wyrażeniu generatora. Zobacz odpowiedź Kenny'egoTM, aby dowiedzieć się, jak to zrobić poprawnie bez użycia zestawu.
aaronasterling
1
sets.Set jest „Przestarzałe od wersji 2.6: Wbudowane typy zestaw / frozenset zastępują ten moduł”. (z docs.python.org/2/library/sets.html )
Moberg
21

Co warte jest, pojawiło się to ostatnio na liście mailingowej python-ideas . Okazuje się, że istnieje już przepis na itertools : 1

def all_equal(iterable):
    "Returns True if all the elements are equal to each other"
    g = groupby(iterable)
    return next(g, True) and not next(g, False)

Podobno działa bardzo ładnie i ma kilka fajnych właściwości.

  1. Zwarcia: przestanie konsumować przedmioty z iteracji, gdy tylko znajdzie pierwszy nierównomierny przedmiot.
  2. Nie wymaga, aby przedmioty były haszowalne.
  3. Jest leniwy i wymaga tylko dodatkowej pamięci O (1) do wykonania kontroli.

1 Innymi słowy, nie mogę się pochwalić za wymyślenie rozwiązania - ani nie mogę się pochwalić za to, że go znalazłem .

mgilson
źródło
3
O wiele szybszy niż najszybsza odpowiedź wymieniona tutaj w najgorszym scenariuszu.
ChaimG
return next(g, f := next(g, g)) == f(z py3.8 oczywiście)
Chris_Rands
17

Oto dwa proste sposoby na zrobienie tego

za pomocą set ()

Podczas konwertowania listy na zestaw usuwane są zduplikowane elementy. Jeśli więc długość przekonwertowanego zestawu wynosi 1, oznacza to, że wszystkie elementy są takie same.

len(set(input_list))==1

Oto przykład

>>> a = ['not', 'the', 'same']
>>> b = ['same', 'same', 'same']
>>> len(set(a))==1  # == 3
False
>>> len(set(b))==1  # == 1
True

using all ()

Spowoduje to porównanie (równoważność) pierwszego elementu listy wejściowej z każdym innym elementem na liście. Jeśli wszystkie są równoważne, prawda zostanie zwrócona, w przeciwnym razie zwróci się fałsz.

all(element==input_list[0] for element in input_list)

Oto przykład

>>> a = [1, 2, 3, 4, 5]
>>> b = [1, 1, 1, 1, 1]
>>> all(number==a[0] for number in a)
False
>>> all(number==b[0] for number in b)
True

PS Jeśli sprawdzasz, czy cała lista jest odpowiednikiem określonej wartości, możesz sprawdzić wartość w parametrze lista_wejściowa [0].

Christopher Nuccio
źródło
1
Dla osób zainteresowanych środowiskiem wykonawczym wykonanie len(set(a))na liście 10 000 000 elementów zajęło 0,09 s, podczas gdy wykonanie allzajęło 0,9 s (10 razy dłużej).
Elliptica,
2
Podoba mi się również ta odpowiedź ze względu na jej pythonową prostotę, oprócz oceny wydajności wspomnianej przez @Elliptica
NickBraunagel,
11

To kolejna opcja, szybsza niż w len(set(x))==1przypadku długich list (wykorzystuje zwarcie)

def constantList(x):
    return x and [x[0]]*len(x) == x
6502
źródło
Jest 3 razy wolniejszy niż ustawione rozwiązanie na moim komputerze, ignorując zwarcie. Jeśli więc nierówny element zostanie znaleziony średnio w pierwszej trzeciej części listy, jest on średnio szybszy.
maks.
9

Jest to prosty sposób:

result = mylist and all(mylist[0] == elem for elem in mylist)

Jest to nieco bardziej skomplikowane, powoduje narzut wywołania funkcji, ale semantyka jest wyraźniej określona:

def all_identical(seq):
    if not seq:
        # empty list is False.
        return False
    first = seq[0]
    return all(first == elem for elem in seq)
Jerub
źródło
Możesz uniknąć zbędnego porównania, używając for elem in mylist[1:]. Wątpię jednak, że znacznie poprawia prędkość, ponieważ elem[0] is elem[0]tak sądzę , że tłumacz może prawdopodobnie dokonać tego porównania bardzo szybko.
Brendan
5

Sprawdź, czy wszystkie elementy są równe pierwszemu.

np.allclose(array, array[0])

Gusiew Slava
źródło
Potrzebuje modułu strony trzeciej.
Bachsau
4

Wątpię, że jest to „najbardziej Python”, ale coś takiego:

>>> falseList = [1,2,3,4]
>>> trueList = [1, 1, 1]
>>> 
>>> def testList(list):
...   for item in list[1:]:
...     if item != list[0]:
...       return False
...   return True
... 
>>> testList(falseList)
False
>>> testList(trueList)
True

załatwi sprawę.

machineghost
źródło
1
Twoja forpętla może zostać przekształcona w język Pythona if any(item != list[0] for item in list[1:]): return False, z dokładnie taką samą semantyką.
musiphil
4

Jeśli interesuje Cię coś nieco bardziej czytelnego (ale oczywiście nie tak wydajnego), możesz spróbować:

def compare_lists(list1, list2):
    if len(list1) != len(list2): # Weed out unequal length lists.
        return False
    for item in list1:
        if item not in list2:
            return False
    return True

a_list_1 = ['apple', 'orange', 'grape', 'pear']
a_list_2 = ['pear', 'orange', 'grape', 'apple']

b_list_1 = ['apple', 'orange', 'grape', 'pear']
b_list_2 = ['apple', 'orange', 'banana', 'pear']

c_list_1 = ['apple', 'orange', 'grape']
c_list_2 = ['grape', 'orange']

print compare_lists(a_list_1, a_list_2) # Returns True
print compare_lists(b_list_1, b_list_2) # Returns False
print compare_lists(c_list_1, c_list_2) # Returns False
Joshua Burns
źródło
Właściwie próbuję sprawdzić, czy wszystkie elementy na jednej liście są identyczne; nie, jeśli dwie osobne listy są identyczne.
maks.
4

Przekształć listę w zestaw, a następnie znajdź liczbę elementów w zestawie. Jeśli wynikiem jest 1, ma identyczne elementy, a jeśli nie, to elementy na liście nie są identyczne.

list1 = [1,1,1]
len(set(list1)) 
>1

list1 = [1,2,3]
len(set(list1)
>3
DePP
źródło
4

Odnośnie używania reduce()z lambda. Oto działający kod, który moim zdaniem jest o wiele ładniejszy niż niektóre inne odpowiedzi.

reduce(lambda x, y: (x[1]==y, y), [2, 2, 2], (True, 2))

Zwraca krotkę, w której pierwszą wartością jest wartość logiczna, jeśli wszystkie elementy są takie same lub nie.

Marcus Lind
źródło
Jest taki mały błąd w zapisanym kodzie (spróbuj [1, 2, 2]): nie bierze on pod uwagę poprzedniej wartości logicznej. Można to naprawić poprzez wymianę x[1] == yz x[0] and x[1] == y.
schot
3

Mogłabym zrobić:

not any((x[i] != x[i+1] for i in range(0, len(x)-1)))

ponieważ anyprzestaje przeszukiwać iterowalny, gdy tylko znajdzie Truewarunek.

Robert Rossney
źródło
Nie potrzebujesz dodatkowych nawiasów wokół wyrażenia generatora, jeśli jest to jedyny argument.
ninjagecko
tak też all(), dlaczego nie użyć all(x == seq[0] for x in seq)? wygląda bardziej pytonicznie i powinien działać tak samo
Chen A.
2
>>> a = [1, 2, 3, 4, 5, 6]
>>> z = [(a[x], a[x+1]) for x in range(0, len(a)-1)]
>>> z
[(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
# Replacing it with the test
>>> z = [(a[x] == a[x+1]) for x in range(0, len(a)-1)]
>>> z
[False, False, False, False, False]
>>> if False in z : Print "All elements are not equal"
pyfunc
źródło
2
def allTheSame(i):
    j = itertools.groupby(i)
    for k in j: break
    for k in j: return False
    return True

Działa w Pythonie 2.4, który nie ma „wszystkiego”.

itertool
źródło
1
for k in j: breakjest równoważne z next(j). Mógłbyś to zrobić def allTheSame(x): return len(list(itertools.groupby(x))<2), gdybyś nie dbał o wydajność.
ninjagecko
2

Może korzystać z mapy i lambda

lst = [1,1,1,1,1,1,1,1,1]

print all(map(lambda x: x == lst[0], lst[1:]))
SuperNova
źródło
2

Lub użyj diffmetody numpy:

import numpy as np
def allthesame(l):
    return np.all(np.diff(l)==0)

I zadzwonić:

print(allthesame([1,1,1]))

Wynik:

True
U10 do przodu
źródło
Myślę, że not np.any(np.diff(l))może być trochę szybszy.
GZ0
2

Lub użyj metody różniczkowej numpy:

import numpy as np
def allthesame(l):
    return np.unique(l).shape[0]<=1

I zadzwonić:

print(allthesame([1,1,1]))

Wynik:

Prawdziwe

Luis B.
źródło
Ta odpowiedź jest identyczna z odpowiedzią U9-Forward z zeszłego roku.
mhwombat
Dobre oko! Użyłem tej samej struktury / API, ale moja metoda używa np.unique i kształtu. Funkcja U9 używa np.all () i np.diff () - nie używam żadnej z tych funkcji.
Luis B
1

Możesz to zrobić:

reduce(and_, (x==yourList[0] for x in yourList), True)

Dość denerwujące jest to, że Python zmusza do importowania operatorów takich jak operator.and_. Począwszy od python3, musisz także zaimportować functools.reduce.

(Nie powinieneś używać tej metody, ponieważ nie złamie się, jeśli znajdzie nierównomierne wartości, ale będzie nadal sprawdzać całą listę. Została ona tutaj uwzględniona jako odpowiedź na kompletność).

ninjagecko
źródło
To nie spowodowałoby zwarcia. Dlaczego wolisz to niż inne rozwiązanie?
maks.
@max: nie zrobiłbyś, właśnie z tego powodu; Zawarłem to dla kompletności. Prawdopodobnie powinienem go edytować, żeby to wspomnieć, dzięki.
ninjagecko
1
lambda lst: reduce(lambda a,b:(b,b==a[0] and a[1]), lst, (lst[0], True))[1]

Następny spowoduje zwarcie:

all(itertools.imap(lambda i:yourlist[i]==yourlist[i+1], xrange(len(yourlist)-1)))
użytkownik3015260
źródło
Twój pierwszy kod był oczywiście niepoprawny: reduce(lambda a,b:a==b, [2,2,2])daje False... Zredagowałem go, ale w ten sposób już nie jest ładny
Berdario
@berdario W takim razie powinieneś napisać własną odpowiedź, zamiast zmieniać to, co napisał ktoś inny. Jeśli uważasz, że ta odpowiedź była błędna, możesz ją skomentować i / lub głosować.
Gorpik
3
Lepiej naprawić coś złego, niż zostawić to wszystkim, aby go przeczytało, być może pomijając komentarze wyjaśniające, dlaczego to było źle
berdario
3
„Kiedy powinienem edytować posty?” „Za każdym razem, gdy czujesz, że możesz ulepszyć posta i masz na to ochotę. Edycja jest zachęcana!”
berdario
1

Zmień listę na zestaw. Zatem jeśli rozmiar zestawu wynosi tylko 1, muszą być takie same.

if len(set(my_list)) == 1:
Lumo5
źródło
1

Istnieje również czysta opcja rekurencyjna w języku Python:

 def checkEqual(lst):
    if len(lst)==2 :
        return lst[0]==lst[1]
    else:
        return lst[0]==lst[1] and checkEqual(lst[1:])

Jednak z jakiegoś powodu w niektórych przypadkach jest on o dwa rzędy wielkości wolniejszy niż w przypadku innych opcji. Pochodząc z mentalności języka C spodziewałem się, że będzie to szybsze, ale tak nie jest!

Inną wadą jest to, że w Pythonie istnieje limit rekurencji, który w tym przypadku należy dostosować. Na przykład używając tego .

Foad
źródło
0

Możesz użyć, .nunique()aby znaleźć liczbę unikalnych przedmiotów na liście.

def identical_elements(list):
    series = pd.Series(list)
    if series.nunique() == 1: identical = True
    else:  identical = False
    return identical



identical_elements(['a', 'a'])
Out[427]: True

identical_elements(['a', 'b'])
Out[428]: False
Saeed
źródło
0

możesz użyć set. Stworzy zestaw i usunie powtarzające się elementy. Następnie sprawdź, czy nie ma więcej niż 1 element.

if len(set(your_list)) <= 1:
    print('all ements are equal')

Przykład:

>>> len(set([5, 5])) <= 1
True
MHB
źródło