快捷導(dǎo)航

從數(shù)據(jù)結(jié)構(gòu)分析看：用for each...in 比 for...in 要快些

更新時(shí)間：2013年04月17日 11:21:34 作者：

本篇文章小編將為大家介紹，從數(shù)據(jù)結(jié)構(gòu)分析看：用for each...in 比 for...in 要快些。需要的朋友可以參考一下

之前聽說火狐的JS引擎支持for each in的語法，例如下述的代碼：

var arr = [10,20,30,40,50];
for each(var k in arr)
    console.log(k);

即可直接遍歷出arr數(shù)組的內(nèi)容。

由于只有FireFox才支持，所以幾乎所有的JS代碼都不用這一特征。

不過在ActionScript里天生就支持for each的語法，不論Array還是Vector，還是Dictionary，只要是可枚舉的對(duì)象都可以for in和for each in。

之前并沒有感覺有太大的差異，為了懶得敲一個(gè)each單詞，一直用熟悉的for in來遍歷。

不過今天仔細(xì)琢磨了會(huì)，從數(shù)據(jù)結(jié)構(gòu)的角度分析了下，覺得for in和for each in效率上有著本質(zhì)的區(qū)別，無論是JS還是AS。

原因很簡(jiǎn)單：Array不是真正意義上的數(shù)組！

何為真正意義的數(shù)組？當(dāng)然就是傳統(tǒng)語言里type[]定義的數(shù)據(jù)類型，所有元素都是連續(xù)保存的。

“Array”雖然也是數(shù)組的意思，但熟悉JS的都知道，它其實(shí)是個(gè)非線性的偽數(shù)組，下標(biāo)可以是任意數(shù)字。寫入arr[1000000]并非真正申請(qǐng)容納一百萬個(gè)元素的空間，而是把1000000轉(zhuǎn)換成相應(yīng)的哈希值，對(duì)應(yīng)到很小一塊儲(chǔ)存空間里，從而節(jié)省了大量?jī)?nèi)存。

例如有如下數(shù)組：

復(fù)制代碼代碼如下:

var arr = [];
  arr[10] = 1000;
  arr[20] = 2000;
  arr[30] = 5000;
  arr[40] = 8000;
  arr[200] = 9000;

用for...in遍歷Array，是個(gè)很累贅的過程：

遍歷時(shí)每次訪問arr[k]，都要進(jìn)行一次Hash(k)計(jì)算，根據(jù)散列表的容量取模，最終在沖突鏈表里找到結(jié)果。

如果支持for each...in的語法，其內(nèi)部的數(shù)據(jù)結(jié)構(gòu)就決定了會(huì)快很多：

Array里儲(chǔ)存存了keys的列表，也把每個(gè)values值作為鏈表關(guān)聯(lián)起來。每當(dāng)有值添加或刪除，就更新其鏈接關(guān)系。

當(dāng)for each...in遍歷時(shí)，只需從第一個(gè)節(jié)點(diǎn)往后迭代即可，無需任何Hash計(jì)算。

當(dāng)然，對(duì)于AS3里Vector這樣的線性數(shù)組來說，兩者相差不大；同理，HTML5里支持二進(jìn)制的數(shù)組ArrayBuffer也是如此。不過從理論上來看，即使arr是個(gè)連續(xù)的線性數(shù)組，for each in還是要快一點(diǎn)：

for...in遍歷時(shí)，每次訪問arr[k]都要進(jìn)行下標(biāo)越界檢查；而for each in則根據(jù)內(nèi)部鏈表，直接從底層反饋出迭代變量，節(jié)省了越界檢查的過程。

您可能感興趣的文章: