python - ¿Por qué un bucle `for` es mucho más rápido para contar los valores reales?

python-3.x performance

Question

Hace poco respondí una pregunta en un sitio hermano que pedía una función que contara todos los dígitos pares de un número. Una de las otras respuestas contenía dos funciones (que resultaron ser las más rápidas, hasta ahora):

def count_even_digits_spyr03_for(n):
    count = 0
    for c in str(n):
        if c in "02468":
            count += 1
    return count

def count_even_digits_spyr03_sum(n):
    return sum(c in "02468" for c in str(n))

Además miré usando una lista de comprensión y list.count :

def count_even_digits_spyr03_list(n):
    return [c in "02468" for c in str(n)].count(True)

Las primeras dos funciones son esencialmente las mismas, excepto que la primera usa un bucle de conteo explícito, mientras que la segunda usa la sum integrada. Habría esperado que la segunda fuera más rápida (basada, por ejemplo, en esta respuesta ), y es lo que hubiera recomendado convertir la primera en una pregunta para una revisión. Pero, resulta que es al revés. Probándolo con algunos números aleatorios con un número creciente de dígitos (de modo que la probabilidad de que un solo dígito sea parejo sea aproximadamente del 50%) obtengo los siguientes tiempos:

¿Por qué el manual for bucle es mucho más rápido? Es casi un factor dos más rápido que usar la sum . Y como la sum integrada debe ser aproximadamente cinco veces más rápida que sumar manualmente una lista (según la respuesta vinculada ), ¡significa que en realidad es diez veces más rápida! ¿Es el ahorro de solo tener que agregar uno al contador para la mitad de los valores, porque la otra mitad se descarta, suficiente para explicar esta diferencia?

Usando un if como filtro así:

def count_even_digits_spyr03_sum2(n):
    return sum(1 for c in str(n) if c in "02468")

Mejora el tiempo solo al mismo nivel que la lista de comprensión.

Cuando extienden los tiempos a números más grandes, y se normalizan al tiempo de bucle for , convergen asintóticamente para números muy grandes (> 10k dígitos), probablemente debido al tiempo que toma str(n) :

Answer 1

Hay algunas diferencias que realmente contribuyen a las diferencias de rendimiento observadas. Mi objetivo es ofrecer una visión general de alto nivel de estas diferencias, pero intento no profundizar en los detalles de bajo nivel o las posibles mejoras. Para los puntos de referencia utilizo mi propio paquete simple_benchmark .

Generadores vs. bucles

Los generadores y las expresiones generadoras son azúcar sintáctica que puede usarse en lugar de escribir clases de iteradores.

Cuando escribes un generador como:

def count_even(num):
    s = str(num)
    for c in s:
        yield c in ''02468''

O una expresión generadora:

(c in ''02468'' for c in str(num))

Eso se transformará (entre bastidores) en una máquina de estado a la que se puede acceder a través de una clase de iterador. Al final, será aproximadamente equivalente a (aunque el código real generado alrededor de un generador será más rápido):

class Count:
    def __init__(self, num):
        self.str_num = iter(str(num))

    def __iter__(self):
        return self

    def __next__(self):
        c = next(self.str_num)
        return c in ''02468''

Por lo tanto, un generador siempre tendrá una capa adicional de direccionamiento indirecto. Eso significa que avanzar el generador (o la expresión del generador o el iterador) significa que usted llama __next__ en el iterador que genera el generador que a su vez llama __next__ en el objeto sobre el que realmente desea iterar. Pero también tiene cierta sobrecarga porque realmente necesita crear una "instancia de iterador" adicional. Normalmente, estos gastos generales son insignificantes si se hace algo sustancial en cada iteración.

Solo para proporcionar un ejemplo de cuánta sobrecarga impone un generador en comparación con un ciclo manual:

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def iteration(it):
    for i in it:
        pass

@bench.add_function()
def generator(it):
    it = (item for item in it)
    for i in it:
        pass

@bench.add_arguments()
def argument_provider():
    for i in range(2, 15):
        size = 2**i
        yield size, [1 for _ in range(size)]

