Chapter 42

疑似乱数

miku
miku
2021.11.15に更新

p5.jsの疑似乱数を生み出す関数

random(); // // 0以上 1未満
random(a, b); // a以上 b未満
random(array); // 配列の中から要素をランダムに選ぶ

// 以降のrandom()の値が指定したseedNumberに依存したものになる
seed(seedNumber);

// 配列内の要素をシャッフルした新しい配列を返す
// 引数に指定した配列に影響はない
const newArray = shuffle(array); 

// 第2引数にtrueを指定することで、引数に指定した配列をシャッフルする
shuffle(array, true);

疑似乱数を利用するには基本的にはこれらの関数を利用すればいいが、ここにはない機能や、これらの関数がどういう風に出来ているかをこれから確認していく。

基本

Math.random(); // 0以上 1未満

JavaScriptには Math.random() という乱数の値を返す関数がある。乱数に関して用意されているのがこの関数しかない上に、引数で乱数の幅を調整したりできないので Math.random() を利用して他の機能をうまく作る必要がある。

範囲を変える

Math.random() * a; // 0以上 a未満
Math.random() * a + b; // b以上 a+b未満

Math.random()a 倍すると、0以上 1未満の範囲に a を掛けるので、0以上 a未満の範囲になる。底を 0 にしたくない場合は、上の結果に b を足すと、b以上 a+b未満の範囲になる。ただし、上限が a ではなく a + b に変わってしまうので、そもそも a を掛けるのではなく (b-a) を掛ければ、範囲がb以上 (b-a)+b未満、つまりb以上a未満になって都合がいい。

ab の変数名を maxmin に変えて関数化したのが下記になる。

function randomRange(min, max) {
  return Math.random() * (max - min) + min;
}

randomRange(min, max)min 以上 max 未満のランダムな値を返す。

整数の範囲に変える

randomInt(min, max)min 以上 max 以下のランダムな整数を返したい。

まずは駄目な例である四捨五入をする例を見てみよう。

function randomInt(min, max) {
  return Math.round(randomRange(min, max));
}

先程の randomRange() の結果を四捨五入する方法だ。

たとえば randomInt(0, 2) のケースで考えてみる。

四捨五入によって返す整数が決まるので、

  • 0以上 0.5未満 -> 0
  • 0.5以上 1.5未満 -> 1
  • 1.5以上 2未満 -> 2

となり、1に変換される範囲だけ他の倍になっている。

偏りが無いようにするには下記のようにすればいい。

function randomInt(min, max) {
  return Math.floor(randomRange(min, max + 1));
}

渡された max の値を1つ増やし、範囲を min~max+1 にして小数点を切り捨てる。

  • 0以上 1未満 -> 0
  • 1以上 2未満 -> 1
  • 2以上 3未満 -> 2

となり、均等に整数が返ることになる。

配列の中から要素をランダムに選ぶ

function pick(array) {
  const i = Math.floor(Math.random() * array.length);
  return array[i];
}

Math.random() * array.length で 0以上 配列サイズ未満の実数を作り、その値を切り捨てることで 0以上 配列サイズ-1 の整数を作ることができる。これを配列のインデックスにすれば配列の中から要素をランダムに選ぶことができる。

プラスマイナスのランダム

const v = random(10, 20) * random([-1, 1]);

A * random([-1, 1])A の符号を50%の確率で反転させることができる。

0を含まないプラスマイナスのランダム

// -1~-5 あるいは 1~5 の範囲の値が返る
const v = random(1, 5) * random([-1, 1]);

-5~5 の範囲のランダム値が欲しいが、0 あるいは 0 付近の値が出ると困るというケースがある。たとえばオブジェクトを動かす速度を決める場合にそのような値が出ると見た目に変化が起こらないからだ。なので random(-5, 5) のようには書けないので、いったん非負数の範囲で考えて、その値に random([-1, 1]) を掛ければいい。

シャッフル(駄目な例)

