Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Encontrando múltiplos de 3 cujo último dígito é 1: loops vs list comprehension

+1 voto
55 visitas
perguntada Set 8, 2020 em Programação Computacional por Felipe Yudi (46 pontos)  

Faça um loop para encontrar todos os múltiplos de 3 cujo último algarismo é 1 no intervalo [0,n]. Compare o tempo de execução de um loop convencional com um loop usando list comprehensions.

Compartilhe

1 Resposta

0 votos
respondida Set 8, 2020 por Felipe Yudi (46 pontos)  

A estratégia é primeiro checar se o número é múltiplo de 3 e depois verificar seu último algarismo. Se ele for igual a 1, o colocamos em uma lista. Caso contrário, o ignoramos.

Vamos usar o módulo time para medir o tempo de execução.

import time

def com_loop(n):
    lst=[]
    for i in range(n+1):
        if i%3 == 0:
            if int(repr(i)[-1]) == 1:
                lst.append(i)
    return lst

def com_compr(n):
    return [i for i in range(n+1) if i%3==0 and int(repr(i)[-1]) == 1]

if __name__=="__main__":

    #Com loop
    start_a = time.time()
    a = com_loop(1000000)
    end_a = time.time()
    print("Tempo com loop:", end_a-start_a)

    #Com list comprehension
    start_b = time.time()
    b = com_compr(1000000)
    end_b = time.time()
    print("Tempo com list comprehension:", end_b-start_b)

No meu caso, a função comloop demorou 0,22 segundos para encontrar os números requeridos. Já a função comcompr demorou 0.17 segundos. Como esperado, list comprehension foi mais rápida que o loop.

comentou Dez 7, 2020 por Athos Carvalho (31 pontos)  
Além da complexidade temporal, podemos testar a complexidade espacial das duas implementações, utilizando a biblioteca memory_profiler.

Para quem utiliza o kernel IPython, é possível utilizar a biblioteca no jupyter notebook com as seguintes magics:

%load_ext memory_profiler

%memit com_loop(1000000)
%memit com_compr(1000000)

Os resultados que obtive foram:

Para a função com_loop
peak memory: 57.35 MiB, increment: 0.53 MiB

Para a função com_compr
peak memory: 57.02 MiB, increment: 0.14 MiB

Apesar de grande parte das vezes a complexidade temporal não ser um fator limitante, é interessante notar que parece haver, pelo menos para o caso analisado, um ganho no uso de memória ao utilizar list comprehensions, além do já mostrado ganho temporal.
...