DIV CSS 佈局教程網

從資料結構看 for each in 為何比 for in 快得多
編輯:關於JavaScript     

仔細琢磨之後發現,for in 和 for each in 在效率上有著本質的差異,無論是 JavaScript 還是 ActionScript。原因歸結起來一句話:Array 不是真正意義上的陣列。

兩種語法

Firefox 的 JS 引擎曾經支援 for each in:

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

它會直接遍歷出元素的值,而不是索引。由於只有 Firefox 支援,幾乎所有跨瀏覽器的 JS 程式碼都不用這個語法(值得一提的是,它在 Firefox 也已於版本 57 移除)。

ActionScript 則天生支援 for each,不論 Array、Vector 還是 Dictionary,只要是可列舉的物件都能用。因為偷懶不想多敲一個 each,長期以來我都用熟悉的 for in 來遍歷,也沒感覺有多大差異。仔細分析之後才發現,兩者的差距是結構性的。

何謂真正的陣列

傳統語言裡用 type[] 定義的資料型別,所有元素在記憶體中連續保存,這才是真正的陣列。

而 JavaScript 的「Array」雖然名字裡有陣列,熟悉它的人都知道那其實是個非線性的偽陣列:索引可以是任意數字,寫入 arr[1000000] 並不會真的配置能容納一百萬個元素的空間,而是把 1000000 轉換成雜湊值,對應到很小的一塊儲存空間,因而省下大量記憶體。例如:

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

for...in 的成本在哪

用 for...in 遍歷這種物件,是個很累贅的過程:

每次存取 arr[k],都要執行一次 Hash(k) 計算,根據雜湊表容量取模定位,如果發生碰撞還得繼續尋找最終的值。這意味著索引型別的遍歷,實際上被當成雜湊表查詢在做。

更麻煩的是 for...in 不只列舉索引,它會沿著原型鏈往上走,把繼承來的可列舉屬性也一併列出來。這在實務上是 bug 的來源:只要在 Array.prototype 上掛了任何東西(某些舊函式庫真的這麼做),所有 for...in 迴圈都會多出意料之外的項目。

for each...in 為何更快

支援 for each...in 的環境,其內部資料結構就決定了它會快很多:

Array 裡直接把每個值作為節點,通過鏈表關聯起來維護。每當有值新增或刪除,就更新其連結關係。當 for each...in 遍歷時,只需從第一個節點往後迭代即可,完全不必做任何雜湊計算,也不會碰到原型鏈上的雜質。

線性陣列的情況

對於 AS3 裡 Vector 這樣的線性陣列,兩者差距不大;HTML5 的 ArrayBuffer 及其型別化陣列視圖也是同理。不過從理論上來看,即使 arr 是連續的線性陣列,for each in 還是要快一點:

for...in 遍歷時,每次存取 arr[k] 都要進行一次索引越界檢查;而 for each in 依據內部鏈表直接從底層回饋出迭代變數,省下了越界檢查的過程。

今天的結論

這套分析在今天有幾個必要的更新。

其一,for each in 已不是選項。它是 SpiderMonkey 的非標準擴充,Firefox 57 之後彻底移除,ES 標準裡從來沒有它。ES6 引進的 for...of 才是正確的替代品,它遍歷的是元素值,語意與當年的 for each in 相近,而且是跨環境通用的標準語法。

其二,現代引擎的 Array 已經是真正的連續陣列。V8、SpiderMonkey、JavaScriptCore 都有多層的內部表示:只有密集數字索引的陣列會存成連續的記憶體區塊(V8 稱作 PACKED_ELEMENTS),只有在出現稀疏索引或 named property 時才退化為字典模式。所以「JS 陣列一定是雜湊表」這個前提,在今天已經不成立。

其三,遍歷時機制的效能排序早有定論。實測上大致是:傳統 for (var i = 0; ...) 迴圈最快,for...of 次之(ES6 的迭代器協議有額外開銷),forEach 因為函式呼叫與閉包配置而較慢,for...in 則因為前述的雜湊查表與原型鏈走訪而敬陪末座,同時也是最容易出錯的一個。

所以結論其實沒變,只是理由更新了:遍歷陣列請用 for...of,永遠不要用 for...in。後者是為列舉物件屬性而設計的,拿來跑陣列既慢又容易踩到原型鏈的雷。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved