not - python if is false

¿Por qué es "if not(a and b)" más rápido que "if not a or not b"?

Question

Por un capricho, recientemente probé estos dos métodos con timeit , para ver qué método de evaluación era más rápido:

import timeit

"""Test method returns True if either argument is falsey, else False."""

def and_chk((a, b)):
    if not (a and b):
        return True
    return False

def not_or_chk((a, b)):
    if not a or not b:
        return True
    return False

... y obtuve estos resultados:

 VALUES FOR a,b ->      0,0         0,1         1,0         1,1
        method
    and_chk(a,b)    0.95559     0.98646     0.95138     0.98788
 not_or_chk(a,b)    0.96804     1.07323     0.96015     1.05874
                                            ...seconds per 1,111,111 cycles.

La diferencia en la eficiencia está entre uno y nueve por ciento, siempre a favor de if not (a and b) , que es lo contrario de lo que podría esperar, ya que entiendo que if not a or not b evaluará sus términos ( if not a y luego if not b ) en orden, ejecutando el bloque if una vez que encuentra una expresión verdadera (y hay no and cláusulas). En contraste, el método and_chk necesita evaluar ambas cláusulas antes de que pueda devolver cualquier resultado al if not.. que lo envuelve.

Los resultados de tiempo, sin embargo, refutan esta comprensión. ¿Cómo, entonces, se evalúa la condición if ? Soy perfectamente consciente del hecho de que este grado de microoptimización es prácticamente, si no del todo, inútil. Solo quiero entender cómo lo está haciendo Python.

Para completar, así es como configuré el timeit ...

cyc = 1111111

bothFalse_and = iter([(0,0)] * cyc)
zeroTrue_and = iter([(1,0)] * cyc)
oneTrue_and = iter([(0,1)] * cyc)
bothTrue_and = iter([(1,1)] * cyc)

bothFalse_notor = iter([(0,0)] * cyc)
zeroTrue_notor = iter([(1,0)] * cyc)
oneTrue_notor = iter([(0,1)] * cyc)
bothTrue_notor = iter([(1,1)] * cyc)

time_bothFalse_and = timeit.Timer(''and_chk(next(tups))'', ''from __main__ import bothFalse_and as tups, and_chk'')
time_zeroTrue_and = timeit.Timer(''and_chk(next(tups))'', ''from __main__ import zeroTrue_and as tups, and_chk'')
time_oneTrue_and = timeit.Timer(''and_chk(next(tups))'', ''from __main__ import oneTrue_and as tups, and_chk'')
time_bothTrue_and = timeit.Timer(''and_chk(next(tups))'', ''from __main__ import bothTrue_and as tups, and_chk'')

time_bothFalse_notor = timeit.Timer(''not_or_chk(next(tups))'', ''from __main__ import bothFalse_notor as tups, not_or_chk'')
time_zeroTrue_notor = timeit.Timer(''not_or_chk(next(tups))'', ''from __main__ import zeroTrue_notor as tups, not_or_chk'')
time_oneTrue_notor = timeit.Timer(''not_or_chk(next(tups))'', ''from __main__ import oneTrue_notor as tups, not_or_chk'')
time_bothTrue_notor = timeit.Timer(''not_or_chk(next(tups))'', ''from __main__ import bothTrue_notor as tups, not_or_chk'')

... luego ejecuta cada timeit.Timer(..) función con .timeit(cyc) para obtener los resultados publicados.

Answer 1

TL; DR

La función not_or_chk requiere dos operaciones unarias además de dos saltos (en el peor de los casos), mientras que la función and_chk solo tiene los dos saltos (nuevamente, en el peor de los casos).

Detalles

El módulo de des al rescate! El módulo dis permite ver el desmontaje del código de Python de su código. Por ejemplo:

import dis

"""Test method returns True if either argument is falsey, else False."""

def and_chk((a, b)):
    if not (a and b):
        return True
    return False

def not_or_chk((a, b)):
    if not a or not b:
        return True
    return False

print("And Check:/n")
print(dis.dis(and_chk))

print("Or Check:/n")
print(dis.dis(not_or_chk))

Produce este resultado:

And Check:

  5           0 LOAD_FAST                0 (.0)
              3 UNPACK_SEQUENCE          2
              6 STORE_FAST               1 (a)
              9 STORE_FAST               2 (b)

  6          12 LOAD_FAST                1 (a)    * This block is the *
             15 JUMP_IF_FALSE_OR_POP    21        * disassembly of    *
             18 LOAD_FAST                2 (b)    * the "and_chk"     *
        >>   21 POP_JUMP_IF_TRUE        28        * function          *

  7          24 LOAD_GLOBAL              0 (True)
             27 RETURN_VALUE

  8     >>   28 LOAD_GLOBAL              1 (False)
             31 RETURN_VALUE
