python Por que um loop for for muito mais rápido para contar os valores True?



python-3.x performance (4)

Recentemente, respondi a uma pergunta em um site de irmã que solicitou uma função que conta todos os dígitos pares de um número. Uma das outras respostas continha duas funções (o que acabou por ser o mais rápido, até agora):

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

Além disso, olhei para usar uma lista de compreensão e list.count :

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

As duas primeiras funções são essencialmente as mesmas, exceto que a primeira usa um loop de contagem explícita, enquanto a segunda usa a sum incorporada. Eu teria esperado que o segundo fosse mais rápido (baseado, por exemplo, nessa resposta ), e é no que eu recomendaria que ele se transformasse se fosse solicitada uma revisão. Mas acontece que é o contrário. Testando-o com alguns números aleatórios com o aumento do número de dígitos (então a chance de que um único dígito seja par é de cerca de 50%) eu recebo os seguintes horários:

Por que o manual for loop é muito mais rápido? É quase um fator dois mais rápido que usar sum . E como a sum deve ser cerca de cinco vezes mais rápida do que a soma manual de uma lista (conforme a resposta vinculada ), isso significa que ela é na verdade dez vezes mais rápida! A poupança é apenas ter que adicionar uma ao contador para metade dos valores, porque a outra metade é descartada, o suficiente para explicar essa diferença?

Usando um if como um filtro assim:

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

Melhora o tempo apenas para o mesmo nível que a compreensão da lista.

Ao estender os timings para números maiores, e normalizar para o tempo do loop for , eles assintoticamente convergem para números muito grandes (> 10k dígitos), provavelmente devido ao tempo que str(n) leva:


Existem algumas diferenças que realmente contribuem para as diferenças de desempenho observadas. Eu pretendo dar uma visão geral de alto nível dessas diferenças, mas tente não ir muito aos detalhes de baixo nível ou possíveis melhorias. Para os benchmarks eu uso meu próprio pacote simple_benchmark .

Geradores vs. loops for

Geradores e expressões geradoras são açúcares sintáticos que podem ser usados ​​em vez de escrever classes de iteradores.

Quando você escreve um gerador como:

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

Ou uma expressão geradora:

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

