JavaScript中的数组与对象效率

I have a model with possibly thousands of objects. I was wondering what would be the most efficient way of storing them and retrieving a single object once I have it's id. The id's are long numbers.

我有一个可能有数千个物体的模型。我想知道存储它们的最有效方法是什么，并且一旦我拥有它的id就检索单个对象。 id是长号。

So these are the 2 options I was thinking about. in option one it's a simple array with an incrementing index. in option 2 it's an associative array and maybe an object, if it makes a difference. My question is which one is more efficient, when I mostly need to retrieve a single object, but also sometimes loop through them and sort.

所以这些是我想到的两个选项。在选项一中，它是一个带有递增索引的简单数组。在选项2中，它是一个关联数组，也许是一个对象，如果它有所不同。我的问题是哪一个更有效率，当我主要需要检索单个对象，但有时也循环遍历它们并进行排序。

Option one with non associative array:

具有非关联数组的选项一：

var a = [{id: 29938, name: 'name1'},
         {id: 32994, name: 'name1'}];
function getObject(id) {
    for (var i=0; i < a.length; i++) {
        if (a[i].id == id) 
            return a[i];
    }
}

Option two with associative array:

选项二与关联数组：

var a = [];  // maybe {} makes a difference?
a[29938] = {id: 29938, name: 'name1'};
a[32994] = {id: 32994, name: 'name1'};
function getObject(id) {
    return a[id];
}

Update:

更新：

OK, I get that using an array in the second option is out of the question. So the declaration line the second option should really be: var a = {}; and the only question is: what is performing better in retrieving an object with a given id: an array or an object where the id is the key.

好的，我知道在第二个选项中使用数组是不可能的。因此第二个选项的声明行应该是：var a = {};唯一的问题是：在检索具有给定id的对象时表现更好：数组或id为关键字的对象。

and also, will the answer change if i will have to sort the list many times?

而且，如果我必须多次对列表进行排序，答案会改变吗？

6 个解决方案

#1

The short version: Arrays are mostly faster than objects. But there is no 100% correct solution.

简短版本：数组大多比对象快。但没有100％正确的解决方案。

Update 2017 - Test and Results

var a1 = [{id: 29938, name: 'name1'}, {id: 32994, name: 'name1'}];

var a2 = [];
a2[29938] = {id: 29938, name: 'name1'};
a2[32994] = {id: 32994, name: 'name1'};

var o = {};
o['29938'] = {id: 29938, name: 'name1'};
o['32994'] = {id: 32994, name: 'name1'};

for (var f = 0; f < 2000; f++) {
    var newNo = Math.floor(Math.random()*60000+10000);
    if (!o[newNo.toString()]) o[newNo.toString()] = {id: newNo, name: 'test'};
    if (!a2[newNo]) a2[newNo] = {id: newNo, name: 'test' };
    a1.push({id: newNo, name: 'test'});
}

Original Post - Explanation

There are some misconceptions in your question.

你的问题有一些误解。

There are no associative arrays in Javascript. Only Arrays and Objects.

These are arrays:

这些是数组：

var a1 = [1, 2, 3];
var a2 = ["a", "b", "c"];
var a3 = [];
a3[0] = "a";
a3[1] = "b";
a3[2] = "c";

This is an array, too:

这也是一个数组：

var a3 = [];
a3[29938] = "a";
a3[32994] = "b";

It's basically an array with holes in it, because every array does have continous indexing. It's slower than arrays without holes. But iterating manually through the array is even slower (mostly).

它基本上是一个带孔的数组，因为每个数组都有连续的索引。它比没有孔的阵列慢。但是手动遍历数组甚至更慢（大多数情况下）。

This is an object:

这是一个对象：

var a3 = {};
a3[29938] = "a";
a3[32994] = "b";

Here is a performance test of three possibilities:

以下是三种可能性的性能测试：

Lookup Array vs Holey Array vs Object Performance Test

An excellent read about these topics at Smashing Magazine: Writing fast memory efficient JavaScript

Smashing Magazine上关于这些主题的精彩读物：编写快速内存高效的JavaScript

#2

It's not really a performance question at all, since arrays and objects work very differently (or are supposed to, at least). Arrays have a continuous index 0..n, while objects map arbitrary keys to arbitrary values. If you want to supply specific keys, the only choice is an object. If you don't care about the keys, an array it is.

它根本不是一个性能问题，因为数组和对象的工作方式非常不同（或至少应该如此）。数组具有连续索引0..n，而对象将任意键映射到任意值。如果要提供特定键，唯一的选择是对象。如果你不关心键，那就是一个数组。

If you try to set arbitrary (numeric) keys on an array, you really have a performance loss, since behaviourally the array will fill in all indexes in-between:

