コラッツの問題

• 11月16日いろふうらがみ迎撃会 - connpass

なんとなく久しぶりに id:irof せんせーに会いたくなったので、重たい腰をあげて行ってきた。なんか Twitter 見てない間に irof せんせーが本を書いてたらしい。
というか、参加登録した後に、イベント主旨が若干変わってて前日になって行きたくなくなったのは内緒。

お酒を軽く入れてテンション高くなって、そのままの勢いでわけの分からない LT したりと失態を犯しつつ、まぁそれなりに楽しかったのかなーと。
それはそれとして、「コラッツの問題」というのがあるのですが、それにまつわる問題を id:syobochim がその場で解いていた(正確に言うとうらがみさんなんだけど)ので、ちょっと僕も解いてみた。

まず問題ですね。

2 ~ 100000 の数でコラッツの問題を 1 になるまで続けたときにでてくるステップ数が一番大きい数字を求めよ。

で、これを実行したときの実行時間を何処まで小さく出来るかという遊び。うらがみさんは Java で 80ms という数字を最初に出していたのでそれよりも小さくするということを最初の目標とした。ちなみに Java 以外の言語で挑戦することにした、つまり JavaScript です。

まず、オーソドックスに書いてみる。

console.time('xxx');

var _ = require('underscore');
var ary = _.range(2, 100001);

function collatz(n){
  return (function inner(m){
    if(m === 1){ return 0; }
    var x = (m % 2 === 0) ? m/2 : m*3+1;
    return inner(x) + 1;
  })(n);
}

var result = _.chain(ary).
      map(function(n){ return [n, collatz(n)]; }).
      max(function(x){ return x[1]; }).
      value();

console.log(result[0]); // 77031

console.timeEnd('xxx'); // xxx: 450ms

無難に underscore.js 使いました。が、このタイムは Java のタイムに遥かに及ばない。いや、マジで Java 強い…。

console.time('xxx');

var Lazy = require('lazy.js');
var memo = [],
    ary = Lazy.range(2, 100001);

function collatz(n){
  return (function inner(m){
    if(m === 1){ return 0; }
    if(memo[m]){ return memo[m]; }

    var z = (m % 2 === 0) ? m/2 : m*3+1,
        result;

    result = memo[z] ? memo[z] : (function(){
      memo[z] = inner(z) + 1;
      return memo[z];
    })();

    return result;
  })(n);
}

var result = Lazy(ary).
      map(function(n){ return [n, collatz(n)]; }).
      max(function(x){ return x[1]; });

console.log(result[0]); // 77031
console.timeEnd('xxx'); // xxx: 176ms

ちょっとメモ化して underscore を Lazy に変えて 176ms これはまぁまぁ。

console.time('xxx');

var memo = [],
    max = 0,
    val, result;

function collatz(n){
  return (function inner(m){
    if(m === 1){ return 0; }
    if(memo[m]){ return memo[m]; }

    var z = (m % 2 === 0) ? m/2 : m*3+1,
        result;

    result = memo[z] ? memo[z] : (function(){
      memo[z] = inner(z) + 1;
      return memo[z];
    })();

    return result;
  })(n);
}

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

console.log(max);

console.timeEnd('xxx'); // xxx: 153ms

ライブラリのロードとデカイ配列を作るのをやめたら 20ms 早くなった。けど、これが限界。
そうそう会場にいるときに 20ms を出したんだけど、全部メモに突っ込んだ後に再計算したので実質計算してなかったので 20ms になっていたようで、少し酔ってたとはいえ恥ずかしい失敗。なので、今のところ僕が普通に書くとこれが限界で、コレ以上縮めるならアルゴリズム的な何かをしないと無理そうなんだけど、分からん…。
ちなみに並行処理とかでやった方が速いかな？って考えたけど、たぶんライブラリをロードする時間と memo 化がうまく効かなそうなので下手に並行にするよりは地味に書いたほうが良さそう。

ということで諦めて Scheme でどうだ！ってやってみた。

(use gauche.dictionary)

(define *memo* (make-hash-table))

(define (collatz n)
  (letrec ((iter (^m
                 (cond
                  [(= m 1) 0]
                  [(dict-exists? *memo* m) (dict-get *memo* m)]
                  [else
                   (if (= m 1)
                       0
                       (let1 z (if (zero? (remainder m 2))
                                   (/ m 2)
                                   (+ (* m 3) 1))
                         (if (dict-exists? *memo* z)
                             (dict-get *memo* z)
                             (let1 v (+ (iter z) 1)
                               (and (dict-put! *memo* z v)
                                    v)))))]))))
    (iter n)))

(time (apply max (map collatz
                    (iota 100000 2))))
; real   0.528
; user   0.730
; sys    0.010

うっ…。なんか思いの外遅かった…。たぶん、 hash-table だから重いのかなーとか思ったり。たぶん改善の余地は腐るほどあるんだろうけど、ちょっと思いつかないのでギブアップ(久しぶりに Scheme 書くとやたら汚いコードになってしまう)。

まぁ気が向いたら Ruby とか Common Lisp でやってみたいと思う。