Otimizando solução do problema 1 do site Project Euler (em Python)

Como estou organizando um grupo para participar de uma competição de programação na minha faculdade fiz um material para ajudar quem precisasse. E esse é um dos materiais que fiz. A ideia é otimizar a solução de vários exercícios relativamente fáceis. Como achei interessante o que escrevi decidi compartilhar aqui.

Caso queiram ver, criei um repositório para guardar esses materiais: repositório.

E obrigado para quem for ler.

O problema em questão é o problema 1 do site Project Euler. O comando que foi dado foi o seguinte:

Se listarmos todos os números naturais abaixo de 10 que são múltiplos de 3 ou 5, obtemos 3, 5, 6 e 9. A soma desses múltiplos é 23.

Encontre a soma de todos os múltiplos de 3 ou 5 abaixo de 1000.

• Valor Esperado: 233168
• Desafio Extra: E qual o resultado para os números abaixo de 1 milhão?
• Desafio Extra: E para números abaixo de 1 bilhão?

E agora começamos a resolver o problema:

Solução 1

Em uma primeira abordagem podemos pensar em percorrer todos os números entre 0 e 1000, verificando se são múltiplos de 3 ou 5, caso sejam, adicionamos o valor ao restante.

Começamos definindo uma variável para armazenar o valor da soma:

sum = 0

Em seguida fazemos um loop para percorrer todos os números de 1 até 999:

for number in range(1, 1000):
  # fazer alguma ação aqui

Obs: como 0 não influencia o resultado final podemos iniciar o loop a partir de 1 sem problemas.

Obs: a função range cria um array indo do valor inicial até o valor final menos 1, ou seja, o array resultante acima é [1,2,3,...,999]. Importante notar que a soma não inclui o valor limite (1000), somente entre os números 0 e 1000.

Agora para cada número que a repetição percorre verificamos se é múltiplo de 3 ou 5, caso seja, adicionamos ele à variável sum:

for number in range(1, 1000):
  if number % 3 == 0 or number % 5 == 0:
    sum += number

E para mostrar o resultado utilizamos a função print. O código final fica assim:

sum = 0

for number in range(1, 1000):
  if number % 3 == 0 or number % 5 == 0:
    sum += number

print(sum)

Solução 1.1

Algumas melhorias podem ser feitas no código que não influenciam na lógica, somente na estrutura e performance (em parte):

sum = sum(filter(lambda n: n % 3 == 0 or n % 5 == 0, range(1, 1000)))
print(sum)

No código acima fazemos exatamente o que foi feito na solução 1, porém de maneira mais performática, utilizando features mais atuais, são elas:

