Projeto Euler p14 aprimora desempenho - python, performance, algoritmo

Eu terminei o projeto Euler problema 14 com o seguinte código:

def longest_Collatz_sequence():
"""
returns longest Collatz
sequence based on formula:
n --> n/2 (n is even)
n --> 3n + 1 (n is odd)
"""
bestSequence = []
lengthOfLongest = 0
longestSequence = []
for n in range(999999,1,-1):
while n != 1:
l = len(longestSequence)
if n % 2 == 0:
longestSequence.append(n)
n /= 2
elif n % 2 != 0:
longestSequence.append(n)
n = (n * 3) + 1
if longestSequence[-1] == 2 and lengthOfLongest < l:
lengthOfLongest = l
bestSequence = longestSequence[:]
bestSequence.append(1)
longestSequence = []
return bestSequence[0]

Demora cerca de 39 segundos para obter o maiorCollatz sequência de números de 1000000 para 2. Eu gostaria de saber se eu poderia colocar em cache todos os valores para acelerar o meu código, também como remove if longestSequence [-1] == 2 do meu código sem obter um loop infinito e quaisquer outras formas de melhorar o código.

A sequência iterativa a seguir é definida para o conjunto de inteiros positivos:

n → n / 2 (n é par) n → 3n + 1 (n é ímpar)

Usando a regra acima e começando com 13, geramos a seguinte sequência:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 PodeVeja-se que esta sequência (a partir de 13 e terminando em 1) contém 10 termos. Embora ainda não tenha sido provado (Problema de Collatz), acredita-se que todos os números iniciais terminem em 1.

Qual número inicial, abaixo de um milhão, produz a cadeia mais longa?

NOTA: Uma vez que a cadeia comece, os termos podem ultrapassar um milhão.

Respostas:

Cada vez que você gera um item na sequência, você também está gerando os itens para aquele item. Por exemplo, para 13, você descobre que ele produz 10 itens. Mas no processo você também descobre que 40 produz 9 itens, 20 produz 8 itens, 10 produz 7 itens, etc. Você pode se lembrar dessas informações em uma lista ou dicionário, de modo que depois de fazer 13, você nunca terá que olhar para 40 , 20, 10, 5, 16, 4 ou 2.

Além disso, quando você gera uma sequência vocênão visto antes, você pode olhar para esta informação e usá-la como um atalho. Para o 13, você já teria visto 10 antes de ver 13, então você calcula 40, 20, 10 e então você sabe que 10 produz 7 itens. você acabou de adicionar isso aos 3 que você já viu e não se incomodou em calcular o resto.

Isso vai usar um pouco de memória, mas é "stotalmente factível para o número de itens que você deve considerar. Você poderia ter algum tipo de corte (por exemplo, armazenar apenas os resultados para números de 100.000 ou menos), o que ainda teria uma grande melhoria de velocidade, mas usaria menos memória.

Uma maneira fácil de fazer isso é reescrever sua função para calcular a sequência recursivamente em vez de iterativamente e, em seguida, aplicar um decorador de memorização, como este. Há alguma sobrecarga na recursão, mas o benefício da memoização provavelmente superará isso.