我有一个可能包含数千个对象的模型。我想知道什么是最有效的方式来存储它们并在获得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];
}
}
选项2与关联数组:
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为键的数组或对象)中,什么表现更好?
而且,如果我必须多次对列表进行排序,答案是否会改变?
简短的版本:数组通常比对象快。但是,没有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";
这是对三种可能性的性能测试:
查找数组与多孔数组与对象性能测试
Smashing Magazine上有关这些主题的精彩读物:编写快速内存高效的JavaScript
根本不是性能问题,因为数组和对象的工作方式非常不同(或至少应该如此)。数组具有连续索引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
使用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
在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和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
这取决于用法。如果是这种情况,查找对象将非常快。
这是一个Plunker示例,用于测试数组和对象查找的性能。
https://plnkr.co/edit/n2expPWVmsdR3zmXvX4C?p=preview
您会看到的;在5.000个长度的数组集合中查找5.000个项目,接管milisecons3000
然而仰望为5.000的对象项目具有5.000的特性,只需要2
或3
milisecons
也使对象树没有太大的区别
我遇到了类似的问题,即我需要存储来自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
如果您有一个排序数组,则可以执行二进制搜索,它比对象查找要快得多,您可以在这里看到我的答案:
如何使用Javascript在排序数组中更快地搜索
-
索引字段(带有数字键的字段)作为神圣数组存储在对象内部。因此查找时间为O(1)
-
与查找数组相同,为O(1)
-
O(n)操作对一组对象进行迭代并针对所提供的对象测试其ID。
文章标签:javascript , performance
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!
评论已关闭!