• Função filter: Como no código feito antes, ela percorre um array e verifica se alguma propriedade (função) é válida para cada elemento. Ela retorna por padrão um array com os valores filtrados. (Mais: Python's filter(): Extract Values From Iterables)
• Funções lambda: Também chamadas de funções anônimas, é um modo de minimizar a definição de funções simples. (Mais: How to Use Python Lambda Functions)

Nesse caso utilizamos uma função lambda para verificar se o número é múltiplo de 3 ou 5, e utilizamos o filter para selecionar os números do array range(1, 1000) ([1,...,999]) que obedecem essa propriedade.

Apesar da lógica ser a mesma, temos ganhos em performance, veja as métricas para o limite de 1.000.000 feitas utilizando o hyperfine:

Benchmark 1: ./solution1.py
  Time (mean ± σ):     413.9 ms ±  10.5 ms    [User: 407.8 ms, System: 4.2 ms]
  Range (min … max):   403.6 ms … 434.1 ms    10 runs

Benchmark 2: ./solution1.1.py
  Time (mean ± σ):     330.1 ms ±  12.2 ms    [User: 319.3 ms, System: 9.5 ms]
  Range (min … max):   314.0 ms … 354.6 ms    10 runs

Summary
  './solution1.1.py' ran
    1.25 ± 0.06 times faster than './solution1.py'

Pode parecer que é uma melhoria insignificante, porém quanto maior a quantidade de operações e a complexidade do programa, maior será a diferença de performances.

Solução 2

As solução 1 e 1.1, apesar de resolver o problema apresenta alguns problemas de performance quanto mais aumentamos o valor limite (1000 no caso). Quando variamos o limite o tempo de execução (número de operações) cresce de forma linear, o que denotamos por O(n).

Algumas métricas da solução 1 feitas também utilizando o hyperfine:

Benchmark 1: ./1000.py
  Time (mean ± σ):      34.2 ms ±   5.8 ms    [User: 26.9 ms, System: 6.9 ms]
  Range (min … max):    28.0 ms …  57.6 ms    66 runs

Benchmark 2: ./10000.py
  Time (mean ± σ):      37.6 ms ±   5.6 ms    [User: 30.2 ms, System: 6.9 ms]
  Range (min … max):    31.3 ms …  62.8 ms    62 runs

Benchmark 3: ./100000.py
  Time (mean ± σ):      74.0 ms ±   8.5 ms    [User: 65.5 ms, System: 7.9 ms]
  Range (min … max):    65.5 ms … 101.9 ms    39 runs

Benchmark 4: ./1000000.py
  Time (mean ± σ):     410.0 ms ±   9.8 ms    [User: 401.4 ms, System: 7.2 ms]
  Range (min … max):   393.6 ms … 430.9 ms    10 runs

Summary
  './1000.py' ran
    1.10 ± 0.25 times faster than './10000.py'
    2.16 ± 0.44 times faster than './100000.py'
   12.00 ± 2.05 times faster than './1000000.py'

Podemos resolver alguns dos problemas de performance utilizando uma outra abordagem. E se ao invés de percorrer todos os números de 1 até o limite, podemos percorrer somente aqueles que sabemos valer a condição (ser múltiplo de 3 ou 5).

Para isso podemos definir uma função auxiliar que percorre os números pulando aqueles que não são múltiplos do número:

def sum_multiples(number, limit):
  sum = 0
  for num in range(0, limit, number):
    sum += num
  
  return sum

Obs: Note que nesse método devemos iniciar com 0, pois a cada iteração somaremos o number, se iniciarmos de 1 estaríamos sempre um número adiantado, o que modificaria o valor final.

Com essa função podemos calcular a soma dos múltiplos de 3 e 5 de 1 até o limite 1000:

sum = sum_multiples(3, 1000) + sum_multiples(5, 1000)

Mas isso não resultará na resposta certa! Quando fazemos isso estamos somando alguns números repetidamente. Veja pelos diagramas:

Ou seja, estamos duplicado o valor da soma dos múltiplos de ambos, para resolvermos isso precisamos subtrair o valor duplicado. E quando falamos dos múltiplos de ambos estamos falando dos múltiplos de 15 (15=3\times5), assim, o programa final fica:

def sum_multiples(number, limit):
  sum = 0
  for num in range(0, limit, number):
    sum += num
  
  return sum

sum = sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)
print(sum)

Veja a diferença de performance comparada com a solução 1 para o limite 1.000.000:

Benchmark 1: ./solution1.py
  Time (mean ± σ):     415.1 ms ±  18.8 ms    [User: 407.1 ms, System: 6.7 ms]
  Range (min … max):   398.3 ms … 462.6 ms    10 runs

Benchmark 2: ./solution2.py
  Time (mean ± σ):      92.6 ms ±  12.5 ms    [User: 84.6 ms, System: 7.4 ms]
  Range (min … max):    81.4 ms … 123.1 ms    30 runs

Summary
  './solution2.py' ran
    4.48 ± 0.64 times faster than './solution1.py'

Uma melhoria de quase 4 vezes no tempo de execução.

Solução 2.1

Como na solução 1.1, podemos melhorar o código com features mais atuais:

sum_multiples = lambda number, limit: sum(range(0, limit, number))

sum = sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)
print(sum)

