JavaScript專題之亂序
亂序
亂序的意思就是将數組打亂。
嗯,沒有了,直接看代碼吧。
Math.random
一個經常會遇見的寫法是使用 Math.random():
var values = [1, 2, 3, 4, 5];
values.sort(function(){
return Math.random() - 0.5;
});
console.log(values)
Math.random() - 0.5
随機得到一個正數、負數或是 0,如果是正數則降序排列,如果是負數則升序排列,如果是 0 就不變,然後不斷的升序或者降序,最終得到一個亂序的數組。
看似很美好的一個方案,實際上,效果卻不盡如人意。不信我們寫個 demo 測試一下:
var times = [0, 0, 0, 0, 0];
for (var i = 0; i < 100000; i++) {
let arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);
times[arr[4]-1]++;
}
console.log(times)
測試原理是:将
[1, 2, 3, 4, 5]
亂序 10 萬次,計算亂序後的數組的最後一個元素是 1、2、3、4、5 的次數分别是多少。
一次随機的結果為:
該結果表示 10 萬次中,數組亂序後的最後一個元素是 1 的情況共有 30636 次,是 2 的情況共有 30906 次,其他依此類推。
我們會發現,最後一個元素為 5 的次數遠遠低于為 1 的次數,是以這個方案是有問題的。
可是我明明感覺這個方法還不錯呐?初見時還有點驚豔的感覺,為什麼會有問題呢?
是的!我很好奇!
插入排序
如果要追究這個問題所在,就必須了解 sort 函數的原理,然而 ECMAScript 隻規定了效果,沒有規定實作的方式,是以不同浏覽器實作的方式還不一樣。
為了解決這個問題,我們以 v8 為例,v8 在處理 sort 方法時,當目标數組長度小于 10 時,使用插入排序;反之,使用快速排序和插入排序的混合排序。
是以我們來看看 v8 的源碼,因為是用 JavaScript 寫的,大家也是可以看懂的。
源碼位址:https://github.com/v8/v8/blob/master/src/js/array.js
為了簡化篇幅,我們對
[1, 2, 3]
這個數組進行分析,數組長度為 3,此時采用的是插入排序。
插入排序的源碼是:
function InsertionSort(a, from, to) {
for (var i = from + 1; i < to; i++) {
var element = a[i];
for (var j = i - 1; j >= from; j--) {
var tmp = a[j];
var order = comparefn(tmp, element);
if (order > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element;
}
};
其原理在于将第一個元素視為有序序列,周遊數組,将之後的元素依次插入這個建構的有序序列中。
我們來個簡單的示意圖:
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-U0NPx0lC-1609927312428)(https://github.com/mqyqingfeng/Blog/raw/master/Images/sort/insertion.gif)]
具體分析
明白了插入排序的原理,我們來具體分析下 [1, 2, 3] 這個數組亂序的結果。
示範代碼為:
var values = [1, 2, 3];
values.sort(function(){
return Math.random() - 0.5;
});
注意此時 sort 函數底層是使用插入排序實作,InsertionSort 函數的 from 的值為 0,to 的值為 3。
我們開始逐漸分析亂序的過程:
因為插入排序視第一個元素為有序的,是以數組的外層循環從
i = 1
開始,a[i] 值為 2,此時内層循環周遊,比較
compare(1, 2)
,因為
Math.random() - 0.5
的結果有 50% 的機率小于 0 ,有 50% 的機率大于 0,是以有 50% 的機率數組變成 [2, 1, 3],50% 的結果不變,數組依然為 [1, 2, 3]。
假設依然是 [1, 2, 3],我們再進行一次分析,接着周遊,
i = 2
,a[i] 的值為 3,此時内層循環周遊,比較
compare(2, 3)
:
有 50% 的機率數組不變,依然是
[1, 2, 3]
,然後周遊結束。
有 50% 的機率變成 [1, 3, 2],因為還沒有找到 3 正确的位置,是以還會進行周遊,是以在這 50% 的機率中又會進行一次比較,
compare(1, 3)
,有 50% 的機率不變,數組為 [1, 3, 2],此時周遊結束,有 50% 的機率發生變化,數組變成 [3, 1, 2]。
綜上,在 [1, 2, 3] 中,有 50% 的機率會變成 [1, 2, 3],有 25% 的機率會變成 [1, 3, 2],有 25% 的機率會變成 [3, 1, 2]。
另外一種情況 [2, 1, 3] 與之分析類似,我們将最終的結果彙總成一個表格:
數組 | i = 1 | i = 2 | 總計 |
---|---|---|---|
[1, 2, 3] | 50% [1, 2, 3] | 50% [1, 2, 3] | 25% [1, 2, 3] |
25% [1, 3, 2] | 12.5% [1, 3, 2] | ||
25% [3, 1, 2] | 12.5% [3, 1, 2] | ||
50% [2, 1, 3] | 50% [2, 1, 3] | 25% [2, 1, 3] | |
25% [2, 3, 1] | 12.5% [2, 3, 1] | ||
25% [3, 2, 1] | 12.5% [3, 2, 1] |
為了驗證這個推算是否準确,我們寫個 demo 測試一下:
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = [1, 2, 3];
arr.sort(() => Math.random() - 0.5);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 為了友善展示,轉換成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)
這是一次随機的結果:
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-YMwm9oQt-1609927312429)(https://github.com/mqyqingfeng/Blog/raw/master/Images/shuffle/mathRandom.png)]
我們會發現,亂序後,
3
還在原位置(即 [1, 2, 3] 和 [2, 1, 3]) 的機率有 50% 呢。
是以根本原因在于什麼呢?其實就在于在插入排序的算法中,當待排序元素跟有序元素進行比較時,一旦确定了位置,就不會再跟位置前面的有序元素進行比較,是以就亂序的不徹底。
那麼如何實作真正的亂序呢?而這就要提到經典的 Fisher–Yates 算法。
Fisher–Yates
為什麼叫 Fisher–Yates 呢? 因為這個算法是由 Ronald Fisher 和 Frank Yates 首次提出的。
話不多說,我們直接看 JavaScript 的實作:
function shuffle(a) {
var j, x, i;
for (i = a.length; i; i--) {
j = Math.floor(Math.random() * i);
x = a[i - 1];
a[i - 1] = a[j];
a[j] = x;
}
return a;
}
原理很簡單,就是周遊數組元素,然後将目前元素與以後随機位置的元素進行交換,從代碼中也可以看出,這樣亂序的就會更加徹底。
如果利用 ES6,代碼還可以簡化成:
function shuffle(a) {
for (let i = a.length; i; i--) {
let j = Math.floor(Math.random() * i);
[a[i - 1], a[j]] = [a[j], a[i - 1]];
}
return a;
}
還是再寫個 demo 測試一下吧:
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = shuffle([1, 2, 3]);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 為了友善展示,轉換成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)
這是一次随機的結果:
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-nmX64iGK-1609927312430)(https://github.com/mqyqingfeng/Blog/raw/master/Images/shuffle/fisher-yates.png)]
真正的實作了亂序的效果!
專題系列
JavaScript專題系列目錄位址:https://github.com/mqyqingfeng/Blog。
JavaScript專題系列預計寫二十篇左右,主要研究日常開發中一些功能點的實作,比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯裡、遞歸、亂序、排序等,特點是研(chao)究(xi) underscore 和 jQuery 的實作方式。
如果有錯誤或者不嚴謹的地方,請務必給予指正,十分感謝。如果喜歡或者有所啟發,歡迎 star,對作者也是一種鼓勵。