JavaScript中数组和对象的效率对比

Question

我有一个可能包含成千上万个对象的模型。我想知道存储它们并在拥有其ID时检索单个对象的最有效方法是什么。这些ID是长数字。

所以我考虑了两个选项。在选项一中，它是一个简单的数组，具有递增的索引。在选项2中，它是一个关联数组，可能还伴随着一个对象，如果这���产生差异。我的问题是，当我大多需要检索单个对象，但有时也需要循环遍历并排序时，哪一个更有效率。

选项一是非关联数组：

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];
    }
}

选项二，使用关联数组：

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

更新：

好的，我明白在第二个选项中使用数组是不可行的。所以第二个选项的声明行应该是：var a = {};，唯一的问题是：使用数组或对象来检索具有给定id的对象哪个性能更好，其中id是键。

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

- Moshe Shaham

---

这可能有所帮助：https://dev59.com/imYr5IYBdhLWcg3w6OGd - Sudhir Bastakoti

你是否需要始终保持有序集合？如果是，那么除了使用数组（尽管不像你目前所做的那样使用索引）之外别无选择。 - Jon

@Jon，实际上我有。你所说的“像你现在这样做”是什么意思？ - Moshe Shaham

@MosheShaham：数组（应该）从0开始具有连续的索引。如果您使用数组，请不要做其他事情。 - Jon

我猜这个基准测试将回答你问题的第一部分：http://jsben.ch/#/Y9jDP - EscapeNetscape

这个问题大约是在十年前被提出的，但是现在你可以在性能优化方面使用Web Assembly（Web 汇编语言）。 - Anatoly

Answer 1

简短版：数组通常比对象更快。但没有100％正确的解决方案。

2017年更新-测试与结果

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'});
}

原始帖子 - 说明

您的问题中存在一些误解。

在Javascript中没有关联数组。只有数组和对象。

这些是数组：

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

这也是一个数组：

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

基本上它是一个带有空洞的数组，因为每个数组都具有连续的索引。它比没有空洞的数组慢。但是手动迭代数组甚至更慢（大多数情况下）。

这是一个对象：

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

这里是三种可能性的性能测试:

查找数组 vs 稀疏数组 vs 对象性能测试

在Smashing Magazine上有一篇关于这些话题的优秀阅读材料：编写快速高效内存的JavaScript

- Alp

---

@Moshe 所以所有关于JavaScript性能的讨论都应该结束了。:P - deceze

这取决于您正在处理的数据和数据大小。非常小的数据集和小对象将使用数组表现得更好。如果您正在处理大型数据集中的查找，其中使用对象作为映射，则对象更有效率。http://jsperf.com/array-vs-object-performance/35 - f1v

同意f1v的观点，但第35个修订版本在测试中有一个缺陷： if (a1[i].id = id) result = a1[i]; 应该改为: if (a1[i].id === id) result = a1[i]; 测试http://jsperf.com/array-vs-object-performance/37 纠正了这个问题。 - Charles Byrne

此答案可以通过在此帖子中总结jsPerf的结论来改进 - 尤其是因为jsPerf的结果才是这个问题的真正答案。其他内容是多余的。这在jsPerf宕机时更为相关（比如现在）。http://meta.stackexchange.com/questions/8231/are-answers-that-just-contain-links-elsewhere-really-good-answers - Jeff

测试有缺陷。「数组」方法在实际中并非如此缓慢。首先，在生成元素时，仅当o和a2没有该元素时才会获得新元素，而总是推入a1的新元素。如果生成两次相同的数字，则不会添加到o和a2中，但将被推入a1中。虽然不太可能，但仍需考虑。其次，在对a1进行测试时，任何正常人都会在发现该项后退出循环...这显着改变了结果。自行查看。 - dodov

Answer 2

这实际上并不是一个性能问题，因为数组和对象的工作方式非常不同（或者至少应该是如此）。数组具有连续的索引0..n，而对象将任意键映射到任意值。如果你想提供特定的键，唯一的选择是对象。如果您不关心键，则应使用数组。

如果您尝试在数组上设置任意（数值）键，则实际上会导致性能损失，因为从行为上讲，数组将填充所有中间索引：

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

_{（请注意，数组并不实际上包含99个undefined值，但由于您在某些时候应该迭代数组，因此它会表现出这种行为。）}

两个选项的文字说明非常清楚它们如何使用：

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

- deceze

---

我不想提供特定的键。我想知道哪个表现更好，然后我会使用它。好的，在第二个选项中，数组是不可能的。但是对象与非关联数组呢？ - Moshe Shaham

@Moshe 在Javascript中不存在非关联数组这种东西。如果你需要键（数字或字符串），请使用对象。如果你只需要一个（有序）列表，请使用数组。没有讨论的余地。性能不是问题。如果性能至关重要，而且你可以接受任何一种键，那么请尝试哪种方法更适合你。 - deceze

我想知道哪种方式更有效：从数组中检索一个对象（通过循环）还是从“关联”对象中检索，其中id是键。如果我的问题不清楚，我很抱歉... - Moshe Shaham

@Moshe 如果你通过键访问任何对象或数组中的内容，它总是比循环容器尝试查找所需内容快得多。在数组或对象中通过键访问项之间的差异可能是可以忽略不计的。无论如何，循环显然都更糟糕。 - deceze

@deceze — 关于“使用数组保存用户对象并且需要通过循环获取基于user_id的用户对象”和“对象具有user_id作为键，因此可以使用user_id作为键来访问用户对象”的问题，哪一个在性能方面更好？对此有任何建议将不胜感激 :) - Rayon

Answer 3

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

var myMap = new Map();

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

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

