Updated at: 2014-01-16

Algorithm

ソート関連

乱数系

XorShift

僕の実装

seed は以下のようにやってみた:

private function _setSeed(seed:uint):void {
    x = seed = 1812433253 * (seed ^ (seed >> 30)) + 0;
    y = seed = 1812433253 * (seed ^ (seed >> 30)) + 1;
    z = seed = 1812433253 * (seed ^ (seed >> 30)) + 2;
    w = seed = 1812433253 * (seed ^ (seed >> 30)) + 3;

    // 初めのほうを読み飛ばし
    for (var i:int = 0;  i < 8;  ++i) {
        _genUint();
    }
}

読み物

メモリ管理

座標系

自動生成系

プロシージャル

リーズナブルな配列のシャッフル Fisher–Yates shuffle

最初に末尾と入れ替えて、範囲を 1 ずつ小さくしてく

  • Wikipedia - Fisher–Yates shuffle
  • 配列を少ない仕事量でシャッフルするFisher-Yates法

    // ActionScript 3.0
    var i:int = array.length;
    var j:int;
    var tmp:Object;
    
    while (i) {
        j   = Math.floor(Math.random() * i);
        tmp = array[--i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
  • underscore.js の実装とかオシャレ

    _.shuffle = function(obj) {
      var rand;
      var index = 0;
      var shuffled = [];
      each(obj, function(value) {
        rand = _.random(index++);
        shuffled[index - 1] = shuffled[rand];
        shuffled[rand] = value;
      });
      return shuffled;
    };
    

配列系

重複を削除する

意外と標準ライブラリになかったりする系の処理。 naive な手法だと要素を走査して「結果のリストにもう入っているか」を都度 find 的なものでチェックする、 というのがありそうだけど非効率。

  • ハッシュマップに覚えとく
    • メモリを消費して速度を得るパターン
    • 無難で速い。でかいリスト対象の場合、メモリを食うのが懸念くらいか
    • 順序が維持できる

  • ソートしてから走査していく
    • 隣り合うやつが同じだったら Pick しない的な
    • CPU 使ってもよいけどメモリ食いたくない場合などに
    • 当然結果はソートされた順序になる。どうせソートしたい場合などには都合がよい

参考:Array remove duplicate elements - Stack Overflow

僕の実装

catmull-rom spline

いもす法

  • 累積和をアルゴリズムを多次元、多次数に拡張したもの
  • 愚直な方法よりも計算量を抑える(次元の上昇に強い)