CODEWITHSUNDEEP
javascriptarraysnode.jsoptimizationset
Pierre-Louis Lacorte
Pierre-Louis Lacorte

Reputation: 363

Is it worth it to convert array into set to search in NodeJS

I would like to know if it is worth to convert an array into a set in order to search using NodeJS.

My use case is that this search is done lot of times, but not necessary on big sets of data (can go up to ~2000 items in the array from time to time).

Looking for a specific id in a list.

Which approach is better :

const isPresent = (myArray, id) => {
   return Boolean(myArray.some((arrayElement) => arrayElement.id === id);
}

or 

const mySet = new Set(myArray)
const isPresent = (mySet, id) => {
   return mySet.has(id);
}

I know that theoretically the second approach is better as it is O(1) and O(n) for the first approach. But can the instantiation of the set offset the gain on small arrays?

Upvotes: 2

Views: 1120

Answers (2)

A. Todkar
A. Todkar

Reputation: 383

@jonrsharpe - particularly for your case, I found that converting an array of 2k to Set itself is taking ~1.15ms. No doubt searching Set is faster than an Array but in your case, this additional conversion can be little costly.

You can run below code in your browser console to check. new Set(arr) is taking almost ~1.2ms

var  arr = [], set = new Set(), n = 2000;
for (let i = 0; i < n; i++) {
  arr.push(i);
};

console.time('Set'); 
set = new Set(arr);
console.timeEnd('Set');

Adding element in the Set is always costly. Below code shows the time required to insert an item in array/set. Which shows Array insertion is faster than Set.

var  arr = [], set = new Set(), n = 2000;
console.time('Array'); 
for (let i = 0; i < n; i++) {
  arr.push(i);  
};
console.timeEnd('Array');

console.time('Set'); 
for (let i = 0; i < n; i++) {
  set.add(i);  
};
console.timeEnd('Set');

I run the following code to analyze the speed of locating an element in the array and set. Found that set is 8-10 time faster than the array.

You can copy-paste this code in your browser to analyze further

var arr = [], set = new Set(), n = 100000;
for (let i = 0; i < n; i++) {
  arr.push(i);
  set.add(i);
}

var result;
console.time('Array'); 
result = arr.indexOf(12313) !== -1; 
console.timeEnd('Array');
console.time('Set'); 
result = set.has(12313); 
console.timeEnd('Set');

So for your case array.some is better!

Upvotes: 2

gcasar
gcasar

Reputation: 759

I will offer a different upside for using Set: your code is now more semantic, easier to know what it does.

Other than that this post has a nice comparison - Javascript Set vs. Array performance but make your own measurements if you really feel that this is your bottleneck. Don't optimise things that are not your bottleneck!

My own heuristic is a isPresent-like utility for nicer code but if the check is done in a loop I always construct a Set before.

Upvotes: 0

Related Questions