コラッツ逆展開

http://ll.jus.or.jp/2006/blog/doukaku2 の話。3回目。
g:haskell:id:jmk:20060712:1152721034 でやっていた逆展開を私もやってみる。
ただし、そのまんまやると h(100)の計算が終わらないようなので、終わるように工夫して：

def collatz( n )
  done=3 # 1,2,4 は計算済みとする
  wait=[ [8,4] ] # 1,2,4 に入れるのは 8 だけ

  def wait.special_insert a # 二分探索で整列しつつ挿入
    r=[0,size]
    while r[0]+1<r[1] do
      m=( r[0]+r[1] )/2
      r[ -self[m][0] <= -a[0] ? 0 : 1 ] = m
    end
    insert( r[ self.empty? || -a[0] <= -self[r[0]][0] ? 0 : 1 ], a )
  end

  while done<n
    a = wait.pop
    if a[0]<=n then
      done+=1
      max = a if !max || max[1]<a[1]
    end
    wait.special_insert [ a[0]*2, a[1]+1 ]
    wait.special_insert [ (a[0]-1)/3, a[1]+1 ] if 3==(a[0]-1)%6
  end

  max[0]
end

p collatz(100)

これで、手元の処理系で collatz(100) は1秒未満。1000 でも現実的な時間で終わる。10000 は試してない。
C++ の std::set のような、ソート済み配列が ruby にはないのでそれも実装する必要があったのが面倒だった。
std::set のためだけに C++ で書こうかとも思ったが、やっぱり ruby にした。
最初は挿入関数を書かずに push してから sort! していたんだが、やっぱりそれはあんまりだと思ってちゃんと書いた。そしたら劇的に速くなった。当たり前。

1,2,4 を計算済みにしている関係で、 引数の値が 3以下だとうまくいかない。まあドンマイということで。