当用作散列时，JavaScript数组的大O是什么？ [英] What's the big O for JavaScript's array when used as a hash?

问题描述

例如，

  var x = []; 
 for（var i = 0; i <100000; i ++）{
 x [i.toString（）+'a'] = 123; //使用字符串来说明xα
} 
 alert（x ['9999a']）; //线性搜索？ 
  

人们可以希望JS引擎不会在内部使用线性搜索O（n），但这是为了在JavaScript中访问对象属性和数组元素在句法上被假定为在 /en.wikipedia.org/wiki/Time_complexity#Constant_timerel =noreferrer>常量时间：O（1）。在ECMAScript规范中不保证性能特征，但所有现代JavaScript引擎都会在一段时间内检索对象属性。

下面是一个简单的例子，显示了当容器是x1000倍大：

  var largeObject = {}; 
 var smallObject = {}; 
 
 var x，i; 
 
 for（i = 0; i <1000000; i ++）{
 largeObject ['a'+ i] = i; 
} 
 
 for（i = 0; i <1000; i ++）{
 smallObject ['b'+ i] = i; 
} 
 
 console.time（'10k来自largeObject'）; 
 for（i = 0; i <10000; i ++）x = largeObject ['a'+（i％1000000）]; 
 console.timeEnd（'10k来自largeObject'）; 
 
 console.time（'10k来自smallObject'）; 
 for（i = 0; i <10000; i ++）x = largeObject ['a'+（i％1000）]; 
 console.timeEnd（'10k来自smallObject'）; 
  

Firebug，Firefox 3.6.10（Mac OS X 10.6.4 - 2.93Ghz Intel Core 2 Duo）：

  10k来自largeObject的访问：22ms 
 10k来自smallObject的访问：19ms 
  

Chrome Dev Tools 6.0.472中的结果：

  10k来自largeObject的访问：15ms 
 10k来自smallObject的访问：15ms 
  

Internet Explorer 8.0.7600和Windows 7上的Firebug Lite

  10k来自largeObject的访问：250ms 
 10k来自smallObject的访问： 219ms 
  

What's the big O for JavaScript's array access when used as a hash?

For example,

var x= [];
for(var i=0; i<100000; i++){
   x[i.toString()+'a'] = 123; // using string to illustrate x[alpha]
}
alert(x['9999a']); // linear search?

One can hope JS engines will not use a linear search internally O(n), but is this for sure?

解决方案

Accessing object properties and array elements in JavaScript is syntacticly assumed to be done in constant time: O(1). Performance characteristics are not guaranteed in the ECMAScript specification, but all the modern JavaScript engines retrieve object properties in constant time.

Here's a simple example showing how access times grow when the container is x1000 times bigger:

var largeObject = {};
var smallObject = {};

var x, i;

for (i = 0; i < 1000000; i++) {
   largeObject['a' + i] = i;
}

for (i = 0; i < 1000; i++) {
   smallObject['b' + i] = i;
}

console.time('10k Accesses from largeObject');
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)];
console.timeEnd('10k Accesses from largeObject');

console.time('10k Accesses from smallObject');
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)];
console.timeEnd('10k Accesses from smallObject');

Results in Firebug, Firefox 3.6.10 (Mac OS X 10.6.4 - 2.93Ghz Intel Core 2 Duo):

10k Accesses from largeObject: 22ms
10k Accesses from smallObject: 19ms

Results in Chrome Dev Tools 6.0.472:

10k Accesses from largeObject: 15ms
10k Accesses from smallObject: 15ms

Internet Explorer 8.0.7600 with Firebug Lite on Windows 7

10k Accesses from largeObject: 250ms
10k Accesses from smallObject: 219ms

这篇关于当用作散列时，JavaScript数组的大O是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！