Array vs Object efficiency in JavaScript

Question

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  lt  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

User · Answer

Indexed fields  fields with numerical keys  are stored as a holy array inside the object  Therefore lookup time is O 1   Same for a lookup array it s O 1   Iterating through an array of objects and testing their ids against the provided one is a O n  operation

User · Answer

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 lt 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 lt 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

User · Answer

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    gt  foo             gt  foo 100     a      a   gt  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

User · Answer

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

User · Answer

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      gt           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  gt  limit            for  let i   0  i  lt   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  gt  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

User · Answer

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

User · Answer

I tried to take this to the next dimension  literally     Given a 2 dimensional array  in which the x and y axes are always the same length  is it faster to   a  look up the cell by creating a two dimensional array and looking up the first index  followed by the second index  i e       var arr          var cell  x  y        or  b  create an object with a string representation of the x and y coordinates  and then do a single lookup on that obj  i e      var obj        var cell   obj  x y         Result  Turns out that it s much faster to do two numeric index lookups on the arrays  than one property lookup on the object   Results here   http   jsperf com arr-vs-obj-lookup-2

User · Answer

The short version  Arrays are mostly faster than objects  But there is no 100  correct solution   Update 2017 - Test and Results  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  lt  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            Original Post - Explanation  There are some misconceptions in your question   There are no associative arrays in Javascript  Only Arrays and Objects   These are arrays   var a1    1  2  3   var a2     a    b    c    var a3       a3 0     a   a3 1     b   a3 2     c     This is an array  too   var a3       a3 29938     a   a3 32994     b     It s basically an array with holes in it  because every array does have continous indexing  It s slower than arrays without holes  But iterating manually through the array is even slower  mostly    This is an object   var a3       a3 29938     a   a3 32994     b     Here is a performance test of three possibilities   Lookup Array vs Holey Array vs Object Performance Test  An excellent read about these topics at Smashing Magazine  Writing fast memory efficient JavaScript

[javascript] Array vs. Object efficiency in JavaScript

Examples related to javascript

Examples related to performance