Pourquoi tout () et tout () inefficace dans le traitement booléens?

voix
2

Je viens de réaliser quelque chose en jouant avec timeitet and, or, any(), all()que je pensais que je pouvais partager ici. Voici le script pour mesurer la performance:

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

Et voici quelques timings:

a = False and recursion(10)
0.08799480279344607

a = True or recursion(10)
0.08964192798430304

Comme prévu, True or recursion(10)ainsi que False and recursion(10)sont très rapides à calculer car seules les premières questions à long terme et l'opération retourne immédiatement.

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

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

Avoir or Trueou and Falsedans la ligne n'accélère pas le calcul ici parce qu'ils sont évalués deuxième et l'ensemble récursivité doit être effectué en premier. Bien que gênant, il est logique et il suit des règles de priorité de fonctionnement.

Ce qui est plus surprenant est que all()et any()ont toujours la pire performance quel que soit le cas:

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

Je me serais attendu à la deuxième évaluation soit beaucoup plus rapide que le premier.

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

Mêmes attentes non comblés.

Il semble donc que , any()et all()sont loin d'être un moyen pratique pour écrire respectivement un grand oret un grand andsi les questions de performance dans votre application. Pourquoi donc?

Edit: sur la base des commentaires il semble que la génération de tuple est lente. Je ne vois aucune raison pour laquelle Python lui-même ne pouvait pas utiliser ceci:

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

Il est plus rapide que déjà les fonctions intégrées et semble avoir le mécanisme de court-circuit.

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: il est bien plus rapide avec des arguments passés un par un, mais plus lent avec des générateurs.

Créé 19/09/2018 à 13:22
source utilisateur
Dans d'autres langues...                            


2 réponses

voix
2

En fait, any()équivaut à une chaîne de oret all()est équivalente à une chaîne de and, y compris de court-circuit. Le problème réside dans la façon dont vous effectuez la référence.

Considérer ce qui suit:

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]

et les micro-indices de référence suivants:

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

Vous pouvez clairement voir que le court-circuit fonctionne, mais si vous commencez à construire la list, qui prend un temps constant qui compense tout gain de performance que vous obtiendriez de court-circuit.

MODIFIER:

Une mise en œuvre manuelle ne nous achète pas tout gain de performance:

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)
Créé 19/09/2018 à 14:11
source utilisateur

voix
1

anyet allcourt-circuiter tout droit.

Le problème est que ici dans les deux cas, vous devez construire tupleavant de le transmettre à anysi l'ordre ne fait pas de différence: le temps est toujours le même. Nous allons décomposer cela avec une variable:

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

Lorsque vous êtes atteint la deuxième ligne, le temps a déjà été dépensé.

Il est différent avec andou orqui court - circuit.

Le cas où anyou allsont intéressants est quand vous évaluez les données lorsque vous testez:

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

Si vous voulez éviter l' évaluation, vous pouvez passer un tuple de lambdas (fonctions de ligne) à anyet appeler les fonctions:

à présent:

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

et:

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

un temps d'exécution très différentes (celle-ci est instantanée)

Créé 19/09/2018 à 13:23
source utilisateur

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