Zenn
🎲

Math.random()は本当にランダム？ ― 開発者のためのシャッフルアルゴリズム徹底解説

に公開
アルゴリズム
random
tech

1. はじめに

Web フロントエンドでもバックエンドでも「ランダム」は驚くほど多用されます。
しかし Math.random()（あるいは random.random()）をそのまま使えば十分でしょうか？
本稿では 擬似乱数 (PRNG) の基礎から Fisher‑Yates シャッフルの正しい実装、
さらには 暗号学的に安全 (CSPRNG) なシャッフルまで、幅広い観点で掘り下げます。

2. 「ランダム」とは何か

種類 代表 API 典型アルゴリズム 主な用途
真の乱数 (TRNG) ハードウェア RNG 電子ノイズ・量子効果 セキュリティ機器
擬似乱数 (PRNG) Math.random()
random.random() 		Mersenne Twister, xorshift ゲーム、シミュレーション
暗号学的擬似乱数 (CSPRNG) crypto.getRandomValues()
crypto.randomInt() 		ChaCha20, AES-CTR DRBG トークン生成、鍵生成

ポイント: PRNG は高速・軽量ですが、出力は決定論的。シードが分かると再現できます。

3. Math.random()の裏側

  • ECMAScript はアルゴリズムを 規定していない
    • V8 は xorshift128+ → xorshift 系
    • JavaScriptCore は Mersenne Twister
  • 実装ごとに周期・統計特性が異なる
  • 暗号用途での使用は非推奨（MDN でも明記）

4. 「ランダムシャッフル」の落とし穴

// 🤔 よく見るけどダメな例
array.sort(() => Math.random() - 0.5);
  • 比較関数は 反射律 を満たさずソートアルゴリズム依存で偏りが生じる
  • n = 10 の場合、10! 通りの並びのうち平均で約 63% しか生成できない

4.1 バイアスを可視化する

import random, math, collections
def bad_shuffle(seq):
    return sorted(seq, key=lambda _: random.random()-0.5)

def count_perm(n, trials=100_000):
    c = collections.Counter(tuple(bad_shuffle(list(range(n)))) for _ in range(trials))
    return max(c.values())/min(c.values())
print(f"max/min 出現比: {count_perm(5):.2f}")

出力例: max/min 出現比: 3.14 — 理想は 1.0 なので 3 倍以上の偏り。

5. Fisher–Yates シャッフル（Knuth Shuffle）

function fisherYates<T>(a: T[]): T[] {
  for (let i = a.length - 1; i >= 1; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 0 ≤ j ≤ i
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}
  • O(n)、追加メモリ O(1)
  • 各要素が最終的にどのインデックスに移動する確率も 1/n
  • 逆向きに走査し「未確定領域」からランダムに交換することで重複選択を防ぐ

5.1 Inside‑Out 版（ストリーム生成向け）

func InsideOut(src []int) []int {
    dst := make([]int, len(src))
    for i, v := range src {
        j := rand.Intn(i + 1)
        dst[i] = dst[j]
        dst[j] = v
    }
    return dst
}

6. CSPRNG を使った堅牢シャッフル

import { randomInt } from "crypto";
function secureShuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = randomInt(i + 1); // crypto安全
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}
  • crypto モジュールは Node v15.6 以降で randomInt をサポート
  • ブラウザなら window.crypto.getRandomValues() とビット演算で乱数範囲を縮める

7. ベストプラクティス

  1. ユースケースで使い分ける
    • ベンチマークやゲーム → PRNG
    • セッション ID, JWT → CSPRNG
  2. シード管理で再現可能なテストを
  3. 統計テスト（χ², Kolmogorov–Smirnov, dieharder）で品質を検証
  4. 並列処理では 乱数ストリームの衝突に注意
  5. 乱数がボトルネックなら 乱数プールをプリフェッチ

8. シャッフル関連アルゴリズム

アルゴリズム 目的 特徴
Reservoir Sampling 部分集合抽出 ストリーム長不明でも O(k) メモリ
Inside‑Out Shuffle 配列生成 Fisher‑Yates の拡張
Perfect Shuffle 交互合体 トランプの“パーフェクトリフル”

9. よくある質問

  • Q. sort+random がダメなら、なぜ多くの記事が紹介しているの？
    A. 実装が簡単で小規模データでは問題が顕在化しにくいから。規模が大きい/Game サーバーでは避けるべき。
  • Q. 乱数性能を測るには？
    A. benchmark.js や pytest-benchmark で 1e6 回呼び出し時間を比較し、必要なら rand crate の SmallRng など軽量 PRNG を検討。

10. まとめ

  • Math.random() は 擬似乱数。暗号学的には不十分
  • シャッフルには Fisher‑Yates が事実上の標準
  • セキュリティを担保したい場合は CSPRNG を組み合わせる
  • 品質評価・シード管理・性能測定を怠らないことがプロダクション品質への第一歩

参考文献

  • Donald E. Knuth. The Art of Computer Programming, Vol. 2 (3rd ed.), §3.4.
  • ECMAScript® 2024 Language Spec — §26.2.3 Math.random
  • Black, Paul E. “Pseudorandom Number Generator.” NIST Dictionary of Algorithms and Data Structures.
  • Melissa O’Neill. PCG: A Family of Simple Fast Space‑Efficient Statistically Good Algorithms for Random Number Generation.

Discussion