コラッツの問題その3

まだやってたのかって感じだけど、たぶんこれが最速。

まず、こういうものを定義します。

macro collatz_calc {
  case { _ ($from:lit, $to:lit) } => {
    var from = unwrapSyntax(#{$from}),
        to = unwrapSyntax(#{$to}),
        max = 0,
        val, result;

    function collatz(n){
      var m = n, count = 0;

      while(m !== 1){
        count++;
        m = (m & 1) ? (m<<1)+m+1 : m >> 1;
      }

      return count;
    }

    for(var i=from; i<=to; i++){
      val = collatz(i);
      if(val > max){ max = val; result = i; }
    }

    letstx $result = [makeValue(result, #{here})];
    return #{
      $result
    }
  }
}
export collatz_calc

使います。

console.time('xxx');
console.log(collatz_calc(2, 100000));
console.timeEnd('xxx');

コンパイルします。

console.time('xxx');
console.log(77031); // 77031
console.timeEnd('xxx'); // xxx: 1ms (Node でこれでブラウザだと 0.5ms)

実行すると 1ms という最速記録を作ることが出来ました。

解説というか説明というか

そもそも Lisp やってたりするとマクロというものに一度は触れると思いますが、考え方はそこです。マクロの強みのひとつとして、コンパイルした際に展開したり計算したりということが出来るので、値が固定されると分かっている場合はコンパイル時に計算してしまえばいいというわけ。というわけで今回みたいに計算式が定まっていて、範囲も決まっている場合はこういうズルが出来るのです(ぉ
ちなみにコンパイルの時間が多少伸びるし、実行時の計算をコンパイル時に肩代わりしているだけというのは言うまでもないことですが、まぁ今回はありでしょう！
今回は sweet.js を使いましたが、普通に一般的な Lisp 系はこういうことが出来るので素晴らしいですね！