トランプゲームにおけるシャッフルのアルゴリズム

問題意識

Wikipedia によると、配列を（破壊的に）シャッフルする最適なアルゴリズムは、改良されたフィッシャー–イェーツの方法(FYと略記)とのこと。

しかし、トランプゲームにおけるシャッフルは以下の点でFYと異なる。

• 52枚全部をシャッフルする必要がない
  • ゲームで使うのは最初の数枚のみ
• そもそも、シャッフルすべき元配列が存在しない
  • 0..51 という配列を用意してもいいが必須ではない

これを考慮して、以下のお題を考えてみたい。

「トランプカードをランダムに n枚取り出す最適なアルゴリズムは何か？」

現状認識

JavaScript では標準ライブラリでシャッフルは提供されていない。Lodash を使ってこう書くのがおそらく標準的だろう。

const deal = num => _.shuffle(_.range(52)).slice(0, num);

deal(3); // -> [ 48, 40, 23 ]
deal(5); // -> [ 7, 37, 19, 3, 34 ]

これを改良できないか？が主な目的となる。なお、Lodash のコード は、FYの実装だった。

改善候補を探す

同じくWikipedia を見ると、FYは、途中で打ち切ることも可能であるらしい。シャッフルされたカードが n枚必要なら、イテレーションをそこで打ち切ることで、全体をシャッフルするのではなく必要な部分だけシャッフルできるらしい。

もう一つ改善の方向性がある。同じくWikipedia に乗っている「取り出し」アルゴリズムである。こちらはシャッフルする配列自体は存在せず、例えば関数のようなものでも動作する。つまり、シャッフル前の配列を用意しなくてもよいのが利点となる。

以上二つを、それぞれ FYP, IO と名付けて実装し計測しよう。なお、FYP = Fisher Yates Partial, IO = Inside Out の略。

結果と考察

1000万回 52枚のカードから9枚を取り出す作業をした結果を記載する。Node 10で動作。FYは冒頭の実装。FYPはFYの9枚で打ち切り、IOは取り出しアルゴリズム。

FY, 15761 msecs
FYP, 4737 msecs
IO, 12753 msecs
IO, 12896 msecs
FYP, 4838 msecs
FY, 16802 msecs

FYPが一番早く、FYの4倍速くなった。IOはFYよりも2割程度高速化するにとどまった。やはりランダム関数を呼ぶ回数が少ない方が速度に影響するようだ。

ランダム関数および配列の初期化にかかるオーバーヘッドを見た。1000万回ランダム関数を呼び出し(random)、配列確保(allocate)、配列確保と値埋め(allocateFill)、範囲配列生成(range)の時間を測定した。

random, 7017 msecs
allocate, 695 msecs
allocateFill, 2194 msecs
range, 2437 msecs

まあ、こんなものかなという気もする。一番時間がかかるのが乱数生成なので、乱数の生成数を抑えれないIOはそんなに早くならない。とはいえ、range - allocate 程度の時間の処理の改善がみられるのは想定通りといえる。

コード

const _ = require('lodash');

const deal0 = (num, length) => _.shuffle(_.range(length)).slice(0, num);
const deal1 = (num, length) => {
  let index = -1;
  const lastIndex = length - 1;
  const result = _.range(length);
  while (++index < num) { // this is the point!, num not length
    const rand = index + Math.floor(Math.random() * (lastIndex - index + 1));
    const value = result[rand];
    result[rand] = result[index];
    result[index] = value;
  }
  return result.slice(0, num);
};
const deal2 = (num, length) => {
  const result = Array(length);
  let index = -1;
  while (++index < length) {
    const rand = Math.floor(Math.random() * (index + 1));
    if (rand !== index) {
      result[index] = result[rand];
    }
    result[rand] = index; // source[index] === index because source is just range
  }
  return result.slice(0, num);
};


const measure = (label, fn) => {
  // warm up
  for (let i = 0; i < 10000; i += 1) {
    fn();
  }
  // measure
  const before = Date.now();
  for (let i = 0; i < 10000000; i += 1) {
    fn();
  }
  const record = Date.now() - before;
  // output
  console.log(`${label}, ${record} msecs`);
};

const main = () => {
  measure('FY', () => deal0(9, 52));
  measure('FYP', () => deal1(9, 52));
  measure('IO', () => deal2(9, 52));
  measure('IO', () => deal2(9, 52));
  measure('FYP', () => deal1(9, 52));
  measure('FY', () => deal0(9, 52));

  measure('random', () => {
    let index = -1;
    while(++index < 52)
      Math.floor(Math.random() * 100);
  });
  measure('allocate', () => {
    Array(52);
  });
  measure('allocateFill', () => {
    Array(52).fill(0);
  });
  measure('range', () => {
    _.range(52);
  });
};

main()