plt.figure()
result = bench.run()
result.plot()

Generadores vs. listas de comprensión

Los generadores tienen la ventaja de que no crean una lista, "producen" los valores uno por uno. Entonces, mientras que un generador tiene la sobrecarga de la "clase de iterador", puede guardar la memoria para crear una lista intermedia. Es un intercambio entre velocidad (lista de comprensión) y memoria (generadores). Esto se ha discutido en varias publicaciones sobre , por lo que no quiero entrar en más detalles aquí.

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def generator_expression(it):
    it = (item for item in it)
    for i in it:
        pass

@bench.add_function()
def list_comprehension(it):
    it = [item for item in it]
    for i in it:
        pass

@bench.add_arguments(''size'')
def argument_provider():
    for i in range(2, 15):
        size = 2**i
        yield size, list(range(size))

plt.figure()
result = bench.run()
result.plot()

sum debe ser más rápida que la iteración manual

Sí, la sum es de hecho más rápida que un bucle explícito. Especialmente si iteras sobre enteros.

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def my_sum(it):
    sum_ = 0
    for i in it:
        sum_ += i
    return sum_

bench.add_function()(sum)

@bench.add_arguments()
def argument_provider():
    for i in range(2, 15):
        size = 2**i
        yield size, [1 for _ in range(size)]

plt.figure()
result = bench.run()
result.plot()

Métodos de cadena frente a cualquier tipo de bucle de Python

Para entender la diferencia de rendimiento cuando se usan métodos de cadena como str.count comparación con los bucles (explícitos o implícitos), las cadenas en Python se almacenan como valores en una matriz (interna). Eso significa que un bucle no llama a ningún método __next__ , puede usar un bucle directamente sobre la matriz, esto será significativamente más rápido. Sin embargo, también impone una búsqueda de método y una llamada de método en la cadena, por eso es más lento para números muy cortos.

Solo para proporcionar una pequeña comparación de cuánto tiempo se tarda en iterar una cadena en comparación con el tiempo que tarda Python en iterar sobre la matriz interna:

import matplotlib.pyplot as plt
from simple_benchmark import BenchmarkBuilder
%matplotlib notebook

bench = BenchmarkBuilder()

@bench.add_function()
def string_iteration(s):
    # there is no "a" in the string, so this iterates over the whole string
    return ''a'' in s  

@bench.add_function()
def python_iteration(s):
    for c in s:
        pass

@bench.add_arguments(''string length'')
def argument_provider():
    for i in range(2, 20):
        size = 2**i
        yield size, ''1''*size

plt.figure()
result = bench.run()
result.plot()

En este punto de referencia, es ~ 200 veces más rápido permitir que Python realice la iteración sobre la cadena que iterar sobre la cadena con un bucle for.

¿Por qué todos ellos convergen para grandes números?

Esto es en realidad porque la conversión de número a cadena será dominante allí. Entonces, para números realmente grandes, básicamente estás midiendo cuánto tiempo se tarda en convertir ese número en una cadena.

Verás la diferencia si comparas las versiones que toman un número y las convierten en una cadena con la que toma el número convertido (uso las funciones de otra respuesta aquí para ilustrar eso). Izquierda es el número de referencia y a la derecha es el punto de referencia que toma las cadenas, también el eje y es el mismo para ambas gráficas:

Como puede ver, los puntos de referencia para las funciones que toman la cadena son significativamente más rápidos para los números grandes que los que toman un número y los convierten en una cadena dentro. Esto indica que la conversión de cadena es el "cuello de botella" para grandes números. Para mayor comodidad, también incluí un punto de referencia que solo realiza la conversión de cadenas a la gráfica de la izquierda (que se vuelve significativa / dominante para números grandes)

%matplotlib notebook

from simple_benchmark import BenchmarkBuilder
import matplotlib.pyplot as plt
import random

bench1 = BenchmarkBuilder()

@bench1.add_function()
def f1(x):
    return sum(c in ''02468'' for c in str(x))

