CODEWITHSUNDEEP
javascriptarrays
JustStarted
JustStarted

Reputation: 130

What is a faster way to get an object from array using find index, or getting value at a key of a map in JavaScript?

Method 1 is using an array which contains objects and i want to get an object with a certain ID. The second method is suing map, in which an object is created at "id" key.

To get object from array 

array.findIndex((x) => x.id == id)

and to get object from map is simple

Map.get(id)

I want to know which method is faster and better

Upvotes: 2

Views: 3438

Answers (2)

niry
niry

Reputation: 3308

It Depends

In theory you should use Big O notation to decide. As noted, .findIndex is O(n) while map.get is O(1), which simply means map.get is more efficient. However, in practice, there are many other considerations. For example:

What is the the size of the data? Does it comes already as an array and you need to Map it? How many lookups you need to perform?

On a very small array, simple lookup (for loop, not .findIndex, because of the additional function call) might be more efficient. On very large array, mapping takes time, few lookups will be more efficient than mapping.

Consider the following code, for large size array, two lookups, mapping will be highly inefficient. Only above ~15-20 lookups (depend on your CPU, memory speed, ETC), mapping will be more efficient.

'use strict';

const gen_arr = size => {
  const arr = [];
  while (size) {
    arr.push({ id:size, data:size.toString() });
    --size;
  }
  return arr;
};

const map_it = arr => {
  const map = new Map();
  for (let obj of arr) {
    map.set(obj.id, obj);
  }
  return map;
}

// Assume nodejs if no performance
const perf = typeof performance != 'undefined' ? performance : { now: ()=> Number(process.hrtime.bigint() / 1000000n) };
let t = perf.now();
const timeit = msg => { const t1 = perf.now(); console.log(msg, 'took', t1 - t, 'ms'); t = t1; };
const start_timer = () => t = perf.now();

const arr_size = 1000000;
const arr = gen_arr(arr_size);

start_timer();
let r = arr.find(obj => obj.id === 1); // end
timeit(`finding ${JSON.stringify(r)} in array`);
r = arr.find(obj => obj.id === arr_size);
timeit(`finding ${JSON.stringify(r)} in array`);
let map = map_it(arr);
timeit('mapping');
r = map.get(1);
timeit(`finding ${JSON.stringify(r)} in map`);
r = map.get(arr_size);
timeit(`finding ${JSON.stringify(r)} in map`);

Upvotes: 2

StepUp
StepUp

Reputation: 38144

Big O notation is how long an algorithm takes to execute depending on how long is the input and usually talking about the unfavorable case scenario.

When you use array.findIndex((x) => x.id == id), it means that the whole array should be iterated in the worst case array.length times. So the complexity of this method is O(n).

When you use Map.get(id), it means that hash will be calculated and then by this hash we can go to the desired item in Map. So the complexity of this method is O(1). It is faster.

UPDATE:

Comment by VLAZ:

On the flip side, of course, a map takes extra space and processing. So, if you only want to look up one or two items, it's probably not worth it. However, if you have lots of lookups, it will have a massive benefit speed-wise. Just throwing it out there. I'd personally opt for a Map.

Upvotes: 4

Related Questions