Crypto API で JavaScript の配列をシャッフルする
気付き
JavaScript の配列をシャッフル(ランダムに並び替える)しようと思います。
調べてみると、Math.random を使って sort すると偏りが出るそうで、Fisher–Yates shuffle法を使うと良いとありました。その中で、乱数を発生させる API として Web Crypto API の名前が出てました。
MDN の Web Crypto API の説明ページを見ると、getRandomValues という、乱数の配列を作るメソッドがありました。
これで乱数の配列を作ってソート関数に入れれば手っ取り早いのでは? と思うのですが、ちょっと検索してもこのアプローチは見つからなかったので、ここで作ってみましょう。
プログラミング
getRandomValues の引数は整数値ベースの TypedArray 、とあります。下記の例では、Uint8Array(arr.length)
の部分で 符号無し8bit整数値 を arr.length
個作ることになります。
要は、0~255までのランダムな数値を、入力された配列の要素数だけ用意するということです。要素数がもっと多い場合は、Uint16Array, Uint32Array などを使ってください。
ソート関数の中で、入力された配列の要素のインデックスとランダムに作られた配列のインデックスを対応させてソートします。
要素数が多い場合は、indexOf を使わずに、あらかじめ、(入力配列の要素 → ランダム配列の要素) の Map を作った方が速いかもしれません。
// ソート関数
function crpShuffle(arr){
// 入力された配列と同じ個数の乱数の配列を作成
crpArr = window.crypto.getRandomValues(new Uint8Array(arr.length))
// 入力された配列と乱数の配列を対応させてソートする。
return arr.sort((a,b) => crpArr[arr.indexOf(a)] - crpArr[arr.indexOf(b)])
}
// テスト実行用関数
function testSort(arr){
//配列を一旦コピーしてソートを実行
tmpArr = [...arr]
return crpShuffle(tmpArr)
}
// 具体的な例で実行
let orgArr = ['レキント','キント','コンガ','トゥンバドーラ','ボンゴ','マッチョ','エンブラ']
console.log(testSort(orgArr))
['キント', 'マッチョ', 'ボンゴ', 'コンガ', 'レキント', 'エンブラ', 'トゥンバドーラ']
結果のランダム性はあまり問題無いようですが、確認のため何千、何万回も繰り返すと、Math.random や Fisher–Yates shuffle法より体感的にも時間がかかります。
他ではほとんど見かけない、短く書ける方法でシャッフルプログラムを作りました。
Discussion