166

我有一个可能包含数千个对象的模型。我想知道一旦我有了它的 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 为键的对象。

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

4

8 回答 8

166

简短版本：数组通常比对象快。但是没有 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

于 2013-06-25T11:08:35.073 回答
28

这根本不是一个性能问题，因为数组和对象的工作方式非常不同（或者至少应该如此）。数组具有连续索引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
于 2013-06-25T10:41:21.910 回答
14

对于 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

于 2015-09-20T11:10:04.830 回答
7

在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 是数组/对象中的第一个 ID：

Array result:
arrTimer: 2.975ms
Object result:
objTimer: 0.068ms
于 2017-11-02T10:07:46.557 回答
5

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

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

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

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

或者

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

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

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

结果在这里：

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

于 2015-02-14T19:50:45.853 回答
3

这取决于使用情况。如果是查找对象，则速度非常快。

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

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

你会看到的；在5.000长度的数组集合中查找5.000项，接管毫秒3000

然而，在对象中查找 5.000 个项目有5.000个属性，仅取2或3毫秒

也使对象树没有太大的区别

于 2016-05-24T15:15:17.500 回答
1

我遇到了一个类似的问题，我需要从仅限于 x 个项目的事件源存储实时烛台。我可以将它们存储在一个对象中，其中每个蜡烛的时间戳将充当键，而蜡烛本身将充当值。另一种可能性是我可以将它存储在一个数组中，其中每个项目都是蜡烛本身。关于实时蜡烛的一个问题是，它们会在最新更新保存最新数据的同一时间戳上不断发送更新，因此您要么更新现有项目，要么添加新项目。所以这是一个很好的基准，它试图结合所有 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
于 2018-11-17T12:03:23.840 回答
0

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

  2. 对于查找数组也是如此，它是 O(1)

  3. 遍历一组对象并根据提供的对象测试它们的 id 是一个 O(n) 操作。

于 2020-09-24T06:42:04.607 回答