LL Ring〜キミならどう書く 2.0 - ROUND 2 - 追記

他の参加者のコードをいろいろ読んでみました。
いやー勉強になりますね。

やっぱり俺のコードはどうにも無駄が多すぎました。
意外にも方針はそんな間違ってなかったんだけどねぇ。
というか、それほどアルゴリズム的な改良の余地はないようで。
皆さん、細かく高速化を図ってみたり、コードを短くしてみたりといった感じです。

そんなわけで、いろんなコードを参考に組みなおしました。

まずは前回の「キャッシュを使えば早くなると思ったんだけどむしろ伸びた」コードに含まれてた明らかな無駄の項を削除しました。
それだけでもうずいぶん早くなりましたよ。

<?php
  $ans = array(0);
  
  function g($n) {
    global $ans;
    
    if ($n == 1) {
      $ans[1] = 1;
      return 1;
    }
    
    if (isset($ans[$n])) {
      return $ans[$n];
    }
    
    if ($n & 1) {
      $ans[$n] = g(3*$n+1) + 1;
      return $ans[$n];
    }
    
    $ans[$n] = g($n/2) + 1;
    return $ans[$n];
  }
  
  function h($n) {
    $max_g = 1;
    $max_k = 1;
    
    for ($i=1; $i<=$n; $i++) {
      if (($tmp = g($i)) > $max_g) {
        $max_g = $tmp;
        $max_k = $i;
      }
    }
    
    return $max_k;
  }
?>

このコードで実行すると1,000,000に対して10数秒。もうなんか満足。
ちなみに現在再現できた最速のコードでもオーダーとしては同程度。
再帰関数として定義していたg()をh()の中にwhile文で展開した。
関数呼び出しがなくなるおかげでずいぶん早くなってるんじゃないかと思うんですが、キャッシュの利用がやや非効率になるのでトータルとしては1,000,000相手に数秒程度の改善。この程度なら上のコードの方が個人的には好きですねぇ。

<?php
  function h($n) {
    $ans = array();
    $max_g = 1;
    $max_k = 1;
    
    for ($i=1; $i<=$n; $i++) {
      $count = 1;
      $current = $i;
      while($current != 1) {
        $current = (($current & 1) ? (3 * $current + 1) : ($current / 2));
        if (isset($ans[$current])) {
          $count += $ans[$current];
          break;
        }
        $count++;
      }
      if (($ans[$i] = $count) > $max_g) {
        $max_g = $count;
        $max_k = $i;
      }
    }
    
    return $max_k;
  }
?>