Isso será transformado (nos bastidores) em uma máquina de estado acessível por meio de uma classe de iteradores. No final, será aproximadamente equivalente a (embora o código real gerado em torno de um gerador seja mais 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'

Então, um gerador sempre terá uma camada adicional de indireção. Isso significa que avançar o gerador (ou expressão geradora ou iterador) significa que você chama __next__ no iterador que é gerado pelo próprio gerador que chama __next__ no objeto que você realmente deseja iterar. Mas também tem alguma sobrecarga porque você realmente precisa criar uma "instância de iterador" adicional. Normalmente, essas despesas gerais são insignificantes se você fizer algo substancial em cada iteração.

Apenas para fornecer um exemplo de quanto sobrecarga um gerador impõe comparado a um loop 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()

Geradores vs. Compreensões de lista

Os geradores têm a vantagem de não criar uma lista, eles "produzem" os valores um a um. Assim, enquanto um gerador tem a sobrecarga da "classe iteradora", ele pode salvar a memória para criar uma lista intermediária. É um trade-off entre velocidade (compreensão da lista) e memória (geradores). Isso foi discutido em vários posts do , então não quero entrar em mais detalhes aqui.

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 deve ser mais rápida que a iteração manual

Sim, a sum é realmente mais rápida do que um loop for explícito. Especialmente se você iterar sobre inteiros.

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 string versus qualquer tipo de loop de Python

Para entender a diferença de desempenho ao usar métodos de strings como str.count comparação com loops (explícito ou implícito) é que as strings em Python são realmente armazenadas como valores em uma matriz (interna). Isso significa que um loop na verdade não chama nenhum método __next__ , ele pode usar um loop diretamente sobre o array, isso será significativamente mais rápido. No entanto, também impõe uma pesquisa de método e uma chamada de método na string, por isso é mais lento para números muito curtos.

Apenas para fornecer uma pequena comparação quanto tempo leva para iterar uma string versus quanto tempo leva Python para iterar sobre a 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()

Nesse benchmark é ~ 200 vezes mais rápido deixar o Python fazer a iteração através da string do que iterar pela string com um loop for.

Por que todos eles convergem para números grandes?

Na verdade, isso ocorre porque o número para a conversão de sequências será dominante. Então, para números realmente altos, você está basicamente medindo quanto tempo leva para converter esse número em uma string.

Você verá a diferença se comparar as versões que pegam um número e convertê-lo em uma string com a que pega o número convertido (eu uso as funções de outra resposta aqui para ilustrar isso). Esquerda é o benchmark de números e à direita é o benchmark que leva as strings - também o eixo y é o mesmo para ambos os gráficos:

Como você pode ver, os benchmarks para as funções que levam a string são significativamente mais rápidos para números maiores que os que pegam um número e os convertem em uma string dentro. Isso indica que a conversão de string é o "gargalo" para números grandes. Por conveniência, também incluí um benchmark fazendo apenas a conversão de string para o gráfico da esquerda (que se torna significativo / 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')

sum é bastante rápida, mas a sum não é a causa da desaceleração. Três fatores principais contribuem para a desaceleração:

  • O uso de uma expressão de gerador causa sobrecarga para pausar constantemente e retomar o gerador.
  • Sua versão do gerador adiciona incondicionalmente, em vez de apenas quando o dígito é par. Isso é mais caro quando o dígito é ímpar.
  • Adicionar booleanos em vez de ints evita que a sum use seu caminho rápido de inteiro.

Os geradores oferecem duas vantagens primárias sobre as compreensões de lista: elas ocupam muito menos memória e podem terminar cedo, se nem todos os elementos forem necessários. Eles não são projetados para oferecer uma vantagem de tempo no caso em que todos os elementos são necessários. Suspender e retomar um gerador uma vez por elemento é muito caro.

Se substituirmos o genexp por uma compreensão de lista:

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 uma aceleração imediata, ao custo de desperdiçar um monte de memória em uma lista.

Se você olhar para a sua versão genexp:

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

você verá que não tem if . Apenas joga booleanos em sum . Em contraste, o seu loop:

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

só adiciona qualquer coisa se o dígito for par.

Se mudarmos o f2 definido anteriormente para também incorporarmos um if , vemos outro aumento de velocidade:

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 ao seu código original, levou 52,2 µs, e f2 , com apenas a mudança de compreensão da lista, levou 40,5 µs.

Provavelmente parecia bastante estranho usando True vez de 1 em f3 . Isso porque mudá-lo para 1 ativa uma aceleração final. sum tem um caminho rápido para números inteiros, mas o caminho rápido é ativado apenas para objetos cujo tipo é exatamente int . bool não conta. Esta é a linha que verifica se os itens são do tipo int :

if (PyLong_CheckExact(item)) {

Assim que fizermos a alteração final, alterando True para 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 uma última pequena aceleração.

Então, depois de tudo isso, nós vencemos o loop 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

Não. Nós quase quebramos mesmo, mas não estamos batendo. O grande problema restante é a lista. Construí-lo é caro, e a sum tem que passar pelo iterador de lista para recuperar elementos, o que tem seu próprio custo (embora eu ache que essa parte é bem barata). Infelizmente, contanto que estejamos passando pela abordagem de teste de dígitos e sum chamadas, não temos nenhuma boa maneira de nos livrarmos da lista. O loop explícito vence.

Podemos ir mais longe de qualquer maneira? Bem, estamos tentando aproximar a sum do loop explícito, mas se estamos presos a essa lista burra, podemos divergir do loop explícito e apenas chamar len vez de sum :

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

Testar dígitos individualmente não é a única maneira de tentarmos vencer o loop também. Divergindo ainda mais do loop explícito, também podemos tentar str.count . str.count itera sobre o buffer de uma string diretamente em C, evitando muitos objetos wrapper e indiretos. Precisamos ligar 5 vezes, fazendo 5 passes na sequência, mas ainda vale a pena:

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

Infelizmente, este é o ponto em que o site que eu estava usando para o tempo me colocou no "tarpit" por usar muitos recursos, então eu tive que trocar de site. Os seguintes horários não são diretamente comparáveis ​​com os horários acima:

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

Se usarmos dis.dis() , podemos ver como as funções realmente se comportam.

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 há apenas uma chamada de função, que é str() no começo:

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

O restante é um código altamente otimizado, usando saltos, armazenamentos e adição in-loco.

O que vem para 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

Embora eu não possa explicar perfeitamente as diferenças, podemos ver claramente que há mais chamadas de função (provavelmente sum() e in (?)), Que fazem o código rodar muito mais lento do que executar as instruções da máquina diretamente.


@ Resposta MarkusMeskanen tem os bits certos - chamadas de função são lentas, e ambos os genexprs e listcomps são basicamente chamadas de função.

De qualquer forma, para ser pragmático:

Usar str.count(c) é mais rápido, e essa minha resposta relacionada sobre o strpbrk() no Python pode tornar as coisas ainda mais rápidas.

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




sum