None
Or Check:

 10           0 LOAD_FAST                0 (.0)
              3 UNPACK_SEQUENCE          2
              6 STORE_FAST               1 (a)
              9 STORE_FAST               2 (b)

 11          12 LOAD_FAST                1 (a)    * This block is the *
             15 UNARY_NOT                         * disassembly of    *
             16 POP_JUMP_IF_TRUE        26        * the "not_or_chk"  *
             19 LOAD_FAST                2 (b)    * function          *
             22 UNARY_NOT
             23 POP_JUMP_IF_FALSE       30

 12     >>   26 LOAD_GLOBAL              0 (True)
             29 RETURN_VALUE

 13     >>   30 LOAD_GLOBAL              1 (False)
             33 RETURN_VALUE
None

Eche un vistazo a los dos bloques de código de bytes Python que he marcado con los asteriscos. Esos bloques son sus dos funciones desmontadas. Tenga en cuenta que and_chk solo tiene dos saltos, y los cálculos en la función se realizan al decidir si se toma el salto o no .

Por otro lado, la función not_or_chk requiere que la operación not se lleve a cabo dos veces en el peor de los casos, además del intérprete que decide si tomar el salto o no.

Answer 2

Acabo de notar esta pregunta a través de su pregunta de Meta SO: ¿es apropiado compartir los resultados de mi investigación para resolver mis propias preguntas menores? . Como mencionas en esa pregunta (y una de las etiquetas en esta pregunta lo indica), este tipo de cosas cae en la categoría de micro-optimización. Idealmente, uno no debería tener que preocuparse por diferencias de rendimiento menores, y como dice Knuth, la optimización prematura es la raíz de todo mal . Pero creo que es divertido e instructivo investigar estos asuntos, ya que puede darte una mejor idea de cómo funciona Python "bajo el capó".

El comentario de Mephy me impulsó a ver cuáles eran las diferencias de tiempo para las versiones sin sentido de tus funciones. Los resultados son interesantes, en mi humilde opinión. También aproveché la oportunidad para simplificar su procedimiento de prueba.

#!/usr/bin/env python

'''''' Do timeit tests on various implementations of NAND

    NAND returns True if either argument is falsey, else False.
    From https://.com/q/29551438/4014959
    Written by PM 2Ring 2015.04.09
''''''

from timeit import Timer
import dis

def and_chk(a, b):
    return not (a and b)

def and_chk_if(a, b):
    if not (a and b):
        return True
    else:
        return False

def not_or_chk(a, b):
    return not a or not b

def not_or_chk_if(a, b):
    if not a or not b:
        return True
    else:
        return False


#All the functions
funcs = (
    and_chk,
    and_chk_if,
    not_or_chk,
    not_or_chk_if,
)

#Argument tuples to test the functions with
bools = (0, 1)
bool_tups = [(u, v) for u in bools for v in bools]


def show_dis():
    '''''' Show the disassembly for each function ''''''
    print ''Disassembly''
    for func in funcs:
        fname = func.func_name
        print ''/n%s'' % fname
        dis.dis(func)
    print


def verify():
    '''''' Verify that the functions actually perform as intended ''''''
    print ''Verifying...''
    for func in funcs:
        fname = func.func_name
        print ''/n%s'' % fname
        for args in bool_tups:
            print args, func(*args)
    print


def time_test(loops, reps):
    '''''' Print timing stats for all the functions ''''''
    print ''Timing tests/nLoops = %d, Repetitions = %d'' % (loops, reps)

    for func in funcs:
        fname = func.func_name
        print ''/n%s'' % fname
        setup = ''from __main__ import %s'' % fname
        for args in bool_tups:
            t = Timer(''%s%s'' % (fname, args), setup)
            r = t.repeat(reps, loops)
            r.sort()
            print args, r


show_dis()
verify()
time_test(loops=520000, reps=3)

salida

Disassembly

and_chk
 13           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE            4 (to 10)
              6 POP_TOP             
              7 LOAD_FAST                1 (b)
        >>   10 UNARY_NOT           
             11 RETURN_VALUE        

and_chk_if
 16           0 LOAD_FAST                0 (a)
              3 JUMP_IF_FALSE            4 (to 10)
              6 POP_TOP             
              7 LOAD_FAST                1 (b)
        >>   10 JUMP_IF_TRUE             5 (to 18)
             13 POP_TOP             

 17          14 LOAD_GLOBAL              0 (True)
             17 RETURN_VALUE        
        >>   18 POP_TOP             

 19          19 LOAD_GLOBAL              1 (False)
             22 RETURN_VALUE        
             23 LOAD_CONST               0 (None)
             26 RETURN_VALUE        

