JavaScriptの配列についてランダムに並べ替えます.
4951 ワード
配列のランダム並べ替え問題を前にして、潜在意識で考えた最初の方法はランダムな下付き順序を生成することです.かつてネット上ではこんな書き方がずっと伝わっていました.
探索する
ECMAScriptの中でAray.prototype.sort(comprefn)に関する基準を見ましたが、具体的な実現アルゴリズムは規定されていませんでした.
Calling comprefn(a,b)always returns the same value v hen given a specific pair of values a and b as its two argmens.
つまり、同じグループa、bの値に対して、comprefn(a、b)は常に同じ値を返す必要がある.上記の
v 8エンジン配列の部分のソースコードを参照してください.性能を考慮して、短い配列に対して使用されるのは挿入順序で、長い配列に対しては高速なソートが使用されています.このようにして、なぜ()=>Math.random()-0.5が本当にランダムに配列を乱すことができないのかが分かります.
(ソースコードによると、長さが22以下のものを使用して並べ替え、22より大きいものを使用していますが、実際のテスト結果は10の境界を示しています.)
ソリューション
(a,b)=>Math.randowm()-0.5の問題は同じグループのa,bに対して毎回返した値が同じであることを保証できないので、配列要素を改造してもいいです.
方法2:(Fisher–Yates shuffle fe雪耶兹ランダム放置アルゴリズム)!おすすめ
Lodashライブラリのshuffleアルゴリズムを調べてみると、実際にはFisher-Yatesシャッフルアルゴリズムを使っていることに気づく.
アルゴリズムの考え:0~i(iの変化はn-1から0の減少)の中からランダムに下付きを取得し、最後の要素(i)と交換する.
まとめ:配列をランダムに並べ替える場合は、(a,b)=>Math.random()-0.5を使わないでください.現在、Fisher–Yates shuffleアルゴリズムは最良の選択であるべきです.
参照リンク:http://developer.51cto.com/art/201704/536457.htm http://blog.csdn.net/lhkaikai/article/details/25627161
function shuffle(arr) {
arr.sort(function () {
return Math.random() - 0.5;
});
}
以前はこの方法が簡単だと思っていましたが、後でまとめた時に、各要素はまだ大きな確率で元の位置の近くに現れています.彼は本当にランダムに並べられているのではないようです.探索する
ECMAScriptの中でAray.prototype.sort(comprefn)に関する基準を見ましたが、具体的な実現アルゴリズムは規定されていませんでした.
Calling comprefn(a,b)always returns the same value v hen given a specific pair of values a and b as its two argmens.
つまり、同じグループa、bの値に対して、comprefn(a、b)は常に同じ値を返す必要がある.上記の
() => Math.random() -0.5
、すなわち(a, b) => Math.random() - 0.5
は、この条件を満たしていないことは明らかである.v 8エンジン配列の部分のソースコードを参照してください.性能を考慮して、短い配列に対して使用されるのは挿入順序で、長い配列に対しては高速なソートが使用されています.このようにして、なぜ()=>Math.random()-0.5が本当にランダムに配列を乱すことができないのかが分かります.
(ソースコードによると、長さが22以下のものを使用して並べ替え、22より大きいものを使用していますが、実際のテスト結果は10の境界を示しています.)
ソリューション
(a,b)=>Math.randowm()-0.5の問題は同じグループのa,bに対して毎回返した値が同じであることを保証できないので、配列要素を改造してもいいです.
let new_i = {
v: i,
r: Math.random()
};
完全コード:function shuffle(arr) {
// ( 、 )
let new_arr = arr.map(i => ({v: i, r: Math.random()}));
//
new_arr.sort((a, b) => a.r - b.r);
// v ,
arr.splice(0, arr.length, ...new_arr.map(i => i.v));
}
let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
let n = 10000;
let count = (new Array(a.length)).fill(0);
for (let i = 0; i < n; i ++) {
shuffle(a);
count[a.indexOf('a')]++;
}
console.log(count);
この方法はランダムで十分です.しかし、性能的にはあまり良くないです.何回かの配列を巡回する必要があります.また、配列に対してもspliceなどの操作が必要です.方法2:(Fisher–Yates shuffle fe雪耶兹ランダム放置アルゴリズム)!おすすめ
Lodashライブラリのshuffleアルゴリズムを調べてみると、実際にはFisher-Yatesシャッフルアルゴリズムを使っていることに気づく.
アルゴリズムの考え:0~i(iの変化はn-1から0の減少)の中からランダムに下付きを取得し、最後の要素(i)と交換する.
function shuffle(arr) {
var i = arr.length, t, j;
while (i) {
j = Math.floor(Math.random() * i--); //!!!
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
es 6バージョン:function shuffle(arr) {
let i = arr.length;
while (i) {
let j = Math.floor(Math.random() * i--);
[arr[j], arr[i]] = [arr[i], arr[j]];
}
}
アルゴリズムに必要な時間はランダムスクランブリングの数に比例しており、そのためのメモリ空間オーバーヘッドは不要である.まとめ:配列をランダムに並べ替える場合は、(a,b)=>Math.random()-0.5を使わないでください.現在、Fisher–Yates shuffleアルゴリズムは最良の選択であるべきです.
参照リンク:http://developer.51cto.com/art/201704/536457.htm http://blog.csdn.net/lhkaikai/article/details/25627161