Javascript - 更快：線性列表搜索或獲取對象值？

-5

a = ['1','2','3','4','5'] 
for(var i = 0; i < a.length; i++) { if (a[i] == 3) console.log('found it!') }

和

a = {'1': true, '2': true, '3': true, '4': true} 
a['3']

這將是更快，爲什麼？

來源

2012-06-11 CamelCamelCamel

爲什麼不自己嘗試一下？在循環中添加這兩種方法可以多次調用它，並且更快地調用它！ – Veger

第二個應該更快。 – gdoron

試試[JSPerf]（http://jsperf.com/） – Joseph

的對象查找平均會快很多試圖找到一個隨機元素時，尤其是當你通過大量的搜索項目。這是因爲底層算法是B-tree search，它的時間複雜度爲O（log n），並允許它快速查找項目成員資格，而不必根據對象中的每個元素進行檢查。

這與在數組中搜索時相反，在決定是否不具有線性時間複雜度O（n）的數組之前，必須檢查每個元素。

這裏是基準顯示對象的查找速度更快：http://jsperf.com/array-vs-objv2/6

來源

2012-06-11 22:12:47 Trevor

a = {'1': true, '2': true, '3': true, '4': true} 
if (a['3'] === true) { 
    console.log("found it"); 
}

將在大多數情況下快，然後

a = ['1','2','3','4','5'] 
for(var i = 0; i < a.length; i++) { 
    if (a[i] == 3) { 
    console.log('found it!') 
    } 
}

因爲第二個可能是通過數組的所有值需要循環。

來源

2012-06-11 22:01:09 TheHippo

我喜歡downvotes沒有任何評論:-) – TheHippo

在第一次你會測試的財產的存在。如果'3'不是對象的一部分，那麼它將是未定義的 – aepheus

以及第一個示例是如何找到的？它可能會循環所有的值，但內部/不可見... – Veger

我修改後的代碼象下面這樣jsPerf http://jsperf.com/array-vs-objv2

比較它們的性能測試1日前使代碼相當於兩個：

測試設置：

var a = []; 
var b = {}; 

for (var i = 1; i <= 100000; i++) { 
    a.push(i); 
    b[''+i] = true; 
}

使用數組：

for(var i = 0; i < a.length; i++) { 
    if (a[i] === 99999) { 
    console.log(true); 
    return; 
    } 
}

使用對象：（較快）

console.log(b['99999']);

試驗2：

使用數組：（較快）

a = ['1','2','3','4','5'] 
for(var i = 0; i < a.length; i++) { 
    if (a[i] === 3) { 
    console.log(true); 
    return; 
    } 
}

使用對象：

a = {'1': true, '2': true, '3': true, '4': true, '5': true}; 
console.log(a['3']);

Resut：（如特雷弗指出）陣列搜索會更快更少的項目，但較大的列表上查找時..陣列比較慢，因爲線性搜索的。

來源

2012-06-11 22:04:01

這不考慮大型搜索或隨機訪問。這是一個更好的基準，揭示了對象查找確實更快：http://jsperf.com/array-vs-objv2/6 – Trevor

@Trevor你是對的..看到更新後。感謝您的更正。 –

關聯數組將執行得更快，它只需要一個邏輯操作。儘管爲了實現這一點，它需要更多地存儲在內存中以將密鑰與價值鏈接起來。這大致相當於一個散列表vs數組參數。

缺點，較慢的插入和較高的內存使用。查找的速度取決於引擎。

https://developers.google.com/v8/design

既設置和搜索

完全分析： http://jsperf.com/array-vs-objv2/5

來源

2012-06-11 22:12:02 aepheus

關聯數組在JavaScript中不存在，只有數字索引的數組和對象。只是有點挑剔， –

說到功能，js中的對象是一個關聯數組。 – aepheus

不完全：對象可以直接添加自定義方法（不是通過原型），並且缺少'indexOf'方法。是的，對象_can_和其他語言中的關聯數組或結構是一樣的，但我們在這裏討論JS。當涉及到術語時，最好做一個儘可能的肛門，否則人們傾向於將對象和數組視爲同一事物，這會導致問題和普遍的混淆。 –

退房對象的屬性和數組元素的這個benchmark figure

訪問時間接近

在你的第一種情況下，有三個訪問陣列項目的次數

而在第二種情況下，只有一次訪問對象屬性

所以我認爲第二個應該更快

來源

2012-06-11 22:13:39 xvatar

FF3，IE7，Chrome1，Opera 9？ _曾經有一次......_：D – Andreas

@Andreas是啊，它很古老..但是我認爲js的基本實現自那時以來沒有多大變化..糾正我，如果我錯了.. – xvatar

不知道JavaScript的所有黑魔法運作，我可以說像a['3']不使用線性搜索。

JavaScript是否具有對該元素的直接引用，因此它甚至不需要執行搜索？也許。如果是這樣，它會使用它來查找比線性搜索更快的a['3']，儘管它可能會花費更多的內存。（我認爲這就是它的實際做法。）

如果沒有，它實際上會搜索您的數據結構，它幾乎肯定不會使用簡單的線性搜索。可能有一些內部工作，或某種二叉樹搜索或其他一些混淆。

來源

2012-06-11 22:16:19 CWSpear

Javascript - 更快：線性列表搜索或獲取對象值？

回答

相關問題