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 .