Perché ne sono () e tutti () inefficiente nel trattamento booleani?

voti
2

Ho appena realizzato qualcosa mentre gioca con timeite and, or, any(), all()che ho pensato che avrei potuto condividere qui. Ecco lo script per misurare le prestazioni:

def recursion(n):
    A slow way to return a True or a False boolean.
    return True if n == 0 else recursion(n-1)       

def my_function():
    The function where you perform all(), any(), or, and.
    a = False and recursion(10)

if __name__ == __main__:
    import timeit
    setup = from __main__ import my_function
    print(timeit.timeit(my_function(), setup=setup))

Ed ecco alcuni tempi:

a = False and recursion(10)
0.08799480279344607

a = True or recursion(10)
0.08964192798430304

Come previsto, True or recursion(10)così come False and recursion(10)sono molto veloce per calcolare in quanto solo le prime questioni termine e l'operazione restituisce immediatamente.

a = recursion(10) or True # recursion() is False
1.4154556830951606 

a = recursion(10) and False # recursion() is True
1.364157978046478

Avendo or Trueo and Falsein linea non accelerare il calcolo qui perché sono valutate secondo e tutta ricorsione deve essere eseguita prima. Mentre fastidioso, è logico e segue regole di priorità di funzionamento.

Ciò che è più sorprendente è che all()e any()avere sempre la peggiore performance a prescindere dal caso:

a = all(i for i in (recursion(10), False))) # recursion() is False
1.8326778537880273

a = all(i for i in (False, recursion(10))) # recursion() is False
1.814645767348111

Mi sarei aspettato la seconda valutazione di essere molto più veloce rispetto al primo.

a = any(i for i in (recursion(10), True))) # recursion() is True
1.7959248761901563

a = any(i for i in (True, recursion(10))) # recursion() is True
1.7930442127481

le aspettative non soddisfatte Stesso qui.

Così sembra any()e all()sono ben lungi dall'essere un modo pratico di scrivere, rispettivamente, un grande ore un grande and, se la performance è nell'applicazione. Perché?

Edit: sulla base delle osservazioni sembra che la generazione tupla è lento. Non vedo alcuna ragione per cui Python stesso non potrebbe utilizzare questo:

def all_faster(*args):
    Result = True
    for arg in args:
        if not Result:
            return False
        Result = Result and arg
    return True

def any_faster(*args):
    Result = False
    for arg in args:
        if Result:
            return True
        Result = Result or arg
    return False

E 'già più veloce di funzioni built-in e sembra avere il meccanismo di corto circuito.

a = faster_any(False, False, False, False, True)
0.39678611016915966

a = faster_any(True, False, False, False, False)
0.29465180389252055

a = faster_any(recursion(10), False) # recursion() is True
1.5922580174283212

a = faster_any(False, recursion(10)) # recursion() is True
1.5799157924820975

a = faster_all(False, recursion(10)) # recursion() is True
1.6116566893888375

a = faster_all(recursion(10), False) # recursion() is True
1.6004807187900951

Edit2: Bene è più veloce con gli argomenti passati ad uno ad uno, ma più lento con i generatori.

È pubblicato 19/09/2018 alle 13:22
fonte dall'utente
In altre lingue...                            


2 risposte

voti
2

In realtà, any()è equivalente ad una catena di ore all()è equivalente ad una catena di and, compreso cortocircuito. Il problema risiede nel modo in cui si esegue il punto di riferimento.

Si consideri il seguente:

def slow_boolean_gen(n, value=False):
    for x in range(n - 1):
        yield value
    yield not value

generator = slow_boolean_gen(10)

print([x for x in generator])
# [False, False, False, False, False, False, False, False, False, True]

e le seguenti micro-benchmark:

%timeit generator = slow_boolean_gen(10, True); next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator)
# 492 ns ± 35.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator)
# 1.18 µs ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator)
# 1.19 µs ± 11.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator)
# 473 ns ± 6.27 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit generator = slow_boolean_gen(10, True); any(x for x in generator)
# 745 ns ± 15 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); any(x for x in generator)
# 1.29 µs ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); all(x for x in generator)
# 1.3 µs ± 22.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); all(x for x in generator)
# 721 ns ± 8.05 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit generator = slow_boolean_gen(10, True); any([x for x in generator])
# 1.03 µs ± 28.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); any([x for x in generator])
# 1.09 µs ± 27.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); all([x for x in generator])
# 1.05 µs ± 11.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); all([x for x in generator])
# 1.02 µs ± 11.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Si può chiaramente vedere che il corto circuito è in funzione, ma se prima di costruire il list, che richiede una costante di tempo che compensa qualsiasi guadagno di prestazione che si otterrebbe da corto circuito.

MODIFICARE:

Un'implementazione manuale non ci compra qualsiasi guadagno di prestazioni:

def all_(values):
    result = True
    for value in values:
        result = result and value
        if not result:
            break
    return result

def any_(values):
    result = False
    for value in values:
        result = result or value
        if result:
            break
    return result

%timeit generator = slow_boolean_gen(10, True); any_(x for x in generator)
# 765 ns ± 6.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); any_(x for x in generator)
# 1.48 µs ± 8.97 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); all_(x for x in generator)
# 1.47 µs ± 5.71 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); all_(x for x in generator)
# 765 ns ± 8.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Risposto il 19/09/2018 a 14:11
fonte dall'utente

voti
1

anye allcortocircuito bene.

Il problema è che qui in entrambi i casi, è necessario costruire la tupleprima di passarlo al anymodo l'ordine non fa una differenza: il tempo impiegato è sempre lo stesso. Facciamo decompongono questo con una variabile:

t = (True, recursion(10))   # recursion is called
a = any(i for i in t)       # this is very fast, only boolean testing

Quando si sta raggiungendo la seconda linea, il tempo è già stato speso.

E 'diverso con ando orche cortocircuito.

Il caso in cui anyo allsono interessante è quando si sta valutando i dati quando si sta testando:

any(recusion(x) for x in (10,20,30))

Se si voleva evitare di valutazione, si potrebbe passare una tupla di lambda (funzioni inline) alle anye chiamare le funzioni:

adesso:

a = any(i() for i in (lambda:recursion(10), lambda:True))) 

e:

a = any(i() for i in (lambda:True,lambda:recursion(10)))) 

avere un tempo di esecuzione molto diverso (quest'ultimo è istantanea)

Risposto il 19/09/2018 a 13:23
fonte dall'utente

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more