O que resulta de uma melhoria de aproximadamente 50% na performance para o limite 1.000.000:

Benchmark 1: ./solution2.py
  Time (mean ± σ):      90.7 ms ±   8.5 ms    [User: 82.3 ms, System: 7.5 ms]
  Range (min … max):    82.1 ms … 124.8 ms    32 runs

Benchmark 2: ./solution2.1.py
  Time (mean ± σ):      62.1 ms ±   5.7 ms    [User: 53.9 ms, System: 7.3 ms]
  Range (min … max):    56.0 ms …  90.8 ms    46 runs

Summary
  './solution2.1.py' ran
    1.46 ± 0.19 times faster than './solution2.py'

Solução 3

Existe ainda uma solução mais otimizada, porém faz uso de matemática. Ela se baseia no mesmo princípio da solução 2, porem descarta o loop e executa cálculos para resolver o problema.

Leve em consideração que:

Ou seja:

Obs: Soma dos termos de uma PA

Assim podemos modificar a função sum_multiples:

def sum_multiples(number, limit):
  sum = 0
  for num in range(0, limit, number):
    sum += num
  
  return sum

Essa função pode ser representada pela seguinte expressão:

s=number, l=limit

Obs: // é o operador de divisão inteira, resultando somente a parte inteira da divisão.

Note que l//s é o ultimo termo que o loop percorre, sendo o maior número inteiro que o loop é executado. Assim, essa expressão pode ser desenvolvida da seguinte forma:

Utilizando a formula da soma de uma PA:

f=l//s

Agora em código:

def sum_multiples(number, limit):
  final = limit // number
  return number * final * (final + 1) // 2

É bom lembrar que nesse caso não utilizaremos sum_multiples(..., 1000), já que a função não utiliza a função range mas sim matemática com os números dados. Nesse caso a solução ficaria:

def sum_multiples(number, limit):
  final = limit // number
  return number * final * (final + 1) // 2

sum = sum_multiples(3, 999) + sum_multiples(5, 999) - sum_multiples(15, 999)
print(sum)

Diferente das outras soluções, o tempo de execução da solução 3 não cresce de acordo com o valor de limite mas permanece mais ou menos constante, o que denotamos por O(1). Algoritmos classificados como O(1) são os mais eficientes.

Comparação

Em uma ultima análise temos os resultados de performance para o limite 1 milhão:

Benchmark 1: ./solution1.py
  Time (mean ± σ):     408.6 ms ±   5.6 ms    [User: 400.5 ms, System: 6.5 ms]
  Range (min … max):   400.5 ms … 417.6 ms    10 runs

Benchmark 2: ./solution1.1.py
  Time (mean ± σ):     321.4 ms ±   4.1 ms    [User: 312.7 ms, System: 7.2 ms]
  Range (min … max):   314.7 ms … 325.7 ms    10 runs

Benchmark 3: ./solution2.py
  Time (mean ± σ):      90.8 ms ±   6.9 ms    [User: 83.3 ms, System: 6.7 ms]
  Range (min … max):    82.8 ms … 115.7 ms    30 runs

Benchmark 4: ./solution2.1.py
  Time (mean ± σ):      60.5 ms ±   7.7 ms    [User: 54.0 ms, System: 6.1 ms]
  Range (min … max):    54.3 ms …  92.8 ms    43 runs

Benchmark 5: ./solution3.py
  Time (mean ± σ):      33.6 ms ±   5.2 ms    [User: 26.3 ms, System: 6.9 ms]
  Range (min … max):    27.4 ms …  56.3 ms    80 runs

Summary
  './solution3.py' ran
    1.80 ± 0.36 times faster than './solution2.1.py'
    2.70 ± 0.46 times faster than './solution2.py'
    9.58 ± 1.48 times faster than './solution1.1.py'
   12.17 ± 1.88 times faster than './solution1.py'

Como vemos, a solução 3 é aproximadamente 1220% vezes mais rápida que a solução 1.