问题描述
当用作散列时,JavaScript 的数组访问的大 O 是什么?
What's the big O for JavaScript's array access when used as a hash?
例如
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?
希望 JS 引擎不会在内部使用 O(n) 的线性搜索,但这是确定的吗?
One can hope JS engines will not use a linear search internally O(n), but is this for sure?
推荐答案
在 JavaScript 中访问对象属性和数组元素在语法上假定在 恒定时间:O(1).ECMAScript 规范不保证性能特征,但所有现代 JavaScript 引擎都在恒定时间内检索对象属性.
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.
下面是一个简单的例子,展示了当容器大 1000 倍时访问时间是如何增长的:
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');
在 Firebug、Firefox 3.6.10(Mac OS X 10.6.4 - 2.93Ghz Intel Core 2 Duo)中的结果:
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
Chrome 开发工具 6.0.472 中的结果:
Results in Chrome Dev Tools 6.0.472:
10k Accesses from largeObject: 15ms
10k Accesses from smallObject: 15ms
Windows 7 上带有 Firebug Lite 的 Internet Explorer 8.0.7600
Internet Explorer 8.0.7600 with Firebug Lite on Windows 7
10k Accesses from largeObject: 250ms
10k Accesses from smallObject: 219ms
这篇关于当用作散列时,JavaScript 数组的大 O 是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!