ソートアルゴリズムを可視化してみよう（３）

JavaScript によるソートアルゴリズムの可視化

こちらのつづきです。

プログラムの解説 - ユーティリティ

今回は util.js の内容です。
中身は、乱数生成のクラスとタイマーのクラスです。

ソートアルゴリズム可視化の目的においては本題ではないので
読み飛ばしてしまっても問題ないですが、
中身が気になる方はご覧ください。

util.js

/**
 *  乱数生成クラス（XorShift）
 *  ＃シードが固定できる乱数生成器として採用
 */
class XorShift {
    /**
     *  XorShift 乱数の最大値
     *  @private
     */
    static MAX = 0xffffffff;
    /**
     *  XorShift
     *  @param {number} seed 乱数のシード値
     */
    constructor ( seed = 88675123 ) {
        [this.x, this.y, this.z, this.w] = [123456789 >>> 0, 362436069 >>> 0, 521288629 >>> 0, seed >>> 0];
        this.iterator = this.generator();
        // 最初に適当に回しておく
        const len = Math.floor( ( this.next() * 99 ) + 1 );
        for ( let i = 0; i < len; i++ ) {
            this.next();
        }
    }
    /**
     *  XorShift のジェネレータ
     *  @private
     */
    *generator () {
        for ( ;; ) {
            this.t = this.x ^ ( this.x << 11 );
            [this.x, this.y, this.z] = [this.y, this.z, this.w];
            this.w = ( ( this.w ^ ( this.w >>> 19 ) ) ^ ( this.t ^ ( this.t >>> 8 ) ) ) >>> 0;
            if ( this.w === XorShift.MAX ) continue;
            yield this.w ;
        }
    }
    /**
     *  乱数を出力する
     *  @returns number [0~1) の乱数
     */
    next () {
        return this.iterator.next().value / XorShift.MAX;
    }
}

/**
    タイマークラス
 */
class Timer {
    constructor () {
        this.running = false;
        this.elapsed_time = 0;
        this.start_time = 0;
    }
    /**
     *  タイマーをスタートする
     */
    start () {
        this.running = true;
        this.elapsed_time = 0;
        this.start_time = performance.now();
    }
    /**
     *  タイマーをリセットする
     */
    reset () {
        this.running = false;
        this.elapsed_time = 0;
        this.start_time = performance.now();
    }
    /**
     *  タイマーを再開する
     */
    resume () {
        if ( !this.running ) {
            this.running = true;
            this.start_time = performance.now();
        }
    }
    /**
     *  タイマーを中断する
     */
    pause () {
        if ( this.running ) {
            this.running = false;
            this.elapsed_time = this.elapsed_time + ( performance.now() - this.start_time );
        }
    }
    /**
     *  タイマーを停止する
     *  @returns number スタートからの経過時間
     */
    stop () {
        if ( this.running ) {
            this.running = false;
            return this.elapsed_time + ( performance.now() - this.start_time );    
        }
    }
}

XorShift クラス

XorShift128 と呼ばれる乱数生成アルゴリズムを実装したものです。
ビットシフトで構成されて高速に値を生成できる特徴があるのと、
シード値を指定できるということもあって組み込んでみました。

コンストラクタ

x, y, z, w という４つの変数を初期化します。
引数としてシード値が与えられた場合は、w を引数で置き換えます。
this.iterator には、後述するジェネレータメソッドから取り出す
イテレータを保持します。

その直後に乱数生成を実行しています。
固定シード値の場合は、乱数列がずれるだけなのですが、
何らか妙なシード値の場合でも、多少安定するようにしています。
おまじない

*generator ()

乱数生成部分のメソッドです。ジェネレータです。
無限ループで yield させることで、イテレータが値を取り出せます。

1. t に、x と x の左シフト を xor して代入します
2. x, y, z に、y, z, w をそれぞれ代入します
3. w に、 w と wの右シフト の xor と、t と tの右シフト の xor を行い、両者を xor して代入します

この 1. と 3. の演算が、この XorShift の名前の所以となっています。
また、３か所あるシフトのビット数 $( 11, 8, 19 )$ の組み合わせと、
変数 x, y, z, w で状態を保持している部分が、
この乱数の周期を実現している仕組みになっているそうです。
上記の場合 XorShift128 (周期 $ 2^{128} - 1$ ）になります。

現在では、XorShift をさらに改良したアルゴリズムも存在しますが、
あまり高品質である必要もないので今回はこのバージョンです。
（なんなら線形合同法などでも十分なのですがせっかくなので。。）

なお、JavaScript では ビット演算は32ビット整数 です。
普通の右シフトではマイナス値も出てきて厄介なので、
符号なし右シフトを使い、$0 ～ 2^{32} - 1$ の範囲で値を取り出します。

next ()

乱数を取り出す際のメソッドです。
イテレータの存在は外からは知らなくて良いようにしています。
0xffffffff で割った値を返却することで、
$0 \leq x < 1$ という範囲で乱数を返却します。

Timer クラス

時間計測用につくりました。
だいたいメソッドの名前どおりに使います。

コンストラクタ

状態を初期化しています。

start ()

タイマーをスタートします。起動状態になります。
次に stop () か pause () が呼ばれるまで動作します。

reset ()

タイマーをリセットします。停止状態になります。

resume ()

タイマーを再開します。起動状態になります。
次に stop () か pause () が呼ばれるまで動作します。

pause ()

タイマーを中断します。停止状態になり、
pause () が呼ばれるまでの経過時間は保持します。
次に resume () を呼ぶことで再開できます。

stop ()

タイマーを停止し、経過時間を返します。