Jak mogę sprawdzić, czy lista ma jedną i tylko jedną prawdziwą wartość?


83

W Pythonie mam listę, która powinna mieć jedną i tylko jedną prawdziwą wartość (to znaczy bool(value) is True). Czy istnieje sprytny sposób, aby to sprawdzić? W tej chwili tylko iteruję listę i ręcznie sprawdzam:

def only1(l)
    true_found = False
    for v in l:
        if v and not true_found:
            true_found=True
        elif v and true_found:
             return False #"Too Many Trues"
    return true_found

Wydaje się to nieeleganckie i niezbyt pytoniczne. Czy jest na to sprytniejszy sposób?


2
Myślę, że twoje rozwiązanie jest całkiem dobre i jest pytoniczne!
wim

1
Common Lisp: (= 1 (count-if #'identity list)).
Kaz

7
sum(lst) == 1
Pål GD

Żeby było jasne: czy chcesz sprawdzić, czy istnieje Truetylko jedna prawdziwa wartość, czy tylko jedna?
Marcin

Odpowiedzi:


44

Najbardziej rozwlekłe rozwiązanie nie zawsze jest najbardziej nieeleganckie. Dlatego dodaję tylko niewielką modyfikację (w celu zaoszczędzenia kilku zbędnych ocen logicznych):

def only1(l):
    true_found = False
    for v in l:
        if v:
            # a True was found!
            if true_found:
                # found too many True's
                return False 
            else:
                # found the first True
                true_found = True
    # found zero or one True value
    return true_found

Oto kilka czasów do porównania:

# file: test.py
from itertools import ifilter, islice

def OP(l):
    true_found = False
    for v in l:
        if v and not true_found:
            true_found=True
        elif v and true_found:
             return False #"Too Many Trues"
    return true_found

def DavidRobinson(l):
    return l.count(True) == 1

def FJ(l):
    return len(list(islice(ifilter(None, l), 2))) == 1

def JonClements(iterable):
    i = iter(iterable)
    return any(i) and not any(i)

def moooeeeep(l):
    true_found = False
    for v in l:
        if v:
            if true_found:
                # found too many True's
                return False 
            else:
                # found the first True
                true_found = True
    # found zero or one True value
    return true_found

Mój wynik:

$ python -mtimeit -s 'import test; l=[True]*100000' 'test.OP(l)' 
1000000 loops, best of 3: 0.523 usec per loop
$ python -mtimeit -s 'import test; l=[True]*100000' 'test.DavidRobinson(l)' 
1000 loops, best of 3: 516 usec per loop
$ python -mtimeit -s 'import test; l=[True]*100000' 'test.FJ(l)' 
100000 loops, best of 3: 2.31 usec per loop
$ python -mtimeit -s 'import test; l=[True]*100000' 'test.JonClements(l)' 
1000000 loops, best of 3: 0.446 usec per loop
$ python -mtimeit -s 'import test; l=[True]*100000' 'test.moooeeeep(l)' 
1000000 loops, best of 3: 0.449 usec per loop

Jak widać, rozwiązanie OP jest znacznie lepsze niż większość innych zamieszczonych tutaj rozwiązań. Zgodnie z oczekiwaniami najlepsze są te z zachowaniem zwarciowym, zwłaszcza to rozwiązanie opublikowane przez Jona Clementsa. Przynajmniej w przypadku dwóch wczesnych Truewartości na długiej liście.

Tutaj to samo dla żadnej Truewartości:

$ python -mtimeit -s 'import test; l=[False]*100000' 'test.OP(l)' 
100 loops, best of 3: 4.26 msec per loop
$ python -mtimeit -s 'import test; l=[False]*100000' 'test.DavidRobinson(l)' 
100 loops, best of 3: 2.09 msec per loop
$ python -mtimeit -s 'import test; l=[False]*100000' 'test.FJ(l)' 
1000 loops, best of 3: 725 usec per loop
$ python -mtimeit -s 'import test; l=[False]*100000' 'test.JonClements(l)' 
1000 loops, best of 3: 617 usec per loop
$ python -mtimeit -s 'import test; l=[False]*100000' 'test.moooeeeep(l)' 
100 loops, best of 3: 1.85 msec per loop

Nie sprawdzałem istotności statystycznej, ale co ciekawe, tym razem podejścia sugerowane przez FJ, a zwłaszcza to Jona Clementsa, ponownie wydają się wyraźnie lepsze.


4
Umm - patrząc na wczesne, prawdziwe czasy - czy nie jest 0.446to najszybsze?
Jon Clements

2
@JonClements dlatego pisałem najwięcej , teraz wyjaśniłem to bardziej. (większość
postów

1
Podejrzewam, że JonClement jest tak szybki, ponieważ większość z nich anyjest zaimplementowana w języku C
Matthew Scouten

1
+1 za twoją pierwszą linię. Wszystkie odpowiedzi sumsą w rzeczywistości gorsze niż prosty i bezpośredni kod PO ..
wim

2
@MarkAmery Dodałem zarówno sekcję o czytelności i elegancji (wprawdzie krótką), jak i o ocenie wydajności. Wydaje mi się, że w kwestii sprytu należy rozważyć oba aspekty. Jak widzę, udzieliłem odpowiedzi, aby odnieść się do obu tych istotnych aspektów. Jeśli uważasz, że ta odpowiedź nie jest przydatna, możesz głosować przeciw.
moooeeeep,

259

Taki, który nie wymaga importu:

def single_true(iterable):
    i = iter(iterable)
    return any(i) and not any(i)

Alternatywnie, być może bardziej czytelna wersja:

def single_true(iterable):
    iterator = iter(iterable)

    # consume from "i" until first true or it's exhausted
    has_true = any(iterator) 

    # carry on consuming until another true value / exhausted
    has_another_true = any(iterator) 

    # True if exactly one true found
    return has_true and not has_another_true

To:

  • Wygląda na to, że ima jakąkolwiek prawdziwą wartość
  • Wciąż patrzy od tego punktu w iterowalne, aby upewnić się, że nie ma innej prawdziwej wartości

34
@MatthewScouten no ... konsumujemy z iterowalnego tutaj ... spróbuj uruchomić kod ...
Jon Clements

12
@MatthewScouten zgodnie z konsumpcją iterowalnej. anybędzie zgodnie z dokumentami zwróci True, gdy tylko zostanie znaleziona wartość inna niż fałszywa. Następnie ponownie szukamy prawdziwej wartości, a jeśli zostanie znaleziona, traktujemy ją jako błąd ... Więc to zadziała dla pustych list, list / innych sekwencji i wszelkich iterowalnych ...
Jon Clements

12
@MathewScouten Efekty uboczne łamią wszystkie twierdzenia! x and not x = Falsejest poprawne tylko wtedy, gdy xjest referencyjnie przezroczyste.
Ben

14
@wim To nie jest szczegół implementacji any()- to udokumentowana cecha funkcji i gwarantowana funkcjonalność dowolnej implementacji, która jest zgodna ze specyfikacją Pythona.
Gareth Latty

17
Każdy, kto uważa, że ​​nie jest to czytelne rozwiązanie, powinien rozważyć to: jest zwięzłe i opiera się tylko na znanych zachowaniach i typowej konstrukcji Pythona. Tylko dlatego, że noob by tego nie zrozumiał, nie czyni go czytelnym. Jest to również doskonały sposób na nauczanie tego, co należy wiedzieć, ponieważ budzi natychmiastową ciekawość u tych, którzy nie widzą, jak to działa.
dansalmo,

49

Zależy to od tego, czy szukasz tylko wartości, Trueczy też szukasz innych wartości, które można by ocenić Truelogicznie (jak 11lub "hello"). Jeśli pierwszy:

def only1(l):
    return l.count(True) == 1

Jeśli ten ostatni:

def only1(l):
    return sum(bool(e) for e in l) == 1

ponieważ spowodowałoby to zliczanie i konwersję w jednej iteracji, bez konieczności tworzenia nowej listy.


2
W Pythonie 3:list(map(bool, l)).count(True)
poke

To tylko znajduje dosłowne True, a nie inne prawdziwe wartości (np .: dodatnie wartości int, a nie puste pojemniki itp.)
Matthew Scouten

6
Wystarczy wskazać OP, że prawdopodobnie nie spowoduje to zwarcia, gdy zostanie znalezionych więcej niż jedna wartość „Prawda”, więc ich kod może zapewnić większą wydajność w pewnych okolicznościach.
NominSim

2
Drugą funkcję można zapisać jako return sum(bool(e) for e in l) == 1. boolpodklasy inti Prawda / Fałsz zachowują się jak 1/0 w zakresie arytmetyki.

1
Unikałbym używania ljako nazwy zmiennej (wygląda zbyt podobnie jak 1tutaj) i przepisałbym sum(bool(e) for e in l)jakosum(1 for e in l if e)
wim

22

Jednowierszowa odpowiedź, która zachowuje zachowanie polegające na zwarciu:

from itertools import ifilter, islice

def only1(l):
    return len(list(islice(ifilter(None, l), 2))) == 1

Będzie to znacznie szybsze niż inne alternatywy tutaj dla bardzo dużych iteracji, które mają dwie lub więcej wartości rzeczywistych stosunkowo wcześnie.

ifilter(None, itr)daje iterowalne, które dostarczą tylko prawdziwych elementów ( xjest prawdziwe, jeśli bool(x)zwraca True). islice(itr, 2)daje element iterowalny, który zwróci tylko pierwsze dwa elementy itr. Konwertując to na listę i sprawdzając, czy długość jest równa jeden, możemy sprawdzić, czy istnieje dokładnie jeden prawdziwy element bez konieczności sprawdzania jakichkolwiek dodatkowych elementów po znalezieniu dwóch.

Oto kilka porównań czasowych:

  • Kod konfiguracji:

    In [1]: from itertools import islice, ifilter
    
    In [2]: def fj(l): return len(list(islice(ifilter(None, l), 2))) == 1
    
    In [3]: def david(l): return sum(bool(e) for e in l) == 1
    
  • Wykazujące zachowanie zwarciowe:

    In [4]: l = range(1000000)
    
    In [5]: %timeit fj(l)
    1000000 loops, best of 3: 1.77 us per loop
    
    In [6]: %timeit david(l)
    1 loops, best of 3: 194 ms per loop
    
  • Duża lista, w których nie występuje zwarcie:

    In [7]: l = [0] * 1000000
    
    In [8]: %timeit fj(l)
    100 loops, best of 3: 10.2 ms per loop
    
    In [9]: %timeit david(l)
    1 loops, best of 3: 189 ms per loop
    
  • Mała lista:

    In [10]: l = [0]
    
    In [11]: %timeit fj(l)
    1000000 loops, best of 3: 1.77 us per loop
    
    In [12]: %timeit david(l)
    1000000 loops, best of 3: 990 ns per loop
    

Więc sum()podejście jest szybsze w przypadku bardzo małych list, ale gdy lista wejściowa staje się większa, moja wersja jest szybsza nawet wtedy, gdy zwarcie nie jest możliwe. Gdy zwarcie jest możliwe na dużym wejściu, różnica w wydajności jest wyraźna.


5
Auć. Trzykrotnie zajęło mi to zrozumienie innych opcji. Jeśli zwarcie jest ważne, wziąłbym kod OP, ponieważ jest znacznie bardziej oczywisty i mniej więcej tak samo wydajny.

1
Głosuj za stylem i zachowując zwarcie. Ale trudniej to przeczytać.
Matthew Scouten

1
+1. Jedyny, który w pełni odtworzył zamiar OP, jakim jest zwarcie.
NominSim

1
+1, jeśli zapewnisz trochę timeiteksperymentów w celu obiektywnego porównania wydajności z rozwiązaniem OP.
moooeeeep

@moooeeeep Naiwnie, gdybyś miał nieskończoną iterowalność, która ma Truegdzieś „wcześnie” dwie wartości, to się skończy, w przeciwieństwie do innych odpowiedzi, które zawsze kręcą kołami, próbując policzyć.
NominSim

15

Chciałem zdobyć odznakę nekromanty, więc uogólniłem doskonałą odpowiedź Jona Clementsa, zachowując zalety logiki zwarciowej i szybkiego sprawdzania predykatów ze wszystkimi.

Oto więc:

N (prawda) = n

def n_trues(iterable, n=1):
    i = iter(iterable)
    return all(any(i) for j in range(n)) and not any(i)

N (prawda) <= n:

def up_to_n_trues(iterable, n=1):
    i = iter(iterable)
    all(any(i) for j in range(n))
    return not any(i)

N (prawda)> = n:

def at_least_n_trues(iterable, n=1):
    i = iter(iterable)
    return all(any(i) for j in range(n))

m <= N (prawda) <= n

def m_to_n_trues(iterable, m=1, n=1):
    i = iter(iterable)
    assert m <= n
    return at_least_n_trues(i, m) and up_to_n_trues(i, n - m)

11
>>> l = [0, 0, 1, 0, 0]
>>> has_one_true = len([ d for d in l if d ]) == 1
>>> has_one_true
True

4
Dlaczego ten głos został odrzucony? Myślę, że jest to najprostsze i najbardziej czytelne ze wszystkich.
dansalmo

1
@dansalmo: Trudno być oczywiście pewnym, ale moja teoria jest taka, że ​​wielu programistów n00b w Pythonie - być może szczególnie ci z językiem Java - czuje się bardziej komfortowo z dłuższą składnią. (Ja byłem trochę taki 5-10 lat temu, ale dziś uważam to za nieprofesjonalne i ignoranckie.) +1
Jonas Byström

5

Możesz to zrobić:

x = [bool(i) for i in x]
return x.count(True) == 1

Lub

x = map(bool, x)
return x.count(True) == 1

Opierając się na metodzie @ JoranBeasley:

sum(map(bool, x)) == 1

5
if sum([bool(x) for x in list]) == 1

(Zakładając, że wszystkie twoje wartości są logiczne).

Prawdopodobnie byłoby to szybsze po prostu zsumowanie

sum(list) == 1   

chociaż może to powodować pewne problemy w zależności od typów danych na liście.


1
Przydałyby się tutaj wielkie litery i znaki interpunkcyjne.
Steven Rumbalski

4

Jeśli jest tylko jeden True, długość Trues powinna wynosić jeden:

def only_1(l): return 1 == len(filter(None, l))

2
Może mógłbyś wyjaśnić swoją odpowiedź?
Linus Caldwell

4

Wydaje się, że to działa i powinno być w stanie obsłużyć każdą iterację, nie tylko lists. W miarę możliwości zwiera, aby zmaksymalizować wydajność. Działa zarówno w Pythonie 2, jak i 3.

def only1(iterable):
    for i, x in enumerate(iterable):  # check each item in iterable
        if x: break                   # truthy value found
    else:
        return False                  # no truthy value found
    for x in iterable[i+1:]:          # one was found, see if there are any more
        if x: return False            #   found another...
    return True                       # only a single truthy value found

testcases = [  # [[iterable, expected result], ... ]
    [[                          ], False],
    [[False, False, False, False], False],
    [[True,  False, False, False], True],
    [[False, True,  False, False], True],
    [[False, False, False, True],  True],
    [[True,  False, True,  False], False],
    [[True,  True,  True,  True],  False],
]

for i, testcase in enumerate(testcases):
    correct = only1(testcase[0]) == testcase[1]
    print('only1(testcase[{}]): {}{}'.format(i, only1(testcase[0]),
                                             '' if correct else
                                             ', error given '+str(testcase[0])))

Wynik:

only1(testcase[0]): False
only1(testcase[1]): False
only1(testcase[2]): True
only1(testcase[3]): True
only1(testcase[4]): True
only1(testcase[5]): False
only1(testcase[6]): False

Podoba mi się to podejście, co powiesz na przerobienie logiki iter(x for x in my_list if x)i użycie next, może ładniejszego niż używanie mapilist.index
wim

@wim: Chociaż nie zastosowałem zaproponowanego przez Ciebie podejścia, Twój komentarz zainspirował mnie do zrewidowania mojej pierwotnej odpowiedzi i uczynienia jej jeszcze bardziej przyrostową oraz pozbycia się mapi list.index.
martineau

3

Rozwiązanie @ JonClements zostało rozszerzone na co najwyżej N wartości True :

# Extend any() to n true values
def _NTrue(i, n=1):
    for x in xrange(n):
        if any(i): # False for empty
            continue
        else:
            return False
    return True

def NTrue(iterable, n=1):
    i = iter(iterable)
    return any(i) and not _NTrue(i, n)

edycja: lepsza wersja

def test(iterable, n=1): 
    i = iter(iterable) 
    return sum(any(i) for x in xrange(n+1)) <= n 

edit2: uwzględnij co najmniej m True i co najwyżej n True

def test(iterable, n=1, m=1): 
    i = iter(iterable) 
    return  m <= sum(any(i) for x in xrange(n+1)) <= n

1
Nie, mam na myśli najwyżej. Zwraca True jeżeli istnieją co najwyżej N wartościami rzeczywistymi wartościami: np 3 Trues na liście 1000 dostanie iterable.count(True) = 3, NTrue(iterable, 1) = False, NTrue(iterable, 2) = False, NTrue(iterable, 3) = True, NTrue(iterable, 4) = True, ... to w zasadzie rozszerza and not any(i)część doand not any(i) and not any(i) and not...
Nisan.H

1
Nie all(any(i) for i in xrange(n)) and not any(i)działa tutaj?
Eric

@Eric, który zwróci True tylko dla dokładnie n wartości prawdziwych. Dało mi to jednak pomysł, aby zsumować wartości anys.
Nisan.H

Masz na myśli raczej any(i) and not all(any(i) for x in xrange(n))?
moooeeeep

@moooeeeep True and not all(<n booleans>)logicznie nie jest tym samym, co count(True) <= n? Chodzi o to, aby przetestować najmniejszy możliwy zestaw i przerwać w pierwszym stanie awarii.
Nisan.H

2
def only1(l)
    sum(map(lambda x: 1 if x else 0, l)) == 1

Objaśnienie: mapFunkcja odwzorowuje listę na inną listę, wykonując czynności True => 1i False => 0. Mamy teraz listę zer i jedynek zamiast Prawda lub Fałsz. Teraz po prostu zsumujemy tę listę i jeśli wynosi 1, była tylko jedna wartość True.


1

Czy tego szukasz?

sum(l) == 1

Nie udaje się to w przypadku listy: [2], ponieważ autor nie określił, że elementy muszą być tylko prawdziwe i fałszywe, lub 1 i 0
vtlinh

1

Ze względu na kompletność i aby zademonstrować zaawansowane wykorzystanie przepływu sterowania Pythona dla iteracji pętli, można uniknąć dodatkowego rozliczania w akceptowanej odpowiedzi, dzięki czemu jest to nieco szybsze .:

def one_bool_true(iterable):
    it = iter(iterable)
    for i in it:
        if i:
            break
    else:            #no break, didn't find a true element
        return False
    for i in it:     # continue consuming iterator where left off
        if i: 
            return False
    return True      # didn't find a second true.

Powyższe proste przepływ sterowania wykorzystuje Pythona wyrafinowanych funkcji pętli: the else. Semantyka polega na tym, że jeśli zakończysz iterację po iteratorze, który konsumujesz, bez breakwychodzenia z niego, wtedy wchodzisz do elsebloku.

Oto akceptowana odpowiedź, która wymaga nieco większej rachunkowości.

def only1(l):
    true_found = False
    for v in l:
        if v:
            # a True was found!
            if true_found:
                # found too many True's
                return False 
            else:
                # found the first True
                true_found = True
    # found zero or one True value
    return true_found

do czasu te:

import timeit
>>> min(timeit.repeat(lambda: one_bool_true([0]*100 + [1, 1])))
13.992251592921093
>>> min(timeit.repeat(lambda: one_bool_true([1, 1] + [0]*100)))
2.208037032979064
>>> min(timeit.repeat(lambda: only1([0]*100 + [1, 1])))
14.213872335107908
>>> min(timeit.repeat(lambda: only1([1, 1] + [0]*100)))
2.2482982632641324
>>> 2.2482/2.2080
1.0182065217391305
>>> 14.2138/13.9922
1.0158373951201385

Widzimy więc, że zaakceptowana odpowiedź trwa nieco dłużej (nieco ponad półtora procenta).

Oczywiście korzystanie z wbudowanego any, napisanego w C, jest znacznie szybsze (patrz odpowiedź Jona Clementa na implementację - to jest krótka forma):

>>> min(timeit.repeat(lambda: single_true([0]*100 + [1, 1])))
2.7257133318785236
>>> min(timeit.repeat(lambda: single_true([1, 1] + [0]*100)))
2.012824866380015

0
import collections

def only_n(l, testval=True, n=1):
    counts = collections.Counter(l)
    return counts[testval] == n

Czas liniowy. Używa wbudowanej klasy Counter, której należy używać do sprawdzania zliczeń.

Po ponownym przeczytaniu pytania wygląda na to, że faktycznie chcesz sprawdzić, czy jest tylko jedna prawdziwa wartość, a nie jedna Truewartość. Spróbuj tego:

import collections

def only_n(l, testval=True, coerce=bool, n=1):
    counts = collections.Counter((coerce(x) for x in l))
    return counts[testval] == n

Chociaż możesz uzyskać lepszą wydajność w najlepszym przypadku, nic nie ma lepszej wydajności w najgorszym przypadku. Jest to również krótkie i łatwe do odczytania.

Oto wersja zoptymalizowana pod kątem wydajności w najlepszym przypadku:

import collections
import itertools

def only_n(l, testval=True, coerce=bool, n=1):
    counts = collections.Counter()
    def iterate_and_count():
        for x in itertools.imap(coerce,l):
            yield x
            if x == testval and counts[testval] > n:
               break
    counts.update(iterate_and_count())
    return counts[testval] == n

W najgorszym przypadku wydajność jest wysoka k(jak w O(kn+c)), ale jest całkowicie ogólna.

Oto pomysł na eksperymentowanie z wydajnością: http://ideone.com/ZRrv2m


0

Oto coś, co powinno działać na wszystko, co prawda, chociaż nie ma zwarcia. Znalazłem to, szukając czystego sposobu na zakazanie wzajemnie wykluczających się argumentów:

if sum(1 for item in somelist if item) != 1:
    raise ValueError("or whatever...")

0

Co powiesz na:

len([v for v in l if type(v) == bool and v])

Jeśli chcesz liczyć tylko wartości logiczne True.

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.