Accelerate JavaScript using Set data type

The author of the material, the translation of which we are publishing today, says that he is sure that many JavaScript developers use mostly data types such as Number , String , Object , Array and Boolean . In most cases, this is enough. But if you need to make the code as fast and scalable as possible, the use of these data types is not always justified.



In this article we will talk about how, using the Set data type, which allows you to work with collections of unique values, make the code faster. This is especially true for large-scale project code. The Array and Set types have a lot in common, but the use of the Set data type is able to give the programmer such opportunities, which are clearly manifested during the execution of programs that the Array type does not.

What is the difference between the Array and Set data types?

The main feature of the Array data type (we will call objects of this type “arrays”) is that arrays are indexed collections of values. This means that the data in the arrays is stored using indexes.
')

 const arr = [A, B, C, D]; console.log(arr.indexOf(A)); // : 0 console.log(arr.indexOf(C)); // : 2 

Unlike arrays, objects of type Set (we will call them "collections") are collections containing data in key / value format. Instead of using indexes, collections store items using keys. Elements stored in the collection can be iterated in the order they are added to the collection, and the collection cannot store the same elements. In other words, all elements of the collection must be unique.

What are the main strengths of the collections?

If we compare collections and arrays, then collections can reveal some advantages over arrays, especially noticeable in situations in which program performance is important:

• Search for items. The array methods indexOf() and includes() , used to search for elements and check whether there is a certain element in the array, are slow.
• Removing items. In the collection item can be deleted, based on its value. In an array, the equivalent of such an action would be using the splice() method, based on the index of the element. As with the search for items, deleting items using indexes is a slow operation.
• Insert item. It is much faster to add an item to a collection than using methods like push() and unshift() to an array.
• Work with NaN value. The indexOf() method cannot be used to search for NaN values ​​in an array, while using the has() collection method to find out if there is a NaN in it.
• Remove duplicate items. Objects of type Set store only unique values. If you need to avoid storing duplicate elements in a certain data structure, this is their significant advantage over arrays. When working with arrays to remove duplicate elements would have to write additional code.

A complete list of the built-in methods of Set type objects can be found here

On the time complexity of algorithms

The methods that arrays use to search for elements have linear time complexity - O (N). In other words, the search time for an element is proportional to the size of the array.

Unlike arrays, the methods used by collections to find, delete, and add items have a time complexity of O (1). This means that the size of the collection has virtually no effect on the working hours of such methods.

Here you can read details about the time complexity of the algorithms.

How much faster are arrays?

Although a variety of factors strongly influence the performance of JavaScript code, in particular, they depend on the system on which the code is run, on the code execution environment used, on the size of the data being processed, I hope my test results will give you the opportunity to compare arrays and collections from a practical point of view, and understand how collection is faster than arrays. Now we will look at three simple tests and analyze their results.

▍ Preparation for tests

Before performing any tests, let's create an array with a million elements and the same collection. For the sake of simplicity, we will use a cycle, the first value of the counter of which will be 0, and the last - 999999:

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

▍Test №1: checking the presence of an element in the array and in the collection

First, 123123 check the presence of the element 123123 in the array and in the collection, knowing in advance that there is such an element in these data structures.

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

Here are the results of this test:

 Array: 0.173ms Set: 0.023ms 

The collection is 7.54 times faster than an array.

▍Test number 2: insert item

Now let's try adding items to arrays and collections.

 console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set'); 

Here's what happened:

 Array: 0.018ms Set: 0.003ms 

The collection is 6.73 times faster than an array.

▍Test number 3: delete item

Now let's remove the element from each data structure (for example, the one that was added in the previous test). Arrays do not have a built-in method for deleting elements, so we will create an auxiliary function in order to keep our code in fair condition:

 const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); }; 

And here is the test code:

 console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set'); 

The result is the following:

 Array: 1.122ms Set: 0.015ms 

In this case, the collection was 74.13 times faster than the array!

In general, it can be noted that code performance can be significantly increased by using collections instead of arrays. Consider a few practical examples.

Example # 1: removing duplicate values ​​from an array

If you need to quickly remove duplicate values ​​from an array, you can convert it to a collection. This is perhaps the easiest way to get rid of duplicate values:

 const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C']; //       let uniqueCollection = new Set(duplicateCollection); console.log(uniqueCollection) // : Set(4) {"A", "B", "C", "D"} //        let uniqueCollection = [...new Set(duplicateCollection)]; console.log(uniqueCollection) // : ["A", "B", "C", "D"] 

Example # 2: a challenge with an interview at Google

In one of my material, I considered four options for answering the question asked by the interviewer from Google. Interviews were conducted using C ++, but if JavaScript were used instead of this language, the Set data structure would necessarily be used to solve the problem.

If you want to more deeply understand the answer to this question - read the above article. Here I just show you the solution.

▍Task

Given an unsorted array of integers and the value of sum . Write a function that returns true if, as a result of the addition of any two elements of this array, we get the value of sum . If there are no such elements in the array, the function should return false .

It turns out, for example, that if we are given an array [3, 5, 1, 4] and the value of sum is equal to 9 , then the function should return true , since 4+5=9 .

▍Decision

The solution to this problem can be approached using the following idea: you need to iterate over the array, creating as it iterates, the Set data structure, to which values ​​will be added that complement the found values ​​to the sum value.

Let us analyze this idea by the example of the above array. When we meet 3 , we can add the number 6 to the collection, since we know that we need to find two numbers that are 9 in total. Then, every time we encounter a new value from the array, we can check the collection and see if it is there. When we meet the number 5 , we will add 4 to the collection. And when, finally, we get to the number 4 , we find it in the collection and we can return true .

Here's what the solution to this problem might look like:

 const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) {   let searchVal = val - arr[i];   if (searchValues.has(arr[i])) {     return true;   } else {     searchValues.add(searchVal);   } }; return false; }; 

And here is a more concise solution:

 const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set)); 

Since the time complexity of the Set.prototype.has() method is O (1), using the Set data structure to store numbers that complement the numbers found in the array to a given value allows you to find a solution in linear time (O (N)).

If the solution would depend on the Array.prototype.indexOf() method or on the Array.prototype.includes() method, the time complexity of each of which is O (N), then the total time complexity of the algorithm would be O (N ² ). As a result, it would become much slower.

Results

If you have not previously encountered the Set data type in JavaScript, then we hope that you, having got an idea about it, will be able to use it in your projects with use.

Dear readers! How would you apply a Set data structure in your code?