如果您尝试在数组上设置任意（数字）键，则确实会导致性能下降，因为在行为上，数组将填充中间的所有索引：

> foo = [];
  []
> foo[100] = 'a';
  "a"
> foo
  [undefined, undefined, undefined, ..., "a"]

_{(Note that the array does not actually contain 99 undefined values, but it will behave this way since you're [supposed to be] iterating the array at some point.)}

（请注意，数组实际上并不包含99个未定义的值，但它会以这种方式运行，因为您[应该]在某个时刻迭代数组。）

The literals for both options should make it very clear how they can be used:

这两个选项的文字应该非常清楚如何使用它们：

var arr = ['foo', 'bar', 'baz'];     // no keys, not even the option for it
var obj = { foo : 'bar', baz : 42 }; // associative by its very nature

#3

With ES6 the most performant way would be to use a Map.

使用ES6，最高效的方法是使用Map。

var myMap = new Map();

myMap.set(1, 'myVal');
myMap.set(2, { catName: 'Meow', age: 3 });

myMap.get(1);
myMap.get(2);

You can use ES6 features today using a shim (https://github.com/es-shims/es6-shim).

您现在可以使用垫片（https://github.com/es-shims/es6-shim）使用ES6功能。

Performance will vary depending on the browser and scenario. But here is one example where Map is most performant: https://jsperf.com/es6-map-vs-object-properties/2

性能将根据浏览器和方案而有所不同。但是这里有一个地图性能最高的例子：https：//jsperf.com/es6-map-vs-object-properties/2

---

REFERENCE https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

参考https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

#4

I tried to take this to the next dimension, literally.

从字面上看，我试图把它带到下一个维度。

Given a 2 dimensional array, in which the x and y axes are always the same length, is it faster to:

给定一个二维数组，其中x和y轴总是相同的长度，它更快：

a) look up the cell by creating a two dimensional array and looking up the first index, followed by the second index, i.e:

a）通过创建二维数组并查找第一个索引，然后查找第二个索引来查找单元格，即：

var arr=[][]    
var cell=[x][y]    

or

要么

b) create an object with a string representation of the x and y coordinates, and then do a single lookup on that obj, i.e:

b）使用x和y坐标的字符串表示创建一个对象，然后对该obj进行单个查找，即：

var obj={}    
var cell = obj['x,y']    

Result:
Turns out that it's much faster to do two numeric index lookups on the arrays, than one property lookup on the object.

结果：结果表明，对数组进行两次数字索引查找要比对象上的一次属性查找快得多。

Results here:

结果在这里：

http://jsperf.com/arr-vs-obj-lookup-2

http://jsperf.com/arr-vs-obj-lookup-2

#5

It depends on usage. If the case is lookup objects is very faster.

这取决于使用情况。如果是查找对象的情况非常快。

Here is a Plunker example to test performance of array and object lookups.

这是一个测试数组和对象查找性能的Plunker示例。

https://plnkr.co/edit/n2expPWVmsdR3zmXvX4C?p=preview

https://plnkr.co/edit/n2expPWVmsdR3zmXvX4C?p=preview

You will see that; Looking up for 5.000 items in 5.000 length array collection, take over 3000 milisecons

你会看到;在5.000长度阵列集中查找5.000个项目，需要超过3000个milisecons

However Looking up for 5.000 items in object has 5.000 properties, take only 2 or 3 milisecons

但是在对象中查找5.000个项目有5.000个属性，只需要2或3个milisecons

Also making object tree don't make huge difference

制作对象树也没有太大的区别

#6

In NodeJS if you know the ID, the looping through the array is very slow compared to object[ID].

在NodeJS中，如果您知道ID，则与对象[ID]相比，通过数组的循环非常慢。

const uniqueString = require('unique-string');
const obj = {};
const arr = [];
var seeking;

//create data
for(var i=0;i<1000000;i++){
  var getUnique = `${uniqueString()}`;
  if(i===888555) seeking = getUnique;
  arr.push(getUnique);
  obj[getUnique] = true;
}

//retrieve item from array
console.time('arrTimer');
for(var x=0;x<arr.length;x++){
  if(arr[x]===seeking){
    console.log('Array result:');
    console.timeEnd('arrTimer');
    break;
  }
}

//retrieve item from object
console.time('objTimer');
var hasKey = !!obj[seeking];
console.log('Object result:');
console.timeEnd('objTimer');

And the results:

结果如下：

Array result:
arrTimer: 12.857ms
Object result:
objTimer: 0.051ms

Even if the seeking ID is the first one in the array/object:

即使搜索ID是数组/对象中的第一个：

Array result:
arrTimer: 2.975ms
Object result:
objTimer: 0.068ms