LLRing

お待たせしました！
キミならどう書く 2.0 ROUND 2の開催です！！

面白そうだったのでこっそり参戦。
自力で素晴らしいコードを書く自信はないので、とりあえず自分で考えてみてから、他の方々のソースコードを読んで勉強しようという目論見です。

関数型のお題ということで、確かに関数型言語と相性が良さそうな問題ですが、残念ながら俺は関数型言語があまり扱えません。なので、Lightweight LanguageということでPHPで書いてみます。

まずはそのまま、ごり押しで書いてみる。

<?php
  function g($n) {
    if ($n == 1)
      return 1;
    
    if (($n % 2) == 0)
      return (g($n/2)+1);
    
    return (g(3*$n+1)+1);
  }
  
  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;
  }
?>

呼び出し側はこんな感じで書いておきますか。

<?php
  $n = 100;
  
  $start = time();
  $k = h($n);
  $end = time();
  print("h(" . $n . ")=" . $k . "<br />\n");
  print("g(" . $k . ")=" . g($k) . "<br />\n");
  print("exec_time=" . ($end - $start) . "(s)\n");
?>

工夫の欠片も感じられないコードではあるものの、それなりにまともに動いてるような気がする。さすがに秒オーダーにはならない。(CPU 2GHz, RAM 512MB) 10,000くらいで数秒なので、耐えられないレベルでもないんじゃないでしょうか。駄目？あ、そう。

じゃあまぁこっからどうしようかという話なんですが。
とりあえずパッと思いついたので、
『これまでに計算したf(n)の結果をすべて配列に保存しておく』
ように組みなおす。
うまくいけば再帰呼び出しをずいぶん減らせないだろうか。
メモリを膨大に喰ってしまう予感に怯えつつ実装。

<?php
  $ans = array(0);
  $length;
  
  function g($n) {
    global $ans;
    global $length;
    
    if ($n == 1) {
      $ans[1] = 1;
      return 1;
    }
    
    if ($ans[$n] != 0) {
      return $ans[$n];
    }
    
    if (($n % 2) == 0) {
      $ans[$n] = g($n/2) + 1;
      return $ans[$n];
    }
    
    $next = (3 * $n) + 1;
    if ($next > $length) {
      $length = $next;
      $ans = array_pad($ans, $length, 0);
    }
    
    $ans[$n] = g($next) + 1;
    return $ans[$n];
  }
  
  function h($n) {
    $length = $n;
    $ans = array_fill(0, $length, 0);
    $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;
  }
?>

あーなんか美しくない。
実行してみたものの無残なもんです。
再帰呼び出し自体は多少省略されるもののちっとも早くなんかなりゃしない。
それどころかおもいっきし伸びた。てか配列のサイズが半端ない。まぁそこは予想通りですが。10,000とかでもう数分オーダーでは話にならないです。

結局シンプルイズベストを全く超えられないままちょっとあきらめ気味。しょぼすぎるな。
まぁこれからいろんな人のコードを見て勉強します。