国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

也談前端面試常見問題之『數(shù)組亂序』

tracy / 601人閱讀

摘要:看完部分的源碼,首先迫不及待想跟大家分享的正是本文主題數(shù)組亂序。這是一道經(jīng)典的前端面試題,給你一個數(shù)組,將其打亂,返回新的數(shù)組,即為數(shù)組亂序,也稱為洗牌問題。關(guān)于數(shù)組亂序,正確的解法應(yīng)該是,復(fù)雜度。

前言

終于可以開始 Collection Functions 部分了。

可能有的童鞋是第一次看樓主的系列文章,這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時候,學(xué)到了很多,同時覺得有些知識點可以獨立出來,寫成文章與大家分享,而本文正是其中之一(完整的系列請猛戳 https://github.com/hanzichi/underscore-analysis)。之前樓主已經(jīng)和大家分享了 Object 和 Array 的擴展方法中一些有意思的知識點,今天開始解讀 Collection 部分。

看完 Collection Functions 部分的源碼,首先迫不及待想跟大家分享的正是本文主題 —— 數(shù)組亂序。這是一道經(jīng)典的前端面試題,給你一個數(shù)組,將其打亂,返回新的數(shù)組,即為數(shù)組亂序,也稱為洗牌問題。

一個好的方案需要具備兩個條件,一是正確性,毋庸置疑,這是必須的,二是高效性,在確保正確的前提下,如何將復(fù)雜度降到最小,是我們需要思考的。

splice

幾年前樓主還真碰到過洗牌問題,還真的是 "洗牌"。當(dāng)時是用 cocos2d-js(那時還叫 cocos2d-html5)做牌類游戲,發(fā)牌前毫無疑問需要洗牌。

當(dāng)時我是這樣做的。每次 random 一個下標(biāo),看看這個元素有沒有被選過,如果被選過了,繼續(xù) random,如果沒有,將其標(biāo)記,然后存入返回數(shù)組,直到所有元素都被標(biāo)記了。后來經(jīng)同事指導(dǎo),每次選中后,可以直接從數(shù)組中刪除,無需標(biāo)記了,于是得到下面的代碼。

function shuffle(a) {
  var b = [];

  while (a.length) {
    var index = ~~(Math.random() * a.length);
    b.push(a[index]);
    a.splice(index, 1);
  }

  return b;
}

這個解法的正確性應(yīng)該是沒有問題的(有興趣的可以自己去證明下)。我們假設(shè)數(shù)組的元素為 0 - 10,對其亂序 N 次,那么每個位置上的結(jié)果加起來的平均值理論上應(yīng)該接近 (0 + 10) / 2 = 5,且 N 越大,越接近 5。為了能有個直觀的視覺感受,我們假設(shè)亂序 1w 次,并且將結(jié)果做成了圖表,猛戳 http://hanzichi.github.io/test-case/shuffle/splice/ 查看,結(jié)果還是很樂觀的。

驗證了正確性,還要關(guān)心一下它的復(fù)雜度。由于程序中用了 splice,如果把 splice 的復(fù)雜度看成是 O(n),那么整個程序的復(fù)雜度是 O(n^2)。

Math.random()

另一個為人津津樂道的方法是 "巧妙應(yīng)用" JavaScript 中的 Math.random() 函數(shù)。

function shuffle(a) {
  return a.concat().sort(function(a, b) {
    return Math.random() - 0.5;
  });
}

同樣是 [0, 1, 2 ... 10] 作為初始值,同樣跑了 1w 組 case,結(jié)果請猛戳 http://hanzichi.github.io/test-case/shuffle/Math.random/。

看平均值的圖表,很明顯可以看到曲線浮動,而且多次刷新,折現(xiàn)的大致走向一致,平均值更是在 5 上下 0.4 的區(qū)間浮動。如果我們將 [0, 1, 2 .. 9] 作為初始數(shù)組,可以看到更加明顯不符預(yù)期的結(jié)果(有興趣的可以自己去試下)。究其原因,要追究 JavaScript 引擎對于 Math.random() 的實現(xiàn)原理,這里就不展開了(其實是我也不知道)。因為 ECMAScript 并沒有規(guī)定 JavaScript 引擎對于 Math.random() 應(yīng)該實現(xiàn)的方式,所以我猜想不同瀏覽器經(jīng)過這樣的亂序后,結(jié)果也不一樣。

什么時候可以用這種方法亂序呢?"非正式" 場合,一些手寫 DEMO 需要亂序的場合,這不失為一種 clever solution。

但是這種解法不但不正確,而且 sort 的復(fù)雜度,平均下來應(yīng)該是 O(nlogn),跟我們接下來要說的正解還是有不少差距的。

Fisher–Yates Shuffle

關(guān)于數(shù)組亂序,正確的解法應(yīng)該是 Fisher–Yates Shuffle,復(fù)雜度 O(n)。

其實它的思想非常的簡單,遍歷數(shù)組元素,將其與之前的任意元素交換。因為遍歷有從前向后和從后往前兩種方式,所以該算法大致也有兩個版本的實現(xiàn)。

從后往前的版本:

function shuffle(array) {
  var _array = array.concat();

  for (var i = _array.length; i--; ) {
    var j = Math.floor(Math.random() * (i + 1));
    var temp = _array[i];
    _array[i] = _array[j];
    _array[j] = temp;
  }
  
  return _array;
}

underscore 中采用從前往后遍歷元素的方式,實現(xiàn)如下:

// Shuffle a collection, using the modern version of the
// [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
_.shuffle = function(obj) {
  var set = isArrayLike(obj) ? obj : _.values(obj);
  var length = set.length;
  var shuffled = Array(length);
  for (var index = 0, rand; index < length; index++) {
    rand = _.random(0, index);
    if (rand !== index) shuffled[index] = shuffled[rand];
    shuffled[rand] = set[index];
  }
  return shuffled;
};

將其解耦分離出來,如下:

function shuffle(a) {
  var length = a.length;
  var shuffled = Array(length);

  for (var index = 0, rand; index < length; index++) {
    rand = ~~(Math.random() * (index + 1));
    if (rand !== index) 
      shuffled[index] = shuffled[rand];
    shuffled[rand] = a[index];
  }

  return shuffled;
}

跟前面一樣,做了下數(shù)據(jù)圖表,猛戳 http://hanzichi.github.io/test-case/shuffle/Fisher-Yates/。

關(guān)于證明,引用自月影老師的文章:

隨機性的數(shù)學(xué)歸納法證明

對 n 個數(shù)進(jìn)行隨機:

首先我們考慮 n = 2 的情況,根據(jù)算法,顯然有 1/2 的概率兩個數(shù)交換,有 1/2 的概率兩個數(shù)不交換,因此對 n = 2 的情況,元素出現(xiàn)在每個位置的概率都是 1/2,滿足隨機性要求。

假設(shè)有 i 個數(shù), i >= 2 時,算法隨機性符合要求,即每個數(shù)出現(xiàn)在 i 個位置上每個位置的概率都是 1/i。

對于 i + 1 個數(shù),按照我們的算法,在第一次循環(huán)時,每個數(shù)都有 1/(i+1) 的概率被交換到最末尾,所以每個元素出現(xiàn)在最末一位的概率都是 1/(i+1) 。而每個數(shù)也都有 i/(i+1) 的概率不被交換到最末尾,如果不被交換,從第二次循環(huán)開始還原成 i 個數(shù)隨機,根據(jù) 2. 的假設(shè),它們出現(xiàn)在 i 個位置的概率是 1/i。因此每個數(shù)出現(xiàn)在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1),也是 1/(i+1)。

