Array vs. Object efficiency in JavaScript

2019-01-02 14:30发布

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?

8条回答
宁负流年不负卿
2楼-- · 2019-01-02 15:07

With ES6 the most performant way would be to use a Map.

var myMap = new Map();

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

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

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/2


REFERENCE https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

查看更多
公子世无双
3楼-- · 2019-01-02 15:08

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:

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

(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:

var arr = ['foo', 'bar', 'baz'];     // no keys, not even the option for it
var obj = { foo : 'bar', baz : 42 }; // associative by its very nature
查看更多
皆成旧梦
4楼-- · 2019-01-02 15:12

Search array: O(n) = n

Search object by key: O(n) = 1

So objects are better.

无色无味的生活
5楼-- · 2019-01-02 15:14

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

"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)
}

Conclusion 10 is the limit here

Storing as objects 4183 nanoseconds 10
Storing as array 373 nanoseconds 10
查看更多
刘海飞了
6楼-- · 2019-01-02 15:15

In NodeJS if you know the ID, the looping through the array is very slow compared to 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');

And the results:

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

Even if the seeking ID is the first one in the array/object:

Array result:
arrTimer: 2.975ms
Object result:
objTimer: 0.068ms
查看更多
若你有天会懂
7楼-- · 2019-01-02 15:26

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 milisecons

However Looking up for 5.000 items in object has 5.000 properties, take only 2 or 3 milisecons

Also making object tree don't make huge difference

查看更多
登录 后发表回答