not_or_chk
 22           0 LOAD_FAST                0 (a)
              3 UNARY_NOT           
              4 JUMP_IF_TRUE             5 (to 12)
              7 POP_TOP             
              8 LOAD_FAST                1 (b)
             11 UNARY_NOT           
        >>   12 RETURN_VALUE        

not_or_chk_if
 25           0 LOAD_FAST                0 (a)
              3 UNARY_NOT           
              4 JUMP_IF_TRUE             8 (to 15)
              7 POP_TOP             
              8 LOAD_FAST                1 (b)
             11 UNARY_NOT           
             12 JUMP_IF_FALSE            5 (to 20)
        >>   15 POP_TOP             

 26          16 LOAD_GLOBAL              0 (True)
             19 RETURN_VALUE        
        >>   20 POP_TOP             

 28          21 LOAD_GLOBAL              1 (False)
             24 RETURN_VALUE        
             25 LOAD_CONST               0 (None)
             28 RETURN_VALUE        

Verifying...

and_chk
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

and_chk_if
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

not_or_chk
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

not_or_chk_if
(0, 0) True
(0, 1) True
(1, 0) True
(1, 1) False

Timing tests
Loops = 520000, Repetitions = 3

and_chk
(0, 0) [0.36773014068603516, 0.37793493270874023, 0.38387489318847656]
(0, 1) [0.36292791366577148, 0.37119913101196289, 0.37146902084350586]
(1, 0) [0.38673520088195801, 0.39340090751647949, 0.39670205116271973]
(1, 1) [0.38938498497009277, 0.39505791664123535, 0.40034103393554688]

and_chk_if
(0, 0) [0.4021449089050293, 0.40345501899719238, 0.41558098793029785]
(0, 1) [0.40686416625976562, 0.41213202476501465, 0.44800615310668945]
(1, 0) [0.4281308650970459, 0.42916202545166016, 0.43681907653808594]
(1, 1) [0.46246123313903809, 0.46759700775146484, 0.47544980049133301]

not_or_chk
(0, 0) [0.35435700416564941, 0.36368083953857422, 0.36867713928222656]
(0, 1) [0.35602092742919922, 0.35732793807983398, 0.36237406730651855]
(1, 0) [0.39550518989562988, 0.40660715103149414, 0.40977287292480469]
(1, 1) [0.4060060977935791, 0.4112389087677002, 0.41296815872192383]

not_or_chk_if
(0, 0) [0.4308779239654541, 0.44109201431274414, 0.45827698707580566]
(0, 1) [0.43600606918334961, 0.4370419979095459, 0.47623395919799805]
(1, 0) [0.48452401161193848, 0.48769593238830566, 0.49147915840148926]
(1, 1) [0.53107500076293945, 0.54048299789428711, 0.55434417724609375]

Estos tiempos se realizaron usando Python 2.6.6 en un Pentium 4 de 2 GHz (un solo núcleo de 32 bits) ejecutando Mepis 11 (una distribución de Linux de la familia Debian).

next(tups) que he evitado usar tu next(tups) estrategia next(tups) para obtener los argumentos para cada llamada a función y, en cambio, estoy pasando los argumentos directamente, como constantes. El tiempo necesario para realizar el next(tups) debe ser bastante constante, pero lo mejor es eliminar esos gastos generales, cuando sea práctico, de modo que las mediciones de tiempo informadas reflejen con mayor precisión el rendimiento del código que realmente nos interesa.

Además, es habitual realizar varias repeticiones del ciclo de temporización y tomar el valor mínimo; FWIW, generalmente hago de 3 a 5 repeticiones. De los documentos timeit :

Nota

Es tentador calcular la media y la desviación estándar del vector de resultados e informarlos. Sin embargo, esto no es muy útil. En un caso típico, el valor más bajo proporciona un límite inferior de la velocidad con la que su máquina puede ejecutar el fragmento de código dado; los valores más altos en el vector de resultados generalmente no son causados ​​por la variabilidad en la velocidad de Python, sino por otros procesos que interfieren con su precisión de tiempo. Entonces, el mínimo () del resultado es probablemente el único número que le interese. Después de eso, debe observar el vector completo y aplicar el sentido común en lugar de las estadísticas.

Tu meta post dice que quieres realizar e informar sobre otros experimentos de micro-optimización, por lo que podrías estar interesado en echar un vistazo a algún código que publiqué hace unos meses que hace pruebas de tiempo en varias implementaciones de la función factorial .