資訊專欄INFORMATION COLUMN
摘要：比如元素大概率出現(xiàn)在數(shù)組的頭部，元素大概率出現(xiàn)在數(shù)組的尾部，所有元素大概率停留在自己初始位置。當(dāng)目標(biāo)數(shù)組長度小于時，使用插入排序反之，使用快排。而在排序算法中，大多數(shù)情況都不會滿足這樣的條件。
最近看了一篇非常有趣的文章：關(guān)于JavaScript的數(shù)組隨機(jī)排序，其作者為oldj前輩。文中指出我們用來“將一個數(shù)組隨機(jī)排序”的經(jīng)典寫法所存在的問題，獲益匪淺。
本文將以更加詳盡的材料和更多樣的code demo進(jìn)行闡述。并嘗試用“Fisher–Yates shuffle”洗牌算法進(jìn)行終極解答。
多個熟悉的場景將一個數(shù)組進(jìn)行亂序處理，是一個非常簡單但是非常常用的需求。
比如，“猜你喜歡”、“點擊換一批”、“中獎方案”等等，都可能應(yīng)用到這樣的處理。包括我自己在寫代碼的時候，也確實遇到過。
一般比較經(jīng)典且流行的方案為：對對象數(shù)組采用array.sort()方法，并傳入一個比較函數(shù)（comparison function），這個比較函數(shù)隨機(jī)返回一個介于［－0.5， 0.5］之間的數(shù)值：
var numbers = [12,4,16,3];
numbers.sort(function() {
return .5 - Math.random();
});
關(guān)于這么做的理論基礎(chǔ)這里不再進(jìn)行闡釋。如果您不明白，可以了解一下JS中sort函數(shù)的使用方法。
有毒的array.sort方法正像oldj前輩文章指出的那樣，其實使用這個方法亂序一個數(shù)組是有問題的。
為此，我寫了一個腳本進(jìn)行驗證。并進(jìn)行了可視化處理。強(qiáng)烈建議讀者去Github圍觀一下，clone下來自己試驗。
腳本中，我對
var letters = ["A","B","C","D","E","F","G","H","I","J"];
letters這樣一個數(shù)組使用array.sort方法進(jìn)行了10000次亂序處理，并把亂序的每一次結(jié)果存儲在countings當(dāng)中。
結(jié)果在頁面上進(jìn)行輸出：
var countings = [
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0}
];
var letters=["A","B","C","D","E","F","G","H","I","J"];
for (var i = 0; i < 10000; i++) {
var r = ["A","B","C","D","E","F","G","H","I","J"].sort(function() {
return .5 - Math.random();
});
for(var j = 0; j <= 9; j++) {
countings[j][r[j]]++;
}
}
for(var i = 0; i <= 9;i++) {
for(var j = 0;j <= 9;j++) {
document.getElementById("results").rows[i + 1].cells[j + 1].firstChild.data = countings[i][letters[j]];
}
}
得到結(jié)果如圖：
這個結(jié)果對數(shù)組中的每一項元素在亂序后的結(jié)果進(jìn)行了統(tǒng)計。
如果點擊“recalculate”按鈕，可以進(jìn)行多次10000次取樣試驗。
不管點擊按鈕幾次，你都會發(fā)現(xiàn)整體亂序之后的結(jié)果絕對不是“完全隨機(jī)”。
比如A元素大概率出現(xiàn)在數(shù)組的頭部，J元素大概率出現(xiàn)在數(shù)組的尾部，所有元素大概率停留在自己初始位置。
由此可以先粗暴地得出結(jié)論：
使用array.sort方法進(jìn)行亂序處理，絕對是有問題的。
但是為什么會有問題呢？這需要從array.sort方法排序底層說起。
在Chrome v8引擎源碼中，可以清晰看到，
v8在處理sort方法時，使用了插入排序和快排兩種方案。當(dāng)目標(biāo)數(shù)組長度小于10時，使用插入排序；反之，使用快排。
Chrome’s v8 uses a combination of InsertionSort and QuickSort. That is, if the array is less than 10 elements in length, it uses an InsertionSort.
其實不管用什么排序方法，大多數(shù)排序算法的時間復(fù)雜度介于O(n)到O(n2)之間，元素之間的比較次數(shù)通常情況下要遠(yuǎn)小于n(n-1)/2，也就意味著有一些元素之間根本就沒機(jī)會相比較（也就沒有了隨機(jī)交換的可能），這些 sort 隨機(jī)排序的算法自然也不能真正隨機(jī)。
怎么理解上邊這句話呢？其實我們想使用array.sort進(jìn)行亂序，理想的方案或者說純亂序的方案是數(shù)組中每兩個元素都要進(jìn)行比較，這個比較有50%的交換位置概率。這樣一來，總共比較次數(shù)一定為n(n-1)。
而在sort排序算法中，大多數(shù)情況都不會滿足這樣的條件。因而當(dāng)然不是完全隨機(jī)的結(jié)果了。
順便說一下，關(guān)于v8引擎的排序方案，源碼使用JS實現(xiàn)的，非常利于前端程序員閱讀。其中，對應(yīng)不同的數(shù)組長度，使用了快排和插入排序不同方法。同時使用了大量的性能優(yōu)化技巧，尤其是關(guān)于快排的pivot選擇上十分有意思。感興趣的讀者不妨研究一下。
真正意義上的亂序要想實現(xiàn)真正意義上的亂序，其實不難。我們首先要規(guī)避不穩(wěn)定的array.sort方法。
在計算機(jī)科學(xué)中，有一個專門的：洗牌算法Fisher–Yates shuffle。如果你對算法天生遲鈍，也不要慌張。這里我一步一步來實現(xiàn)，相信您一定要得懂。
先來整體看一下所有代碼實現(xiàn)，一共也就10行：
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
console.log(tempArray);
解析：
首先我們有一個已經(jīng)排好序的數(shù)組：
Step1：
第一步需要做的就是，從數(shù)組末尾開始，選取最后一個元素。
在數(shù)組一共9個位置中，隨機(jī)產(chǎn)生一個位置，該位置元素與最后一個元素進(jìn)行交換。
Step2：
上一步中，我們已經(jīng)把數(shù)組末尾元素進(jìn)行隨機(jī)置換。
接下來，對數(shù)組倒數(shù)第二個元素動手。在除去已經(jīng)排好的最后一個元素位置以外的8個位置中，隨機(jī)產(chǎn)生一個位置，該位置元素與倒數(shù)第二個元素進(jìn)行交換。
Step3：
理解了前兩部，接下來就是依次進(jìn)行，如此簡單。
以上方法，是基于Fisher–Yates shuffle洗牌算法。下面，我們就需要自己開動腦筋，完成一個亂序方案。
其實這并不難，關(guān)鍵在于如何生產(chǎn)真正的亂序。因為往往生成的并不是完全意義上的亂序，關(guān)于這一點，讀者可以參考The Danger of Na?veté一文。
我們來看一下社區(qū)上劉哇勇的一系列進(jìn)階方案：
function shuffle (array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * array.length);
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}
關(guān)于這種方案，也給出了分析：
我們創(chuàng)建了一個copy數(shù)組，然后遍歷目標(biāo)數(shù)組，將其元素復(fù)制到copy數(shù)組里，同時將該元素從目標(biāo)數(shù)組中刪除，這樣下次遍歷的時候就可以跳過這個序號。而這一實現(xiàn)的問題正在于此，即使一個序號上的元素已經(jīng)被處理過了，由于隨機(jī)函數(shù)產(chǎn)生的數(shù)是隨機(jī)的，所有這個被處理過的元素序號可能在之后的循環(huán)中不斷出現(xiàn)，一是效率問題，另一個就是邏輯問題了，存在一種可能是永遠(yuǎn)運(yùn)行不完。
改進(jìn)的方案為：
function shuffle(array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * n--);
copy.push(array.splice(i, 1)[0]);
}
return copy;
}
改進(jìn)的做法就是處理完一個元素后，用Array的splice()方法將其從目標(biāo)數(shù)組中移除，同時也更新了目標(biāo)數(shù)組的長度。如此一來下次遍歷的時候是從新的長度開始，不會重復(fù)處理的情況了。
當(dāng)然這樣的方案也有不足之處：比如，我們創(chuàng)建了一個copy數(shù)組進(jìn)行返回，在內(nèi)存上開辟了新的空間。
不過，這可以完全避免：
function shuffle(array) {
var m = array.length,
t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
有趣的是，這樣的實現(xiàn)已經(jīng)完全等同于上文洗牌算法Fisher–Yates shuffle的方案了。
總結(jié)本文剖析了“數(shù)組亂序”這么一個簡單，但是有趣的需求場景。
對這個場景的深入分析，讓我們認(rèn)識到JS和計算機(jī)算法中的一些玄妙。
文章簡要提到了V8引擎對array.sort的處理、洗牌算法Fisher–Yates等內(nèi)容。希望對讀者有所啟發(fā)。
Happy Coding!
PS: 作者Github倉庫，歡迎通過代碼各種形式交流。
最近看了一篇非常有趣的文章：關(guān)于JavaScript的數(shù)組隨機(jī)排序，其作者為oldj前輩。文中指出我們用來“將一個數(shù)組隨機(jī)排序”的經(jīng)典寫法所存在的問題，獲益匪淺。
本文將以更加詳盡的材料和更多樣的code demo進(jìn)行闡述。并嘗試用“Fisher–Yates shuffle”洗牌算法進(jìn)行終極解答。
多個熟悉的場景將一個數(shù)組進(jìn)行亂序處理，是一個非常簡單但是非常常用的需求。
比如，“猜你喜歡”、“點擊換一批”、“中獎方案”等等，都可能應(yīng)用到這樣的處理。包括我自己在寫代碼的時候，也確實遇到過。
一般比較經(jīng)典且流行的方案為：對對象數(shù)組采用array.sort()方法，并傳入一個比較函數(shù)（comparison function），這個比較函數(shù)隨機(jī)返回一個介于［－0.5， 0.5］之間的數(shù)值：
var numbers = [12,4,16,3];
numbers.sort(function() {
return .5 - Math.random();
});
關(guān)于這么做的理論基礎(chǔ)這里不再進(jìn)行闡釋。如果您不明白，可以了解一下JS中sort函數(shù)的使用方法。
有毒的array.sort方法正像oldj前輩文章指出的那樣，其實使用這個方法亂序一個數(shù)組是有問題的。
為此，我寫了一個腳本進(jìn)行驗證。并進(jìn)行了可視化處理。強(qiáng)烈建議讀者去Github圍觀一下，clone下來自己試驗。
腳本中，我對
var letters = ["A","B","C","D","E","F","G","H","I","J"];
letters這樣一個數(shù)組使用array.sort方法進(jìn)行了10000次亂序處理，并把亂序的每一次結(jié)果存儲在countings當(dāng)中。
結(jié)果在頁面上進(jìn)行輸出：
var countings = [
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0}
];
var letters=["A","B","C","D","E","F","G","H","I","J"];
for (var i = 0; i < 10000; i++) {
var r = ["A","B","C","D","E","F","G","H","I","J"].sort(function() {
return .5 - Math.random();
});
for(var j = 0; j <= 9; j++) {
countings[j][r[j]]++;
}
}
for(var i = 0; i <= 9;i++) {
for(var j = 0;j <= 9;j++) {
document.getElementById("results").rows[i + 1].cells[j + 1].firstChild.data = countings[i][letters[j]];
}
}
得到結(jié)果如圖：
這個結(jié)果對數(shù)組中的每一項元素在亂序后的結(jié)果進(jìn)行了統(tǒng)計。
如果點擊“recalculate”按鈕，可以進(jìn)行多次10000次取樣試驗。
不管點擊按鈕幾次，你都會發(fā)現(xiàn)整體亂序之后的結(jié)果絕對不是“完全隨機(jī)”。
比如A元素大概率出現(xiàn)在數(shù)組的頭部，J元素大概率出現(xiàn)在數(shù)組的尾部，所有元素大概率停留在自己初始位置。
由此可以先粗暴地得出結(jié)論：
使用array.sort方法進(jìn)行亂序處理，絕對是有問題的。
但是為什么會有問題呢？這需要從array.sort方法排序底層說起。
在Chrome v8引擎源碼中，可以清晰看到，
v8在處理sort方法時，使用了插入排序和快排兩種方案。當(dāng)目標(biāo)數(shù)組長度小于10時，使用插入排序；反之，使用快排。
Chrome’s v8 uses a combination of InsertionSort and QuickSort. That is, if the array is less than 10 elements in length, it uses an InsertionSort.
其實不管用什么排序方法，大多數(shù)排序算法的時間復(fù)雜度介于O(n)到O(n2)之間，元素之間的比較次數(shù)通常情況下要遠(yuǎn)小于n(n-1)/2，也就意味著有一些元素之間根本就沒機(jī)會相比較（也就沒有了隨機(jī)交換的可能），這些 sort 隨機(jī)排序的算法自然也不能真正隨機(jī)。
怎么理解上邊這句話呢？其實我們想使用array.sort進(jìn)行亂序，理想的方案或者說純亂序的方案是數(shù)組中每兩個元素都要進(jìn)行比較，這個比較有50%的交換位置概率。這樣一來，總共比較次數(shù)一定為n(n-1)。
而在sort排序算法中，大多數(shù)情況都不會滿足這樣的條件。因而當(dāng)然不是完全隨機(jī)的結(jié)果了。
順便說一下，關(guān)于v8引擎的排序方案，源碼使用JS實現(xiàn)的，非常利于前端程序員閱讀。其中，對應(yīng)不同的數(shù)組長度，使用了快排和插入排序不同方法。同時使用了大量的性能優(yōu)化技巧，尤其是關(guān)于快排的pivot選擇上十分有意思。感興趣的讀者不妨研究一下。
真正意義上的亂序要想實現(xiàn)真正意義上的亂序，其實不難。我們首先要規(guī)避不穩(wěn)定的array.sort方法。
在計算機(jī)科學(xué)中，有一個專門的：洗牌算法Fisher–Yates shuffle。如果你對算法天生遲鈍，也不要慌張。這里我一步一步來實現(xiàn)，相信您一定要得懂。
先來整體看一下所有代碼實現(xiàn)，一共也就10行：
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
console.log(tempArray);
解析：
首先我們有一個已經(jīng)排好序的數(shù)組：
Step1：
第一步需要做的就是，從數(shù)組末尾開始，選取最后一個元素。
在數(shù)組一共9個位置中，隨機(jī)產(chǎn)生一個位置，該位置元素與最后一個元素進(jìn)行交換。
Step2：
上一步中，我們已經(jīng)把數(shù)組末尾元素進(jìn)行隨機(jī)置換。
接下來，對數(shù)組倒數(shù)第二個元素動手。在除去已經(jīng)排好的最后一個元素位置以外的8個位置中，隨機(jī)產(chǎn)生一個位置，該位置元素與倒數(shù)第二個元素進(jìn)行交換。
Step3：
理解了前兩部，接下來就是依次進(jìn)行，如此簡單。
以上方法，是基于Fisher–Yates shuffle洗牌算法。下面，我們就需要自己開動腦筋，完成一個亂序方案。
其實這并不難，關(guān)鍵在于如何生產(chǎn)真正的亂序。因為往往生成的并不是完全意義上的亂序，關(guān)于這一點，讀者可以參考The Danger of Na?veté一文。
我們來看一下社區(qū)上劉哇勇的一系列進(jìn)階方案：
function shuffle (array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * array.length);
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}
關(guān)于這種方案，也給出了分析：
我們創(chuàng)建了一個copy數(shù)組，然后遍歷目標(biāo)數(shù)組，將其元素復(fù)制到copy數(shù)組里，同時將該元素從目標(biāo)數(shù)組中刪除，這樣下次遍歷的時候就可以跳過這個序號。而這一實現(xiàn)的問題正在于此，即使一個序號上的元素已經(jīng)被處理過了，由于隨機(jī)函數(shù)產(chǎn)生的數(shù)是隨機(jī)的，所有這個被處理過的元素序號可能在之后的循環(huán)中不斷出現(xiàn)，一是效率問題，另一個就是邏輯問題了，存在一種可能是永遠(yuǎn)運(yùn)行不完。
改進(jìn)的方案為：
function shuffle(array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * n--);
copy.push(array.splice(i, 1)[0]);
}
return copy;
}
改進(jìn)的做法就是處理完一個元素后，用Array的splice()方法將其從目標(biāo)數(shù)組中移除，同時也更新了目標(biāo)數(shù)組的長度。如此一來下次遍歷的時候是從新的長度開始，不會重復(fù)處理的情況了。
當(dāng)然這樣的方案也有不足之處：比如，我們創(chuàng)建了一個copy數(shù)組進(jìn)行返回，在內(nèi)存上開辟了新的空間。
不過，這可以完全避免：
function shuffle(array) {
var m = array.length,
t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
有趣的是，這樣的實現(xiàn)已經(jīng)完全等同于上文洗牌算法Fisher–Yates shuffle的方案了。
總結(jié)本文剖析了“數(shù)組亂序”這么一個簡單，但是有趣的需求場景。
對這個場景的深入分析，讓我們認(rèn)識到JS和計算機(jī)算法中的一些玄妙。
文章簡要提到了V8引擎對array.sort的處理、洗牌算法Fisher–Yates等內(nèi)容。希望對讀者有所啟發(fā)。
Happy Coding!
PS: 作者Github倉庫，歡迎通過代碼各種形式交流。
百度知識搜索部大前端繼續(xù)招兵買馬，有意向者火速聯(lián)系。。。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/50658.html
摘要：比如元素大概率出現(xiàn)在數(shù)組的頭部，元素大概率出現(xiàn)在數(shù)組的尾部，所有元素大概率停留在自己初始位置。當(dāng)目標(biāo)數(shù)組長度小于時，使用插入排序反之，使用快排。而在排序算法中，大多數(shù)情況都不會滿足這樣的條件。 最近看了一篇非常有趣的文章：關(guān)于JavaScript的數(shù)組隨機(jī)排序，其作者為oldj前輩。文中指出我們用來將一個數(shù)組隨機(jī)排序的經(jīng)典寫法所存在的問題，獲益匪淺。 本文將以更加詳盡的材料和更多樣的c...
摘要：毫無疑問，設(shè)計模式于己于他人于系統(tǒng)都是多贏的設(shè)計模式使代碼編寫真正工程化設(shè)計模小書前端掘金這是一本關(guān)于的小書。 JavaScript 常見設(shè)計模式解析 - 掘金設(shè)計模式（Design pattern）是一套被反復(fù)使用、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié)。使用設(shè)計模式是為了可重用代碼、讓代碼更容易被他人理解、保證代碼可靠性。毫無疑問，設(shè)計模式于己于他人于系統(tǒng)都是多贏的；設(shè)計...
摘要：并嘗試用為什么你統(tǒng)計的方式是錯的掘金翻譯自工程師的文章。正如你期望的，文中的前端開發(fā)單一職責(zé)原則前端掘金單一職責(zé)原則又稱單一功能原則，面向?qū)ο笪鍌€基本原則之一。 單頁式應(yīng)用性能優(yōu)化 - 首屏數(shù)據(jù)漸進(jìn)式預(yù)加載 - 前端 - 掘金前言 針對首頁和部分頁面打開速度慢的問題，我們開始對單頁式應(yīng)用性能進(jìn)行優(yōu)化。本文介紹其中一個方案：基于 HTTP Chunk 的首屏數(shù)據(jù)漸進(jìn)式預(yù)加載方案，該方案總...
摘要：源碼地址為了簡化篇幅，我們對這個數(shù)組進(jìn)行分析，數(shù)組長度為，此時采用的是插入排序。插入排序的源碼是其原理在于將第一個元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個構(gòu)建的有序序列中。 JavaScript 專題系列第十九篇，講解數(shù)組亂序，重點探究 Math.random() 為什么不能真正的亂序？ 亂序 亂序的意思就是將數(shù)組打亂。 嗯，沒有了，直接看代碼吧。 Math.random ...
閱讀 2261·2021-10-09 09:41
閱讀 3409·2021-09-13 10:34
閱讀 1920·2019-08-30 12:59
閱讀 557·2019-08-29 17:27
閱讀 1063·2019-08-29 16:07
閱讀 2956·2019-08-29 13:15
閱讀 1306·2019-08-29 13:14
閱讀 1562·2019-08-26 12:18
