Ruby - ハッシュを使ってCollat​​zのシーケンスを解く

Question

私はアルゴリズムを解くのにはとても新しいので、私に負担をかけてください。

私は、最大長が1,000,000のCollat​​zシーケンスを解決しましたが、ハッシュテーブルを使用して関数を高速化するために既に存在するキーを検索することで効率を上げたいと考えています。しかし、何かが間違っているのは分かっています。なぜなら、数字が1,000,000に達するのに1〜2秒しかかからないはずですが、それでも実行には9〜10秒かかります。私はアルゴリズムでハッシュテーブルを使用することにかなり新しいので、誰かが私の方法で間違ってやっていることを教えてくれますか？

非常に高く評価されました！

def collatz(n) 
    chain = 1 
    until n == 1 
    n = (n.even?) ? (n/2) : (n*3+1) 
    chain += 1 
    end 
    chain 
end 

def longest_chain2(number) 
    cache = { 1 => 1 } 
    start_num = 1 
    longest = 1 
    while start_num < number 
    chain = cache[start_num] 
    if chain > longest 
     longest = chain 
     longest_start = start_num 
    end 
    start_num += 1 
    cache[start_num] = collatz(start_num) 
    end 
    return longest_start 
end 

puts longest_chain2(1000000) 

Answer 1

全体の夜に私の脳をラッキングした後、私は全体を再加工し、各ステップの道のすべてのステップを書いて、私の根本的な問題は、私は（前からcollat​​zのメソッドを呼び出すことができないことに気づきましたそのメソッドはチェーン全体を計算しますが、私がすでに計算した数で停止する必要があります）。そこで、以下の私のソリューションです：

def longest_chain2(number) 
    cache = { 1 => 1 } 
    start_num = 1 
    longest = 1 
    while start_num < number 
    n = start_num 
    chain = 0 
    while n != 1 && n >= start_num 
     if n.even? 
     n = n/2 
     else 
     n = 3*n+1 
     end 
     chain += 1 
    end 
    chain += cache[n] 
    if chain > longest 
     longest = chain 
     longest_start = start_num 
    end 
    cache[start_num] = chain 
    start_num += 1 
    end 
    return longest_start 
end 

この方法で、私はその時点まで連鎖数アップに追加し、[n]はキャッシュの値を呼びかけながら、既に存在しないキーを追加することがあります。