綜合 1. 2. 3. 得出,對于任意 n >= 2,經(jīng)過這個算法,每個元素出現(xiàn)在 n 個位置任意一個位置的概率都是 1/n。

小結(jié)

關(guān)于數(shù)組亂序,如果面試中被問到,能說出 "Fisher–Yates Shuffle",并且能基本說出原理(你也看到了,其實代碼非常的簡單),那么基本應(yīng)該沒有問題了;如果能更進(jìn)一步,將其證明呈上(甚至一些面試官都可能一時證明不了),那么就牛逼了。千萬不能只會用 Math.random() 投機取巧!

Read More:

數(shù)組的完全隨機排列(推薦)

Fisher–Yates Shuffle(推薦)

如何測試洗牌程序

How to randomize (shuffle) a JavaScript array?

Code for Shuffling an Array

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/79901.html

相關(guān)文章

  • 也談面試必備問題 JavaScript 數(shù)組去重

    摘要:而數(shù)組元素去重是基于運算符的。而如果有迭代函數(shù),則計算傳入迭代函數(shù)后的值,對值去重,調(diào)用方法,而該方法的核心就是調(diào)用方法,和我們上面說的方法一異曲同工。 Why underscore (覺得這部分眼熟的可以直接跳到下一段了...) 最近開始看 underscore.js 源碼,并將 underscore.js 源碼解讀 放在了我的 2016 計劃中。 閱讀一些著名框架類庫的源碼,就好像...

    Coly 評論0 收藏0
  • JavaScript專題系列20篇正式完結(jié)!

    摘要:寫在前面專題系列是我寫的第二個系列,第一個系列是深入系列。專題系列自月日發(fā)布第一篇文章,到月日發(fā)布最后一篇,感謝各位朋友的收藏點贊,鼓勵指正。 寫在前面 JavaScript 專題系列是我寫的第二個系列,第一個系列是 JavaScript 深入系列。 JavaScript 專題系列共計 20 篇,主要研究日常開發(fā)中一些功能點的實現(xiàn),比如防抖、節(jié)流、去重、類型判斷、拷貝、最值、扁平、柯里...

    sixleaves 評論0 收藏0
  • 案例 - 收藏集 - 掘金

    摘要:同行這么做使用實現(xiàn)圓形進(jìn)度條前端掘金在開發(fā)微信小程序的時候,遇到圓形進(jìn)度條的需求。實現(xiàn)也談數(shù)組去重前端掘金的數(shù)組去重是一個老生常談的話題了。百度前端技術(shù)學(xué)院自定義前端掘金一標(biāo)簽概念元素表示用戶界面中項目的標(biāo)題。 閑話圖片上傳 - 掘金作者:孫輝,美團(tuán)金融前端團(tuán)隊成員。15年畢業(yè)加入美團(tuán),相信技術(shù),更相信技術(shù)只是大千世界里知識的一種,個人博客: https://sunyuhui.com ...

    張金寶 評論0 收藏0
  • 案例 - 收藏集 - 掘金

    摘要:同行這么做使用實現(xiàn)圓形進(jìn)度條前端掘金在開發(fā)微信小程序的時候,遇到圓形進(jìn)度條的需求。實現(xiàn)也談數(shù)組去重前端掘金的數(shù)組去重是一個老生常談的話題了。百度前端技術(shù)學(xué)院自定義前端掘金一標(biāo)簽概念元素表示用戶界面中項目的標(biāo)題。 閑話圖片上傳 - 掘金作者:孫輝,美團(tuán)金融前端團(tuán)隊成員。15年畢業(yè)加入美團(tuán),相信技術(shù),更相信技術(shù)只是大千世界里知識的一種,個人博客: https://sunyuhui.com ...

    huangjinnan 評論0 收藏0
  • JavaScript專題系列文章

    摘要:專題系列共計篇,主要研究日常開發(fā)中一些功能點的實現(xiàn),比如防抖節(jié)流去重類型判斷拷貝最值扁平柯里遞歸亂序排序等,特點是研究專題之函數(shù)組合專題系列第十六篇,講解函數(shù)組合,并且使用柯里化和函數(shù)組合實現(xiàn)模式需求我們需要寫一個函數(shù),輸入,返回。 JavaScript 專題之從零實現(xiàn) jQuery 的 extend JavaScritp 專題系列第七篇,講解如何從零實現(xiàn)一個 jQuery 的 ext...

    Maxiye 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<