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.
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.
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.
and also, will the answer change if i will have to sort the list many times?
With ES6 the most performant way would be to use a Map.
You can use ES6 features today using a shim (https://github.com/es-shims/es6-shim).
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/2REFERENCE https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map
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.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:
(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.)The literals for both options should make it very clear how they can be used:
Search array: O(n) = n
Search object by key: O(n) = 1
So objects are better.
I had a similar problem that I am facing where I need to store live candlesticks from an event source limited to x items. I could have them stored in an object where the timestamp of each candle would act as the key and the candle itself would act as the value. Another possibility was that I could store it in an array where each item was the candle itself. One problem about live candles is that they keep sending updates on the same timestamp where the latest update holds the most recent data therefore you either update an existing item or add a new one. So here is a nice benchmark that attempts to combine all 3 possibilities. Arrays in the solution below are atleast 4x faster on average. Feel free to play
Conclusion 10 is the limit here
In NodeJS if you know the
ID
, the looping through the array is very slow compared toobject[ID]
.And the results:
Even if the seeking ID is the first one in the array/object:
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.
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
miliseconsHowever Looking up for 5.000 items in object has 5.000 properties, take only
2
or3
miliseconsAlso making object tree don't make huge difference