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

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

こちらのつづきです。

https://qiita.com/w0rc/items/aaf0431f04445a1c97e0

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

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

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

```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ビット整数](https://developer.mozilla.org/ja/docs/Web/JavaScript/Guide/Expressions_and_operators#%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97%E5%AD%90) です。
普通の右シフトではマイナス値も出てきて厄介なので、
符号なし右シフトを使い、$0 ～ 2^{32} - 1$ の範囲で値を取り出します。

#### next ()

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

### Timer クラス

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

#### コンストラクタ

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

#### start ()

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

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

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

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

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