Por que qualquer () e todos () ineficiente no tratamento booleans?

votos
2

Eu só percebi algo enquanto brincava com timeite and, or, any(), all()que eu percebi que eu poderia compartilhar aqui. Aqui está o script para medir o desempenho:

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

E aqui estão alguns horários:

a = False and recursion(10)
0.08799480279344607

a = True or recursion(10)
0.08964192798430304

Como esperado, True or recursion(10)bem como False and recursion(10)são muito rápidos para calcular porque só os primeiros assuntos prazo e a operação retorna imediatamente.

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

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

Ter or Trueou and Falsena linha de não acelerar a computação aqui, porque eles são avaliados segundo e toda a recursividade tem de ser realizada pela primeira vez. Enquanto irritante, é lógico e segue regras de prioridade operação.

O que é mais surpreendente é que all()e any()sempre tem o pior desempenho, independentemente do processo:

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

Eu teria esperado que a segunda avaliação a ser muito mais rápido do que o primeiro.

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

expectativas não atendidas mesmo aqui.

Então parece que any()e all()estão longe de ser uma maneira útil para escrever respectivamente, um grande ore um grande andse as questões de desempenho em sua aplicação. Por que é que?

Edit: com base nos comentários, parece que a geração tupla é lento. Eu não vejo nenhuma razão pela qual o próprio Python não poderia usar isto:

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

É mais rápido já que as funções internas e parece ter o mecanismo de curto-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: Certo é mais rápido com argumentos passados ​​um por um, mas mais lento com geradores.

Publicado 19/09/2018 em 13:22
fonte usuário
Em outras línguas...                            


2 respostas

votos
2

Na verdade, any()é equivalente a uma cadeia de ore all()é equivalente a uma cadeia de and, incluindo curto-circuito. O problema reside na forma como você executar o benchmark.

Considere o seguinte:

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 os seguintes micro-benchmarks:

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

Você pode ver claramente que o curto-circuito está funcionando, mas se você construir primeiro o listque leva um tempo constante, que compensa qualquer ganho de desempenho que você obteria de curto-circuito.

EDITAR:

A implementação manual não nos comprar qualquer ganho de desempenho:

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)
Respondeu 19/09/2018 em 14:11
fonte usuário

votos
1

anye allcurto-circuito bem.

O problema é que aqui em ambos os casos, você tem que construir o tupleantes de passá-lo para anyassim a ordem não faz diferença: o tempo ainda é o mesmo. Vamos decompor isto com uma variável:

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

Quando você está alcançando a segunda linha, o tempo já foi gasto.

É diferente com andou orque curto-circuito.

O caso em que anyou allsão interessantes é quando você está avaliando os dados quando você está testando:

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

Se você queria evitar a avaliação, você poderia passar uma tupla de lambdas (funções inline) para anye chamar as funções:

agora:

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

e:

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

tem um tempo de execução muito diferente (o último é instantânea)

Respondeu 19/09/2018 em 13:23
fonte usuário

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