JavaScript 中的数组与对象效率

我有一个模型，里面可能有成千上万的物品。我想知道如何最有效地存储它们，并在获得一个对象的 id 后检索该对象。身份证上的号码很长。

这就是我考虑的两个选择。在选项1中，它是一个具有递增索引的简单数组。在第二个选项中，如果它有所不同，它可能是一个关联数组，也可能是一个对象。我的问题是，当我主要需要检索单个对象，但有时也需要遍历它们并进行排序时，哪一个更有效。

第一种选择是不带关联数组的:

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 为键的对象。

还有，如果我要对列表进行多次排序，答案是否会改变？

163357 次浏览
小开

这根本不是性能问题，因为数组和对象的工作方式非常不同(或者至少应该如此)。数组具有连续索引 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
小开
最佳答案

简而言之: 数组通常比对象快，但是没有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'});
}

test setup test results

原文后解释

你的问题中有一些误解。

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";

下面是对三种可能性的性能测试:

查找阵列与多孔阵列与对象性能测试

一个关于这些主题的优秀阅读在 Smashing 杂志: 编写快速高效的内存 JavaScript

小开

我试着把这个带到另一个维度，真的。

给定一个二维数组，其中 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

小开

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

var myMap = new Map();


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


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

您可以使用 ES6的功能今天使用垫片(https://github.com/es-shims/es6-shim)。

性能因浏览器和场景而异，但这里有一个 Map性能最好的例子: https://jsperf.com/es6-map-vs-object-properties/2

参考文献 Https://developer.mozilla.org/en/docs/web/javascript/reference/global_objects/map

小开

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

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

Https://plnkr.co/edit/n2exppwvmsdr3zmxvx4c?p=preview

你会明白的 在 5000长度数组集合中查找 5000项，接管 3000毫秒

然而，在对象中查找 5000项目有 5000属性，只采取 2或 3毫秒

同样，创建对象树也没有太大的不同

小开

在 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
小开

我有一个类似的问题，我需要面对的地方，我需要存储从事件源限制为 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
小开

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

  2. 对于查找数组也是 O (1)

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


提交答案