你可以使用一个shim（https://github.com/es-shims/es6-shim）来使用ES6的功能。

性能将根据浏览器和场景而异。但这里有一个例子，其中Map是最有效的：https://jsperf.com/es6-map-vs-object-properties/2

---

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

- sandstrom

---

有任何支持这个观点的资源吗？根据我的观察，ES6中的Set比数组更快，但Map比对象和数组都要慢。 - Steel Brain

这更多是“语义化”的问题，而不是性能问题，这也是问题所在。 - AlexG

@AlexG，我很确定标题清楚地说明了“效率”。 - Qix - MONICA WAS MISTREATED

Answer 4

在NodeJS中，如果你知道ID，那么遍历数组与object[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');

结果如下：

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

即使寻找的ID是数组/对象中的第一个：

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

- Paweł

Answer 5

我尝试将这个问题提升到下一个维度，字面意思是更高的维度。

给定一个二维数组，在其中x轴和y轴总是相同的长度，那么以下哪个方法更快呢？

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

```array[firstIndex][secondIndex]```

b) 将每行的所有单元格作为单独的数组存储，并且使用一维数组查找单元格，即：

```array[(row * width) + column]```

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

或者

b) 创建一个包含x和y坐标字符串表示的对象，然后在该对象上进行单个查找，即：

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

结果：
事实证明，在数组上进行两个数字索引查找比在对象上进行一个属性查找要快得多。

此处结果：

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

- Davem M

Answer 6

这取决于用途。如果要查找对象，速度非常快。这里有一个Plunker示例，用于测试数组和对象查找的性能。 https://plnkr.co/edit/n2expPWVmsdR3zmXvX4C?p=preview 你会发现： 在5,000个长度的数组集合中查找5,000个项目需要超过3,000毫秒。 然而，在拥有5,000个属性的对象中查找5,000个项目只需要2或3毫秒。 并且创建对象树并不会有太大的差异。

- Mehmet Otkun

Answer 7

我遇到了一个类似的问题，需要从一个仅限于x项的事件源中存储实时K线图。我可以将它们存储在一个对象中，其中每个蜡烛的时间戳充当键，而蜡烛本身充当值。另一个可能性是将其存储在数组中，其中每个项目都是蜡烛本身。实时蜡烛图的一个问题是它们会在相同的时间戳上不断发送更新，其中最新的更新包含最新的数据，因此您要么更新现有项目，要么添加新项目。因此，下面的解决方案尝试结合了所有3种可能性。平均而言，以下解决方案中的数组至少快4倍。随意尝试。

"use strict";

const EventEmitter = require("events");
let candleEmitter = new EventEmitter();

//Change this to set how fast the setInterval should run
const frequency = 1;

setInterval(() => {
    // Take the current timestamp and round it down to the nearest second
    let time = Math.floor(Date.now() / 1000) * 1000;
    let open = Math.random();
    let high = Math.random();
    let low = Math.random();
    let close = Math.random();
    let baseVolume = Math.random();
    let quoteVolume = Math.random();

    //Clear the console everytime before printing fresh values
    console.clear()

    candleEmitter.emit("candle", {
        symbol: "ABC:DEF",
        time: time,
        open: open,
        high: high,
        low: low,
        close: close,
        baseVolume: baseVolume,
        quoteVolume: quoteVolume
    });



}, frequency)

// Test 1 would involve storing the candle in an object
candleEmitter.on('candle', storeAsObject)

// Test 2 would involve storing the candle in an array
candleEmitter.on('candle', storeAsArray)

//Container for the object version of candles
let objectOhlc = {}

//Container for the array version of candles
let arrayOhlc = {}

//Store a max 30 candles and delete older ones
let limit = 30

function storeAsObject(candle) {

    //measure the start time in nanoseconds
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;

    // Create the object structure to store the current symbol
    if (typeof objectOhlc[symbol] === 'undefined') objectOhlc[symbol] = {}

    // The timestamp of the latest candle is used as key with the pair to store this symbol
    objectOhlc[symbol][time] = candle;

    // Remove entries if we exceed the limit
    const keys = Object.keys(objectOhlc[symbol]);
    if (keys.length > limit) {
        for (let i = 0; i < (keys.length - limit); i++) {
            delete objectOhlc[symbol][keys[i]];
        }
    }

    //measure the end time in nano seocnds
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]

    console.log("Storing as objects", end - start, Object.keys(objectOhlc[symbol]).length)
}

function storeAsArray(candle) {

    //measure the start time in nanoseconds
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;
    if (typeof arrayOhlc[symbol] === 'undefined') arrayOhlc[symbol] = []

    //Get the bunch of candles currently stored
    const candles = arrayOhlc[symbol];

    //Get the last candle if available
    const lastCandle = candles[candles.length - 1] || {};

    // Add a new entry for the newly arrived candle if it has a different timestamp from the latest one we storeds
    if (time !== lastCandle.time) {
        candles.push(candle);
    }

    //If our newly arrived candle has the same timestamp as the last stored candle, update the last stored candle
    else {
        candles[candles.length - 1] = candle
    }

    if (candles.length > limit) {
        candles.splice(0, candles.length - limit);
    }

    //measure the end time in nano seocnds
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]


    console.log("Storing as array", end - start, arrayOhlc[symbol].length)
}

结论 这里的上限是10。

Storing as objects 4183 nanoseconds 10
Storing as array 373 nanoseconds 10

- PirateApp

Answer 8

1. 索引字段（具有数字键的字段）存储为对象内部的数组。因此查找时间为O（1）

2. 对于查找数组，它也是O（1）

3. 遍历对象数组并测试其ID是否与提供的ID相同是一项O（n）操作。

- badunius