Hvorfor er noen () og alle () ineffektiv ved behandling booleans?

stemmer
2

Jeg skjønte bare noe mens du spiller med timeitog and, or, any(), all()som jeg tenkte jeg kunne dele her. Her er manuset for å måle ytelsen:

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

Og her er noen timings:

a = False and recursion(10)
0.08799480279344607

a = True or recursion(10)
0.08964192798430304

Som forventet, True or recursion(10)samt False and recursion(10)er veldig raske til å beregne fordi bare de første varige saker og driften returnerer umiddelbart.

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

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

Å ha or Trueeller and Falsei linjen ikke fremskynde beregningen her fordi de er vurdert andre og hele rekursjon skal utføres først. Mens irriterende, det er logisk og det følger drift prioriterte regler.

Hva er mer overraskende er at all()og any()alltid ha de verste resultatene uavhengig av saken:

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

Jeg ville ha forventet den andre evalueringen til å være mye raskere enn den første.

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

Samme udekkede forventninger her.

Så det virker som any(), og all()er langt fra å være en praktisk måte å skrive henholdsvis en stor orog en stor anddersom ytelsen saker i programmet. Hvorfor det?

Edit: basert på kommentarer det synes tuppel generasjon er treg. Jeg ser ingen grunn til at Python selv ikke kunne bruke denne:

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

Det er raskere allerede enn de innebygde funksjoner og synes å ha kortslutnings mekanisme.

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: er alright det er raskere med argumenter som sendes én etter én, men tregere med generatorer.

Publisert på 19/09/2018 klokken 13:22
kilden bruker
På andre språk...                            


2 svar

stemmer
2

Faktisk, any()er ekvivalent med en kjede av orog all()er ekvivalent til en kjede av and, blant annet kortslutning. Problemet ligger i måten du utfører referanseindeksen.

Vurder følgende:

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]

og følgende mikroytelsestester:

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

Du kan tydelig se at kortslutningen fungerer, men hvis du først bygge list, hadde en konstant tid som oppveier eventuelle ytelsesgevinst som du ville fått fra kortslutning.

REDIGERE:

En manuell implementering ikke kjøpe oss noen ytelsesgevinst:

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)
Svarte 19/09/2018 kl. 14:11
kilden bruker

stemmer
1

anyog allkortslutning all right.

Problemet er at her i begge tilfeller, må du bygge den tuplefør gi det til anyslik at ordren ikke gjøre en forskjell: den tiden det tar er fortsatt den samme. La oss brytes dette med en variabel:

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

Når du når den andre linjen, tiden er allerede blitt brukt.

Det er annerledes med andeller orsom kortslutning.

Saken der anyeller aller interessant er når du evaluerer dataene når du tester:

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

Hvis du ønsker å unngå evaluering, kan du passere en tuppel av lambdaene (inline funksjoner) til anyog ringe funksjonene:

nå:

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

og:

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

har en helt annen utførelsestiden (den sistnevnte er momentant)

Svarte 19/09/2018 kl. 13:23
kilden bruker

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