@bench1.add_function()
def f2(x):
    return sum([c in ''02468'' for c in str(x)])

@bench1.add_function()
def f3(x):
    return sum([True for c in str(x) if c in ''02468''])    

@bench1.add_function()
def f4(x):
    return sum([1 for c in str(x) if c in ''02468''])

@bench1.add_function()
def explicit_loop(x):
    count = 0
    for c in str(x):
        if c in ''02468'':
            count += 1
    return count

@bench1.add_function()
def f5(x):
    s = str(x)
    return sum(s.count(c) for c in ''02468'')

bench1.add_function()(str)

@bench1.add_arguments(name=''number length'')
def arg_provider():
    for i in range(2, 15):
        size = 2 ** i
        yield (2**i, int(''''.join(str(random.randint(0, 9)) for _ in range(size))))


bench2 = BenchmarkBuilder()

@bench2.add_function()
def f1(x):
    return sum(c in ''02468'' for c in x)

@bench2.add_function()
def f2(x):
    return sum([c in ''02468'' for c in x])

@bench2.add_function()
def f3(x):
    return sum([True for c in x if c in ''02468''])    

@bench2.add_function()
def f4(x):
    return sum([1 for c in x if c in ''02468''])

@bench2.add_function()
def explicit_loop(x):
    count = 0
    for c in x:
        if c in ''02468'':
            count += 1
    return count

@bench2.add_function()
def f5(x):
    return sum(x.count(c) for c in ''02468'')

@bench2.add_arguments(name=''number length'')
def arg_provider():
    for i in range(2, 15):
        size = 2 ** i
        yield (2**i, ''''.join(str(random.randint(0, 9)) for _ in range(size)))

f, (ax1, ax2) = plt.subplots(1, 2, sharey=True)
b1 = bench1.run()
b2 = bench2.run()
b1.plot(ax=ax1)
b2.plot(ax=ax2)
ax1.set_title(''Number'')
ax2.set_title(''String'')

Answer 2

La respuesta de @MarkusMeskanen tiene los bits correctos: las llamadas de función son lentas, y tanto genexprs como listcomps son básicamente llamadas de función.

De todos modos, para ser pragmático:

Usar str.count(c) es más rápido, y esta respuesta mía relacionada con strpbrk() en Python podría acelerar aún más las cosas.

def count_even_digits_spyr03_count(n):
    s = str(n)
    return sum(s.count(c) for c in "02468")


def count_even_digits_spyr03_count_unrolled(n):
    s = str(n)
    return s.count("0") + s.count("2") + s.count("4") + s.count("6") + s.count("8")

Resultados:

string length: 502
count_even_digits_spyr03_list 0.04157966522
count_even_digits_spyr03_sum 0.05678154459
count_even_digits_spyr03_for 0.036128606150000006
count_even_digits_spyr03_count 0.010441866129999991
count_even_digits_spyr03_count_unrolled 0.009662931009999999

Answer 3

Si usamos dis.dis() , podemos ver cómo se comportan realmente las funciones.

count_even_digits_spyr03_for() :

  7           0 LOAD_CONST               1 (0)
              3 STORE_FAST               0 (count)

  8           6 SETUP_LOOP              42 (to 51)
              9 LOAD_GLOBAL              0 (str)
             12 LOAD_GLOBAL              1 (n)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 GET_ITER
        >>   19 FOR_ITER                28 (to 50)
             22 STORE_FAST               1 (c)

  9          25 LOAD_FAST                1 (c)
             28 LOAD_CONST               2 (''02468'')
             31 COMPARE_OP               6 (in)
             34 POP_JUMP_IF_FALSE       19

 10          37 LOAD_FAST                0 (count)
             40 LOAD_CONST               3 (1)
             43 INPLACE_ADD
             44 STORE_FAST               0 (count)
             47 JUMP_ABSOLUTE           19
        >>   50 POP_BLOCK

 11     >>   51 LOAD_FAST                0 (count)
             54 RETURN_VALUE

Podemos ver que solo hay una llamada de función, que es str() al principio:

9 LOAD_GLOBAL              0 (str)
...
15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)

El resto es un código altamente optimizado, que utiliza saltos, tiendas y adiciones in situ.

Lo que viene a count_even_digits_spyr03_sum() :

 14           0 LOAD_GLOBAL              0 (sum)
              3 LOAD_CONST               1 (<code object <genexpr> at 0x10dcc8c90, file "test.py", line 14>)
              6 LOAD_CONST               2 (''count2.<locals>.<genexpr>'')
              9 MAKE_FUNCTION            0
             12 LOAD_GLOBAL              1 (str)
             15 LOAD_GLOBAL              2 (n)
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 GET_ITER
             22 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             25 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             28 RETURN_VALUE

Si bien no puedo explicar perfectamente las diferencias, podemos ver claramente que hay más llamadas a funciones (probablemente sum() y in (?)), Lo que hace que el código se ejecute mucho más lento que ejecutar las instrucciones de la máquina directamente.

Answer 4

Todas sus funciones contienen un número igual de llamadas a str(n) (una llamada) c in "02468" (para cada c en n). Desde entonces me gustaría simplificar:

import timeit

num = ''''.join(str(i % 10) for i in range(1, 10000001))

def count_simple_sum():
    return sum(1 for c in num)

def count_simple_for():
    count = 0
    for c in num:
        count += 1
    return count


print(''For Loop Sum:'', timeit.timeit(count_simple_for, number=10))
print(''Built-in Sum:'', timeit.timeit(count_simple_sum, number=10))

sum sigue siendo más lenta:

For Loop Sum: 2.8987821330083534
Built-in Sum: 3.245505138998851

La diferencia clave entre estas dos funciones es que en count_simple_for solo está iterando lanzar num con pure for loop for c in num , pero en count_simple_sum está creando un objeto generator aquí (de @Markus Meskanen responda con dis.dis ):

  3 LOAD_CONST               1 (<code object <genexpr> at 0x10dcc8c90, file "test.py", line 14>)
  6 LOAD_CONST               2 (''count2.<locals>.<genexpr>'')

sum está iterando sobre este objeto generador para sumar los elementos producidos, y este generador está iterando sobre elementos en num para producir 1 en cada elemento. Tener un paso más de iteración es costoso porque requiere llamar al generator.__next__() en cada elemento y estas llamadas se colocan en try: ... except StopIteration: bloque que también agrega cierta sobrecarga.

Answer 5

sum es bastante rápida, pero la sum no es la causa de la desaceleración. Tres factores principales contribuyen a la desaceleración:

• El uso de una expresión de generador genera una sobrecarga para pausar y reanudar constantemente el generador.
• La versión de su generador se agrega incondicionalmente en lugar de solo cuando el dígito es par. Esto es más caro cuando el dígito es impar.
• Agregar booleanos en lugar de ints evita que la sum use su ruta rápida de enteros.

Los generadores ofrecen dos ventajas principales sobre las listas de comprensión: toman menos memoria y pueden terminar antes si no se necesitan todos los elementos. No están diseñados para ofrecer una ventaja de tiempo en el caso de que todos los elementos sean necesarios. Suspender y reanudar un generador una vez por elemento es bastante costoso.

Si reemplazamos el genexp con una lista de comprensión:

In [66]: def f1(x):
   ....:     return sum(c in ''02468'' for c in str(x))
   ....: 
In [67]: def f2(x):
   ....:     return sum([c in ''02468'' for c in str(x)])
   ....: 
In [68]: x = int(''1234567890''*50)
In [69]: %timeit f1(x)
10000 loops, best of 5: 52.2 µs per loop
In [70]: %timeit f2(x)
10000 loops, best of 5: 40.5 µs per loop

vemos una aceleración inmediata, a costa de perder un montón de memoria en una lista.

Si te fijas en tu versión genexp:

def count_even_digits_spyr03_sum(n):
    return sum(c in "02468" for c in str(n))

Ya verás que no tiene if . Simplemente lanza booleanos en sum . En contraste, su bucle:

def count_even_digits_spyr03_for(n):
    count = 0
    for c in str(n):
        if c in "02468":
            count += 1
    return count

Solo agrega nada si el dígito es par.

Si cambiamos el f2 definido anteriormente para incorporar también un if , vemos otra aceleración:

In [71]: def f3(x):
   ....:     return sum([True for c in str(x) if c in ''02468''])
   ....: 
In [72]: %timeit f3(x)
10000 loops, best of 5: 34.9 µs per loop

f1 , idéntico a su código original, tomó 52.2 µs, y f2 , con solo el cambio de comprensión de la lista, tomó 40.5 µs.

Probablemente se veía bastante incómodo usando True lugar de 1 en f3 . Eso es porque cambiarlo a 1 activa una aceleración final. sum tiene una ruta rápida para enteros, pero la ruta rápida solo se activa para objetos cuyo tipo es exactamente int . bool no cuenta Esta es la línea que comprueba que los elementos son de tipo int :

if (PyLong_CheckExact(item)) {

Una vez que hacemos el cambio final, cambiando True a 1 :

In [73]: def f4(x):
   ....:     return sum([1 for c in str(x) if c in ''02468''])
   ....: 
In [74]: %timeit f4(x)
10000 loops, best of 5: 33.3 µs per loop

Vemos una última aceleración pequeña.

Entonces, después de todo eso, ¿superamos el bucle explícito?

In [75]: def explicit_loop(x):
   ....:     count = 0
   ....:     for c in str(x):
   ....:         if c in ''02468'':
   ....:             count += 1
   ....:     return count
   ....: 
In [76]: %timeit explicit_loop(x)
10000 loops, best of 5: 32.7 µs per loop

No Incluso hemos roto, pero no lo estamos superando. El gran problema que queda es la lista. Construirlo es caro, y la sum tiene que pasar por el iterador de la lista para recuperar elementos, que tiene su propio costo (aunque creo que esa parte es bastante barata). Desafortunadamente, mientras estemos en el enfoque de sum dígitos de prueba y de llamada, no tenemos ninguna buena manera de deshacernos de la lista. El bucle explícito gana.

¿Podemos ir más lejos de todos modos? Bueno, hemos estado tratando de acercar la sum al bucle explícito hasta ahora, pero si estamos atascados con esta lista de tontos, podríamos desviarnos del bucle explícito y simplemente llamar a len lugar de a la sum :

def f5(x):
    return len([1 for c in str(x) if c in ''02468''])

Probar dígitos individualmente no es la única forma en que podemos intentar superar el bucle, también. Divergiéndonos aún más del bucle explícito, también podemos intentar str.count . str.count itera sobre el búfer de una cadena directamente en C, evitando muchos objetos de envoltura e indirección. Necesitamos llamarlo 5 veces, haciendo 5 pases sobre la cadena, pero todavía vale la pena:

def f6(x):
    s = str(x)
    return sum(s.count(c) for c in ''02468'')

Desafortunadamente, este es el punto en el que el sitio que estaba usando para la sincronización me pegó en el "tarpit" por usar demasiados recursos, así que tuve que cambiar de sitio. Los siguientes tiempos no son directamente comparables con los tiempos anteriores:

>>> import timeit
>>> def f(x):
...     return sum([1 for c in str(x) if c in ''02468''])
... 
>>> def g(x):
...     return len([1 for c in str(x) if c in ''02468''])
... 
>>> def h(x):
...     s = str(x)
...     return sum(s.count(c) for c in ''02468'')
... 
>>> x = int(''1234567890''*50)
>>> timeit.timeit(lambda: f(x), number=10000)
0.331528635986615
>>> timeit.timeit(lambda: g(x), number=10000)
0.30292080697836354
>>> timeit.timeit(lambda: h(x), number=10000)
0.15950968803372234
>>> def explicit_loop(x):
...     count = 0
...     for c in str(x):
...         if c in ''02468'':
...             count += 1
...     return count
... 
>>> timeit.timeit(lambda: explicit_loop(x), number=10000)
0.3305045129964128