摘要:隨機洗牌算法說實話,以前理解數組的排序,都是將數組按照一定的邏輯由大到小或者由小到大排序,我自己是沒有碰到過隨機打亂數組排序的問題。然后里用的是所謂的洗牌算法,很高效。總結又是三個知識點,分別是隨機洗牌分組和函數的實現,沒什么復雜的。
這是第三篇關于 Underscore 的源碼解讀,最近一段時間學的東西很少,自己太忙了,一方面忙著找實習,晚上回去還要寫畢業論文。畢業論文真的很憂傷,因為是兩年半,九月份就要交一個初稿,一般都是暑假寫,如果暑假出去實習,是沒時間點,所以要現在寫一個版本出來。
隨機洗牌算法說實話,以前理解數組的排序,都是將數組按照一定的邏輯(由大到小或者由小到大)排序,我自己是沒有碰到過隨機打亂數組排序的問題。今天看到這個問題,先是一愣,為什么要把一個數組給隨機亂序,仔細想想這種應用場合還是很多的,比如隨機地圖、隨機洗牌等等,都是隨機亂序的應用。
如果這是一個面試題,將一個數組隨機亂序,我的解決辦法如下:
function randomArr( arr ){ var ret = [], rand, len, newA = arr.slice(); // 為了不破壞原數組 while(len = newA.length){ rand = Math.floor(Math.random() * len); ret.push(newA.splice(rand, 1)[0]); } return ret; }
這是一個解決辦法,但是卻不是一個高效的解決辦法,首先,空間復雜度來講,新建了兩個數組(若不考慮對原數組的改變,可以只用一個返回數組),如果能在原數組上直接操作,那真的是太好了,其次時間復雜度來講,splice 函數要對數組進行改變,復雜度可以算作 n,所以總的時間復雜度應該為 O(n^2)。
然后 _ 里用的是所謂的洗牌算法,很高效。洗牌算法的思路有個很大的不同,用交換數組元素的方式替換原來的 splice,因為 splice 太坑了,然后對上面的代碼進行改進:
function randomArr2( arr ){ var rand, temp; for(var i = arr.length - 1; i >= 0; i--){ rand = Math.floor(Math.random() * ( i + 1 )); // 交互 i 和 rand 位置的元素 temp = arr[i]; arr[i] = arr[rand]; arr[rand] = temp; } return arr; }
改進后看起來就好多了,也比較好理解,還有一個循環的方式是從 0 到 n,randmo 函數沒次取值到范圍為 i~n,方法也大體是相同的。然而在 _ 中的 shuffle 方法的循環卻是從左到右,看了半天才明白,代碼如下:
// [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); // 新建一個 kength 長度的空數組 for (var index = 0, rand; index < length; index++) { rand = _.random(0, index); // 獲取 0~index 之間的隨機數 // shuffled[index] 是 undefined 的,先將 index 處的值替換成 rand 處的值 // 再將 rand 處的值替換成 set 集合處的 index if (rand !== index) shuffled[index] = shuffled[rand]; shuffled[rand] = set[index]; } return shuffled; };
_.shuffle 使用的是從左到右的思路,以至于我都無法判斷出這是不是隨機數組,向右前進一位,找到 0 ~ index 之間的一個隨機數,插入新元素,如果還按照之前的解題思路,在原數組的基礎上進行修改,則可以得到:
function randomArr3(arr){ var rand, temp; for(var i = 0; i < arr.length; i++){ // 這里的 random 方法和 _.random 略有不同 rand = Math.floor(Math.random() * ( i + 1 )); if(rand !== i){ temp = arr[i]; arr[i] = arr[rand]; arr[rand] = temp; } } return arr; }
_.random 方法是一個非常實用的方法,而我在構造 randomArr3 函數的時候,是想得到一個 0 ~ i 之間的一個隨機數,來看看 _.random 是如何方便的實現的:
_.random = function(min, max) { if (max == null) { max = min; min = 0; } // 和我最終的思路是一樣的 return min + Math.floor(Math.random() * (max - min + 1)); };group 原理
有時候需要對從服務器獲得的 ajax 數據進行統計、分組,這個時候就用到了 _ 中的 group 函數。
與 group 相關的函數有三個,它們分別是 groupBy,indexBy,countBy,具體使用可以參考下面的代碼:
// groupBy 用來對數據進行分組 _.groupBy([3, 4, 5, 1, 8], function(v){ return v % 2 }); // {0:[4,8],1:[3,5,1]} // 還可以用數據的屬性來區分 _.groupBy(["red", "yellow", "black"], "length"); // {3:["red"],5:["black"],6:["yellow"]} // 從某一個屬性入手,相同的會替換 _.indexBy([{id: 1,name: "first"}, {id: 2, name: "second"}, {id: 1, name: "1st"}], "id"); // {1:{id:1,name:"1st"},2:{id:2,name:"second"}} // 用來統計數量 _.countBy([3, 4, 5, 1, 8], function(v){ return v % 2 == 0 ? "even" : "odd" }); // {odd: 3, even: 2}
這三個函數的實現都非常類似,在 _ 中有進行優化,即常見的函數閉包:
var group = function(behavior) { return function(obj, iteratee, context) { // 函數閉包 var result = {}; // 要返回的對象 iteratee = cb(iteratee, context); _.each(obj, function(value, index) { var key = iteratee(value, index, obj); // 針對 group、index、count,有不同的 behavior 函數 behavior(result, value, key); }); return result; }; }; _.groupBy = group(function(result, value, key) { // 每個屬性都是一個數組 if (_.has(result, key)) result[key].push(value); else result[key] = [value]; }); _.indexBy = group(function(result, value, key) { // 對于相同的前者被后者替換 result[key] = value; }); _.countBy = group(function(result, value, key) { // 每個屬性是數量 if (_.has(result, key)) result[key]++; else result[key] = 1; });
對于 groupBy 和 countBy 處理模式幾乎是一摸一樣的,只是一個返回數組,一個返回統計值而已。
關于統計,這三個函數用的還真的不是很多,循環很好構造,處理函數也很好構造,如果數據是數組,直接 forEach 循環一遍添加一個處理函數就 ok 了,不過 _ 最大的優點就是省事吧,這種重復利用函數、函數閉包的思路,是值的借鑒的。
bind 函數call、apply、bind 這三個函數也算是 js 函數中三劍客,經常能看到面試題,讓實現 bind 函數,我就有一個疑問,難道支持 apply 的瀏覽器,不支持 bind 函數:
實現 bind 函數:
Function.prototype.bind = Function.prototype.bind || function(context){ var slice = Array.prototype.slice var args = slice.call(arguments, 1), self = this; return function(){ self.apply(context, args.concat(slice.call(arguments))); } }
有時候也會看到有人這樣寫:
Function.prototype.bind = Function.prototype.bind || function(context){ var self = this; return function(){ self.apply(context, arguments); } }
下面這種寫法顯然是低級新手玩家的手準,因為對于 bind 函數,有個很大的優點就是提前預定參數,如果懂了這個,就不會犯這個錯誤。
來看看 _ 里高級玩家的寫法:
_.bind = function(func, context) { // 原生 bind 還是好,此函數總結 if (nativeBind && func.bind === nativeBind) return nativeBind.apply(func, slice.call(arguments, 1)); // 報個錯 if (!_.isFunction(func)) throw new TypeError("Bind must be called on a function"); var args = slice.call(arguments, 2); // 先存變量 var bound = function() { return executeBound(func, bound, context, this, args.concat(slice.call(arguments))); }; return bound; }; var executeBound = function(sourceFunc, boundFunc, context, callingContext, args) { // 還是用 apply 來回調,args 已經是拼接好的 if (!(callingContext instanceof boundFunc)) return sourceFunc.apply(context, args); // 后面好想是針對 constructor 的,表示看不懂 var self = baseCreate(sourceFunc.prototype); var result = sourceFunc.apply(self, args); if (_.isObject(result)) return result; return self; };
在 _ 里類似 bind 的函數還有 _.partial 和 _.bindAll,只是使用的時候大同小異,就不多做介紹了,總之記住一句話,閉包無敵。
總結又是三個知識點,分別是隨機洗牌、分組和 bind 函數的實現,沒什么復雜的。
說到閉包,其實面試的時候問得最多的就是這個問題了,有啥優點,有啥缺點,如果是現場面,我直接手寫一串代碼,對面試官說:看,這就是閉包:
function add(m){ var fn = function(n){ return add( m + n ); } fn.toString = function(){ return m; } return fn; } add(2)(3)(4).toString(); //9
好像不對,這不是閉包,是柯里化。
參考Fisher–Yates shuffle
JavaScript 數組亂序
Underscore.js (1.8.3) 中文文檔
淺談 underscore 內部方法 group 的設計原理
歡迎來我的博客交流。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/83108.html
摘要:看完部分的源碼,首先迫不及待想跟大家分享的正是本文主題數組亂序。這是一道經典的前端面試題,給你一個數組,將其打亂,返回新的數組,即為數組亂序,也稱為洗牌問題。關于數組亂序,正確的解法應該是,復雜度。 前言 終于可以開始 Collection Functions 部分了。 可能有的童鞋是第一次看樓主的系列文章,這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時候,學到...
摘要:本文同步自我得博客前兩天在微博上看到的微博推薦了我的前兩篇文章,有點意外和驚喜。沒看過前兩篇博客的朋友可以戳這里源碼解析一源碼解析二上一篇文章介紹了的個函數的具體實現細節,今天將繼續介紹其他的函數。 本文同步自我得博客:http://www.joeray61.com 前兩天在微博上看到SF的微博推薦了我的前兩篇文章,有點意外和驚喜。作為一個菜鳥,真的是倍受鼓舞,我寫博客的動力也更充足了...
摘要:代碼實現代碼一測試用例輸出其中,代碼二測試用例輸出其中,參考資料洗牌算法學習筆記數組隨機排序洗牌算法給數組隨機排序洗牌算法原理 原理及步驟 1.定義一個數組(shuffled),長度(length)是原數組(arr)長度2.取 0 到 index (初始0) 隨機值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr...
閱讀 1118·2021-11-25 09:43
閱讀 1639·2021-09-13 10:25
閱讀 2592·2021-09-09 11:38
閱讀 3400·2021-09-07 10:14
閱讀 1714·2019-08-30 15:52
閱讀 641·2019-08-30 15:44
閱讀 3572·2019-08-29 13:23
閱讀 1974·2019-08-26 13:33