function shuffle(a) {
  for (let k = 0; k < n; k++) {
    const i = Math.floor(Math.random() * n);
    const j = Math.floor(Math.random() * n);
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

配列の要素をシャッフルするには、たとえば2つの添字をランダムに選び、その添字にある要素同士を交換。これを繰り返していく方法があるが、一度も選ばれない添字が出ることもあり得る。かなりの回数で実行すればその可能性も限りなく減るだろうが、そもそも何回まで行えばいいかもわかりづらく効率も悪いし、絶対にでないという保証もない。

なので、代わりにFisher-Yatesのシャッフルというアルゴリズムを利用したい。

Fisher-Yatesのシャッフル

function shuffle(a) {
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
}

配列の後ろから前に向けて走査するループを用意する。添字は i とする。0~i までの添字をランダムに選び、それを j とする。ij の要素を交換する。

i0 以外のすべての添字を1回ずつ代入するので、交換が行われない要素は存在しない。j は毎回 0~i のどれかになるが、i の値は毎回1つずつ減っていく。なので後ろの要素が交換の対象から外れていくが、これはすでに交換を1回でも行ったものなので問題がない。むしろ j の値を 0~n-1 にしてしまうと、1回でも交換したという事実が無くなる可能性がある。

i >= 0 ではなく i > 0 なのは、i0 のとき j の値は 0 にしかならないので、かならず自身同士を交換することになるので 0 まで見る必要がない。前から後ろに操作しているのは、j の範囲は 0~i と必ず下限が 0 になるからだ。前から走査してもいいのだが、1回目は 0~n - 1、2回目は 1~n-1 …と下限が 0 でなくなるので計算がややこしくなる。

重み付けの抽選

数値が入った配列からランダムに値を選ぶ際、中の値を重み付けとして捉え、抽選を行う。たとえば [1, 1, 2, 3] という配列を用意した場合、要素の合計値が 7 なので、配列内の各要素が選ばれる確率は次のようになる。

[\dfrac{1}{7}, \dfrac{1}{7}, \dfrac{2}{7}, \dfrac{3}{7}]

function pickWeighted(array) {
  // 配列内の数字の合計を求める
  const total = array.reduce((a, b) => a + b, 0);
  // 配列内の数字を合計値で割った新しい配列を作る
  const probs = array.map((value) => value / total);
  // 0~1までの閾値を作る
  const threshold = Math.random();

  // 閾値を超えたときのインデックスを返す
  // もし閾値を超えない場合は確率の値を足していく
  // 例えば1回目が0.1(10%)で閾値を超えない場合、
  // 2回目が0.4(40%)の場合は、0.1 + 0.4 > 閾値の計算を行う
  let curProb = 0;
  return probs.findIndex((value) => {
    curProb += value;
    return threshold < curProb;
  });
}

シード値

乱数で取得する値の並びがまったく同じになるように調整できると便利なときがある。たとえば、デバッグ時やなにかのリプレイを行うようなときだ。そのような乱数列を生み出すために、乱数を利用する前に前もって渡しておく値のことをシードと呼び、シード毎に固定の乱数列が生成される。

function setup() {
  createCanvas(windowWidth, windowHeight);

  randomSeed(100);
  console.log(random()); // 0.2748232155572623
  console.log(random()); // 0.3489434248767793
  console.log(random()); // 0.29036099393852055

  randomSeed(100);
  console.log(random()); // 0.2748232155572623
  console.log(random()); // 0.3489434248767793
  console.log(random()); // 0.29036099393852055
}

Xorshift

自前でシードが指定できる疑似乱数が必要な場合はXorshiftという生成アルゴリズムを利用すると便利だ。

ここで紹介するXorshiftは32bit用のもので、1以上4294967295以下の整数値全てを重複なくバラバラに出力するアルゴリズムになる。

順番 生成される値
仮にこの位置を1番目だとする 3337163801
2番目 1763869612
3番目 330629095
...
4294967293番目 447601850
4294967294番目 2254653639
4294967295番目 12346
4294967296番目(1番目) 3337163801
4294967297番目(2番目) 1763869612
4294967298番目(3番目) 330629095

バラバラといっても内部の計算式に乱数が使われているわけではないので、ローテーション自体は固定のものになる。たとえば 3337163801 の後に生成される値は必ず 1763869612 になる。内部では前回生成した値を保持しているが、それを外部から初期値として指定できるようにすると、それはそのままシード値になる。

下記で掲載している実装例では Math.random() と同じように 0 以上 1 未満の値が返却されるように正規化している。

XorShiftの実装例

const XorShift = {
  max: 0xffffffff, // 2^32 - 1

  init(seed) {
    const xs = { seed: 0 };

    // 引数がなければシード値をランダムに選ぶ
    if (seed === undefined) {
      xs.seed = Math.floor(Math.random() * XorShift.max) + 1;
    } else {
      XorShift.setSeed(xs, seed);
    }

    // この時点で初期値(seed)が1以上max以下の値になるように調整されている

    return xs;
  },

  // シード値の指定(0 <= seed < max)
  setSeed(xs, seed) {
    // 整数にする
    seed = Math.floor(seed);
    if (!(0 <= seed && seed < XorShift.max)) {
      throw new Error(`シード値の範囲は0以上${XorShift.max}未満の値でなければいけません。`);
    }
    xs.seed = seed + 1;
  },

  // 0以上1未満の値を返す
  getValue(xs) {
    XorShift.next(xs);

    // 上限値が1未満になる、の実装のため、seed/max=1になるような計算はスキップする
    if (xs.seed === XorShift.max) {
      XorShift.next(xs);
    }

    // 下限値が0になるように分子分母ともに1を引いて割合を求める
    return (xs.seed - 1) / (XorShift.max - 1);
  },

  // 次に生成される値を計算
  next(xs) {
    xs.seed = xs.seed ^ (xs.seed << 13);
    xs.seed = xs.seed ^ (xs.seed >>> 17);
    xs.seed = xs.seed ^ (xs.seed << 5);
    xs.seed = xs.seed >>> 0; // 33bit番目以上の情報は捨てる
  },
};
const a = XorShift.init(12345);
console.log(XorShift.getValue(a)); // 0.7769939958942095
console.log(XorShift.getValue(a)); // 0.4106828970418698
console.log(XorShift.getValue(a)); // 0.07698058480256265

const b = XorShift.init(12345);
console.log(XorShift.getValue(b)); // 0.7769939958942095
console.log(XorShift.getValue(b)); // 0.4106828970418698
console.log(XorShift.getValue(b)); // 0.07698058480256265