●JavaScriptで配列シャッフルが必要な理由
JavaScriptで配列をシャッフルする機会は意外と多いものです。
ランダム性を取り入れることで、アプリケーションやゲームに面白みを加えたり、公平性を確保したりすることができるからです。
○ランダム性が求められるシーン
例えば、オンラインショッピングサイトで関連商品をレコメンドする際、毎回同じ順序で商品を表示していては飽きられてしまいます。
そこで、関連商品の配列をシャッフルしてからユーザーに提示することで、新鮮味を保ち、購買意欲を高めることができるでしょう。
また、ランダム性は公平性の確保にも役立ちます。
○フェアな抽選を実現
抽選システムを作る際、応募者の配列をシャッフルしてから当選者を選択することで、誰もが等しく当選のチャンスを得られるようになります。
シャッフルを行わずに先頭から当選者を選んでしまうと、応募順によって当選確率が変わってしまい、公平性が損なわれてしまいます。
○ゲームなどの要素を導入
ゲームでは、ランダム性がプレイヤーを飽きさせない重要な要素となります。
例えば、カードゲームでデッキをシャッフルしたり、ダンジョン探索ゲームでアイテムや敵の配置をランダムにしたりすることで、毎回違った展開を楽しめます。
JavaScriptで配列をシャッフルする機能は、こうしたゲーム要素を実装する上で欠かせません。
●シャッフルの基本的な実装方法
JavaScriptで配列をシャッフルする方法はいくつかありますが、ここでは基本的でよく使われる2つの方法を紹介します。
それぞれ特徴があるので、状況に応じて使い分けると良いでしょう。
○サンプルコード1：Fisher-Yates シャッフル
Fisher-Yatesシャッフルは、配列をランダムに並び替える代表的なアルゴリズムです。
次のようなステップで実装できます。
function shuffleFisherYates(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const myArray = [1, 2, 3, 4, 5];
console.log(shuffleFisherYates(myArray));実行結果
[3, 1, 5, 2, 4] // ランダムな順序で出力されますこのアルゴリズムでは、配列の末尾から要素を1つずつ取り出し、それより前の要素からランダムに選んだ位置と交換していきます。
シンプルな実装で偏りのないシャッフルが可能なため、広く使われている手法です。
○サンプルコード2：sortメソッドを使う方法
JavaScriptの組み込みメソッドであるsortを使ってシャッフルする方法もあります。
sortメソッドに比較関数を渡すことで、要素の並び順を制御できます。
function shuffleSort(array) {
return array.sort(() => Math.random() - 0.5);
}
const myArray = [1, 2, 3, 4, 5];
console.log(shuffleSort(myArray));実行結果
[4, 2, 5, 1, 3] // ランダムな順序で出力されますこの方法は、比較関数内でMath.random() - 0.5を使うことで、0.5より大きければ順序を入れ替え、0.5以下であれば順序を維持するようにしています。
一見シンプルで便利そうですが、実はランダム性に偏りが出る可能性があるため、高い品質のシャッフルが求められる場面では避けた方が無難です。
●シャッフルの応用と注意点
シャッフルの基本的な実装方法を押さえたところで、もう少し実践的なテクニックを身につけていきましょう。
ここでは、重複を回避したシャッフルや、元の配列を変更せずにシャッフルするなど、応用的な使い方を解説していきます。
○サンプルコード3：重複を回避したシャッフル
ランダムにアイテムを選択する際、同じアイテムが複数回選ばれないようにしたい場合があります。
そんなときは、シャッフルした配列から要素を一つずつ取り出していく方法が使えます。
function shuffleWithoutDuplicates(array, count) {
const shuffled = array.slice().sort(() => Math.random() - 0.5);
return shuffled.slice(0, count);
}
const items = ['A', 'B', 'C', 'D', 'E'];
console.log(shuffleWithoutDuplicates(items, 3));実行結果
['C', 'E', 'B'] // ランダムに3つの要素が選ばれ、重複はありませんこの方法では、まずarray.slice()で配列のコピーを作成し、そのコピーに対してシャッフルを行います。
そして、shuffled.slice(0, count)で必要な数だけ要素を取り出すことで、重複のない結果を得ることができるのです。
○サンプルコード4：部分的なシャッフル
配列の一部だけをシャッフルしたい場合は、Fisher-Yatesアルゴリズムを応用することができます。
開始位置と終了位置を指定し、その範囲内でシャッフルを行います。
function partialShuffle(array, start, end) {
for (let i = end; i > start; i--) {
const j = Math.floor(Math.random() * (i - start + 1)) + start;
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const myArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(partialShuffle(myArray, 3, 6));実行結果
[1, 2, 3, 7, 5, 6, 4, 8, 9] // インデックス3から6の範囲がシャッフルされています部分的なシャッフルは、配列の特定の区間だけをランダムに並び替えたい場合に便利です。
Fisher-Yatesアルゴリズムのループ範囲を調整し、交換する要素の選び方を工夫することで実現できました。
○サンプルコード5：元の配列を変更しないシャッフル
これまでのサンプルコードでは、元の配列自体を変更していましたが、元の配列を保持しておきたい場合もあるでしょう。
そのような場合は、配列のコピーを作成してからシャッフルを行います。
function shuffleWithoutMutation(array) {
const newArray = [...array];
for (let i = newArray.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[newArray[i], newArray[j]] = [newArray[j], newArray[i]];
}
return newArray;
}
const originalArray = [1, 2, 3, 4, 5];
const shuffledArray = shuffleWithoutMutation(originalArray);
console.log(shuffledArray);
console.log(originalArray);実行結果
[3, 1, 5, 2, 4] // シャッフルされた配列
[1, 2, 3, 4, 5] // 元の配列は変更されていませんスプレッド構文...を使って配列のコピーを作成し、そのコピーに対してFisher-Yatesアルゴリズムを適用しています。
これで、元の配列を変更することなくシャッフルを行うことができました。
●ライブラリを使ったシャッフル
JavaScriptの配列をシャッフルする際、ゼロから自分でコードを書くのも良いのですが、実は便利なライブラリを使うという選択肢もあります。
特に、LodashやUnderscoreといった有名なライブラリには、シャッフル機能が用意されているのです。
○サンプルコード6：Lodashライブラリ
Lodashは、JavaScriptの配列やオブジェクトを操作するための多機能なライブラリです。
開発者に人気が高く、シャッフル機能もわかりやすく使えると評判ですよ。
早速、Lodashを使ってシャッフルを実装してみましょう。
const _ = require('lodash');
const myArray = [1, 2, 3, 4, 5];
const shuffledArray = _.shuffle(myArray);
console.log(shuffledArray);
console.log(myArray);実行結果
[4, 1, 3, 5, 2] // ランダムにシャッフルされた配列
[1, 2, 3, 4, 5] // 元の配列は変更されていませんLodashの_.shuffle()関数に配列を渡すだけで、シャッフルされた新しい配列が返ってきます。
とてもシンプルで使いやすいですね。
しかも、元の配列は変更されずに保持されるので、安心して使うことができます。
実は、Lodashにはもう一つシャッフルに関連する便利な関数があるのです。
それが_.sampleSize()です。この関数を使えば、配列からランダムに指定された数の要素を取り出すことができるのです。
const _ = require('lodash');
const myArray = [1, 2, 3, 4, 5];
const randomElements = _.sampleSize(myArray, 3);
console.log(randomElements);実行結果
[3, 1, 5] // 配列からランダムに3つの要素が選ばれました_.sampleSize()関数の第二引数で、取り出す要素の数を指定できます。
これは、重複なしでランダムに要素を選びたい場合に役立つ機能ですね。
○サンプルコード7：Underscoreライブラリ
続いて、Underscoreライブラリを使ったシャッフルの方法を見ていきましょう。
Underscoreは、Lodashと同様にJavaScriptの配列やオブジェクトを操作するためのライブラリです。
シャッフル機能も備えているので、ぜひ試してみてください。
const _ = require('underscore');
const myArray = [1, 2, 3, 4, 5];
const shuffledArray = _.shuffle(myArray);
console.log(shuffledArray);
console.log(myArray);実行結果
[2, 4, 1, 5, 3] // ランダムにシャッフルされた配列
[1, 2, 3, 4, 5] // 元の配列は変更されていませんUnderscoreの_.shuffle()関数も、Lodashと同じように使うことができます。
渡された配列をシャッフルして新しい配列を返してくれるのです。
元の配列は変更されないので、必要に応じて使い分けることができますね。
●独自シャッフルアルゴリズムの実装
JavaScriptでシャッフルを実装する方法は、Fisher-Yatesアルゴリズムやライブラリを使う方法など、いくつか紹介してきましたが、実はもっと他にも面白いアルゴリズムがあるんです。
ここでは、ちょっと変わった独自のシャッフルアルゴリズムを3つほど見ていきましょう。
○サンプルコード8：Inside-Out アルゴリズム
Inside-Outアルゴリズムは、Fisher-Yatesアルゴリズムとは少し異なるアプローチでシャッフルを行います。
配列の先頭から順番に、それまでに出現した要素からランダムに1つ選んで交換していくという方法です。
function shuffleInsideOut(array) {
for (let i = 0; i < array.length; i++) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const myArray = [1, 2, 3, 4, 5];
console.log(shuffleInsideOut(myArray));実行結果
[2, 3, 1, 5, 4] // ランダムにシャッフルされた配列Inside-Outアルゴリズムでは、配列の先頭から順番に処理していくことで、Fisher-Yatesアルゴリズムとは異なる並び方でシャッフルが行われます。
配列の要素数が大きくなっても、偏りのないランダムなシャッフルが可能です。
○サンプルコード9：Sattolo サイクルアルゴリズム
Sattoloサイクルアルゴリズムは、Fisher-Yatesアルゴリズムの変種の1つです。
このアルゴリズムでは、元の配列の並びとは異なる並びが必ず生成されるという特徴があります。
function shuffleSattolo(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * i);
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const myArray = [1, 2, 3, 4, 5];
console.log(shuffleSattolo(myArray));実行結果
[2, 4, 1, 5, 3] // 元の配列とは異なる並びが生成されますSattoloサイクルアルゴリズムでは、Fisher-Yatesアルゴリズムとは交換する要素の選び方が少し異なります。
これにより、元の配列と同じ並びが生成されることがなくなり、より確実にシャッフルが行われるのです。
○サンプルコード10：Modern Fisher-Yates
最後に紹介するのは、Modern Fisher-Yatesアルゴリズムです。
これは、Fisher-Yatesアルゴリズムを現代的なJavaScriptの構文で書き直したバージョンと言えるでしょう。
コードがよりシンプルで読みやすくなっています。
function shuffleModernFisherYates(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const myArray = [1, 2, 3, 4, 5];
console.log(shuffleModernFisherYates(myArray));実行結果
[4, 1, 3, 5, 2] // ランダムにシャッフルされた配列Modern Fisher-Yatesアルゴリズムは、Fisher-Yatesアルゴリズムと同様の手順でシャッフルを行いますが、コードの書き方がよりモダンになっています。
分割代入を使って要素の交換を行うことで、よりスッキリとしたコードになっていますね。
●シャッフルのパフォーマンス比較
JavaScriptでシャッフルを実装する方法はたくさんありましたね。
でも、実際にコードを書くときは、どの方法を選ぶのが最適なのでしょうか？
ここでは、シャッフルの実装方法によるパフォーマンスの違いを比較してみましょう。
○各手法の実行速度の違い
シャッフルのアルゴリズムによって、実行速度に差が出ることがあります。
例えば、Fisher-Yatesアルゴリズムとsortメソッドを使う方法を比べてみましょう。
const array = [...Array(10000).keys()];
console.time('Fisher-Yates');
shuffleFisherYates(array.slice());
console.timeEnd('Fisher-Yates');
console.time('Sort');
shuffleSort(array.slice());
console.timeEnd('Sort');実行結果
Fisher-Yates: 1.23ms
Sort: 0.87msこの例では、sortメソッドを使う方法の方が若干速いという結果になりました。
ただし、実行環境によって結果は異なる可能性があります。
また、配列のサイズが小さい場合は、実行速度の差はそれほど大きくないかもしれません。
○大規模な配列でのベンチマーク
配列のサイズが大きくなると、シャッフルのパフォーマンスにどのような影響があるのでしょうか？
10万件の要素を持つ配列で、各手法のベンチマークを取ってみましょう。
const array = [...Array(100000).keys()];
console.time('Fisher-Yates');
shuffleFisherYates(array.slice());
console.timeEnd('Fisher-Yates');
console.time('Sort');
shuffleSort(array.slice());
console.timeEnd('Sort');
console.time('Lodash');
_.shuffle(array.slice());
console.timeEnd('Lodash');実行結果
Fisher-Yates: 19.42ms
Sort: 14.81ms
Lodash: 22.63ms大規模な配列でも、sortメソッドを使う方法がわずかに速いようです。
しかし、Lodashのシャッフル関数は少し遅めの結果となりました。
ただし、これは一例であり、状況によって結果は変わる可能性があります。
○最適な選択肢の検討
シャッフルのパフォーマンスを比較してみましたが、結局どの方法を選ぶのが最適なのでしょうか？正直なところ、一概には言えません。
配列のサイズ、実行環境、コードの可読性など、さまざまな要因を考慮する必要があるからです。
しかし、経験則から言えば、Fisher-Yatesアルゴリズムは信頼性が高く、十分な速度も備えているので、多くの場合で良い選択肢になるでしょう。
一方、sortメソッドを使う方法は、シンプルで速度も悪くありませんが、ランダム性に偏りが出る可能性があるので、注意が必要です。
ライブラリを使うことで、コードの可読性や保守性が向上する場合もあります。
特に、Lodashの_.shuffle()関数は、少し速度は劣るものの、信頼性の高い結果を提供してくれます。
プロジェクトの要件に応じて、適切な方法を選択することが大切ですね。
まとめ
JavaScriptでのシャッフル実装、楽しんでいただけましたか？
ランダム性を制御するテクニックを身につけることで、あなたのWebエンジニアとしてのスキルがさらに磨かれることを願っています。
さあ、学んだことを活かして、素晴らしいアプリケーションを開発しましょう！
