10

O código que estou utilizando é:

import time

def divisores(num):
    for i in range(1, int(num/2+1)):
        if num % i == 0: 
           yield i
    yield num

inicio = time.time()

d = divisores(47587950)
[print(i) for i in d]

print("Fim da execução: %s segundos" % round((time.time() - inicio),2))

O retorno: Fim da execução: 5.94 segundos. Esse código é lento.

Existe uma forma mais performática de calcular os divisores de um número usando Python?

0

4 Respostas 4

9

Dica: Não uses list comprehensions para executar funções como o print(), append() etc... vai criar-te uma lista temporária cheia de valores None, e tem implicações a nivel de performance se esta for muito grande, podes testar isto fazendo print(print('hey')) cujo print exterior vai imprimir o retorno do print interior (que é None), REF.

Em relação à performance não há muito a fazer e a tua implementação em grande parte está bem feita:

Maneira 1:

def divisores(num):
    for i in range(1, num//2+1):
        if num % i == 0: 
            yield i
    yield num

num = 47587950
print(list(divisores(num)))

Maneira 2:

num = 47587950
print([i for i in range(1, num//2+1) if num%i==0])

Quanto à performance a primeira maneira consegue ser um pouco mais rápida, e se não transformares em lista é praticamente instantâneo:

DEMONSTRAÇÃO

Na demonstração acima:

  • usando a maneira 1 temos um tempo de 1.7259 secs
  • usando a maneira 2 demoramos 1.9021 secs

Lembrando que no teu computador deve correr mais depressa do que no Ideone.

Usando a função da Maneira 1 o mais indicado para imprimires um de cada vez seria:

...
num = 47587950
for d in divisores(num):
    print(d)
2
  • Por quê eliminar a linha yield num sendo que o próprio número é divisor dele mesmo? O mesmo deve constar no retorno da função também.
    – Woss
    Commented 26/03/2017 às 13:36
  • Ha que parvoíce, é verdade, se for para incluir ele mesmo claro que sim. Obrigado pelo reparo @AndersonCarlosWoss
    – Miguel
    Commented 26/03/2017 às 13:37
9

Sim, dá para otimizar bastante.

Se você encontrou um divisor, então na verdade encontrou - na maioria dos casos - dois. Por exemplo, se o número for 100 e eu encontrei o divisor 2, então eu também encontrei o divisor 50 (resultado de 100 / 2). Com isso eu economizo uma iteração do for para cada divisor encontrado.

A única exceção é quando o número é um quadrado perfeito: se o número for 100 e eu encontrei o divisor 10, não posso considerar que 100 / 10 é outro divisor, senão estarei contando o 10 duas vezes.

Outro detalhe é que, fazendo desta forma, a iteração pode ir até a raiz quadrada do número, em vez de ir até a metade. Pois se um determinado número n possui divisores, então ele pode ser escrito como o produto a * b (sendo que a e b são divisores de n). Se ambos (tanto a quanto b) forem maiores que a raiz quadrada de n, então a * b seria maior que n, por isso um deles tem que ser menor que a raiz quadrada. Então se eu encontrei um deles (o menor que a raiz quadrada), também já encontrei o maior, como já descrito acima. Por isso o loop pode ir até a raiz quadrada.

Ficaria assim:

from math import sqrt

def divisores(num):
    yield 1 # 1 é divisor de qualquer número
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            yield i # encontrei um divisor
            outro_divisor = num // i
            if outro_divisor != i: # não é quadrado perfeito
                yield outro_divisor # retorna o outro divisor
    yield num # o próprio número é divisor dele mesmo

Um detalhe é que os divisores não estarão em ordem crescente, mas aí bastaria ordená-los (sorted(divisores(num))).


Fazendo um teste com o módulo timeit e comparando com as soluções das outras respostas:

# loop simples (testa um a um)
def divisores(num):
    for i in range(1, num // 2 + 1):
        if num % i == 0: 
            yield i
    yield num

# otimizado (conforme descrição acima)
from math import sqrt
def divisores_otimizado(num):
    yield 1 # 1 é divisor de qualquer número
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            yield i
            outro_divisor = num // i
            if outro_divisor != i:
                yield outro_divisor
    yield num

# numpy, sugestão de uma das respostas
import numpy as np
def divisores_numpy(num):
    n = np.arange(1,num)
    d = num % n
    zeros = d == 0
    return n[zeros]

from timeit import timeit

# executa 1 vez cada teste
params = { 'number' : 1, 'globals': globals() }

num = 47587950
# loop simples
print(timeit('for _ in divisores(num): pass', **params))
# numpy
print(timeit('for _ in divisores_numpy(num): pass', **params))
# meu código
print(timeit('for _ in divisores_otimizado(num): pass', **params))
# meu código, porém ordenando o resultado
print(timeit('for _ in sorted(divisores_otimizado(num)): pass', **params))

O timeit retorna o tempo em segundos, e claro que ele varia de uma máquina para outra, pois depende de vários fatores (hardware, se havia outras coisas rodando na máquina, etc). Mas enfim, na minha eu obtive resultados próximos disso:

3.7604584
0.2803169999999997
0.0007887000000001976
0.0007956000000000074

Ou seja, o loop simples que testa um por um demorou mais de 3 segundos, o numpy demorou menos que 3 décimos de segundo, e o meu código demorou menos que 800 microssegundos (ou seja, menos que 0,8 milissegundos). A versão que ordena os divisores foi um pouco mais lenta, mas como a lista de divisores é pequena (no caso, tem apenas 36 números), a ordenação não interfere tanto no resultado final (houve um aumento de poucos microssegundos).

Ou seja, esta solução (seja ordenando ou não) foi por volta de 4700 vezes mais rápida do que o loop simples e cerca de 350 vezes mais rápida que o numpy. Testando no IdeOne.com e no Repl.it, os tempos mudam, mas os resultados são similares: numpy mais lento, e o loop simples muito mais lento ainda (obs: no Repl.it tive que testar com um número menor porque o numpy estava aparentemente estourando a memória).


A diferença é grande porque quanto maior o número em questão, maior é a diferença entre a quantidade de iterações feitas. No caso, o número é 47587950 (mais de 47 milhões). O loop simples vai até a metade do número, portanto são feitas mais de 23 milhões de iterações. Já o algoritmo otimizado vai até a raiz quadrada do número, fazendo apenas 6898 iterações - ou seja, cerca de 3400 vezes menos iterações.

E quanto maior o número, mais essa diferença aumenta (por exemplo, se o número for 100 milhões, serão 50 milhões de iterações no loop simples contra 10 mil iterações no otimizado - cerca de 7200 vezes menos iterações). E no caso do numpy, por mais rápido que ele seja, ainda está sendo criado um array com milhões de elementos e iterando por todos, por isso também é mais lento.

De forma geral, os outros algoritmos possuem complexidade O(n) (chamada de linear), enquanto que o algoritmo acima possui complexidade O(n1/2) (também chamada de sub-linear). Por isso a quantidade de operações cresce bem menos (proporcionalmente ao tamanho da entrada) se comparado com os algoritmos das outras respostas. Usando o exemplo dos parágrafos acima, ao usar um número cerca de 2 vezes maior (ou seja, aumentei de 47 milhões para 100 milhões), as iterações do algoritmo otimizado aumentam apenas cerca de 45%. Sem contar, é claro, a quantidade total de iterações com relação ao número original, que faz com que a diferença de desempenho seja tão grande.

2

Numpy nasceu para isso:

import numpy as np
import time

def divisores(num):
    n = np.arange(1,num)
    d = num % n
    zeros = d == 0
    print (n[zeros])

inicio = time.time()
divisores(47587950)
print("Fim da execução: %s segundos" % round((time.time() - inicio),2))  

Saida:

[       1        2        3        5        6        9       10       15
       18       25       30       45       50       75       90      150
      225      450   105751   211502   317253   528755   634506   951759
  1057510  1586265  1903518  2643775  3172530  4758795  5287550  7931325
  9517590 15862650 23793975]  
Fim da execução: 0.99 segundos

Levou 0.99 segundos aqui.

1
  • E acho que demorou é muito. Mas meu notebook anterior quebrou e tive que comprar um bem no dólar disparado (2015) então comprei uma carroça.
    – user1084
    Commented 26/03/2017 às 16:14
-1
a = 1
num = int(input("Digite o número: "))
while a <= num:
    x = num % a
    a = a +1
    if x == 0:
        print (a-1)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .