Otimizando uma função de partição
Aqui está o código, em python:
# function for pentagonal numbers
def pent (n): return int((0.5*n)*((3*n)-1))
# function for generalized pentagonal numbers
def gen_pent (n): return pent(int(((-1)**(n+1))*(round((n+1)/2))))
# array for storing partitions - first ten already stored
partitions = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42]
# function to generate partitions
def partition (k):
if (k < len(partitions)): return partitions[k]
total, sign, i = 0, 1, 1
while (k - gen_pent(i)) >= 0:
sign = (-1)**(int((i-1)/2))
total += sign*(partition(k - gen_pent(i)))
i += 1
partitions.insert(k,total)
return total
Ele usa este método para calcular partições:
p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) ...
(fonte:Wikipedia)
No entanto, o código está demorando bastante quando se trata de números grandes (acima de p (10 ^ 3)). Quero perguntar se posso otimizar meu código ou sugerir um algoritmo ou abordagem diferente, mas mais rápido. Quaisquer sugestões de otimização são bem-vindas.
E não, antes que você pergunte, isso não é para trabalhos de casa ou Projeto Euler, é para o valor da experiência.