Detailed explanation of how to use Set to improve the performance of JS code

I'm sure there are a lot of developers stuck with the basic global objects: numbers, strings, objects, arrays and booleans. For many use cases, these are needed. But if you want your code to be as fast and scalable as possible, these basic types aren't always good enough.

In this article, we will discuss how the Set object in JS can make your code faster — especially scalable. There is a lot of overlap in how Array and Set work. But using Set will have an advantage over Array in terms of code running speed.

What is the difference between Set

The most fundamental difference is that the array is an indexed collection, which means that the data values ​​in the array are sorted by index.

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

In contrast, set is a collection of keys. setDoes not use indexes, but uses keys to sort data. The elements in set are iterable in insertion order, and it cannot contain any duplicate data. In other words, each item in set must be unique.

What are the main benefits

set has several advantages over arrays, especially in terms of runtime:

• View elements: Using indexOf() or includes() to check whether an item in an array exists is slower.
• Delete element: In Set, you can delete the item based on its value. In arrays, the equivalent method is splice() using element-based indexing. Like the previous point, relying on indexes is slow.
• Saving NaN: Cannot use indexOf() or includes() to find the value NaN while Set can save this value.
• Delete duplicates:SetObjects only store unique values. If you don’t want duplicates to exist, this is a significant advantage over arrays, because arrays require additional Code to handle duplication.

time complexity?

The time complexity of the method used to search for elements in an array is 0(N). In other words, the runtime grows at the same rate as the data size.

In contrast, the time complexity of Set methods for searching, deleting and inserting elements is only O(1), which means that the data Size actually has nothing to do with the running time of these methods.

How fast is Set?

While run times can vary greatly depending on the system used, the size of the data provided, and other variables, I hope my test results will give you a realistic idea of ​​Set speed. I'll share three simple tests and the results I got.

Preparing for testing

Before running any tests, create an array and a Set, each with 1 million elements. . To keep it simple, I started with 0 and counted until 999999.

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

Test 1: Find Elements

We search for the number 123123

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

• Array: 0.173ms
• Set: 0.023ms

Set is faster7.54 times

Test 2: Add element

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

• Array: 0.018ms
• Set: 0.003ms

Set The speed is 6.73 times faster

Test 3: Delete elements

Finally, delete an element. Since the array has no built-in method, first create an auxiliary function:

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

This is the code for the test:

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

• Array: 1.122ms
• Set: 0.015ms

Set It’s faster 74.13 times

Overall That said, we can see that using Set greatly improves the runtime. Let's take a look at some practical examples of Set being useful.

Case 1: Delete duplicate values ​​from the array

If you want to quickly delete duplicate values ​​from the array, you can convert it into a Set . This is by far the cleanest way to filter unique values:

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 将数组转换为 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]

Case 2: Google Interview Questions

Question:

Given an unordered array of integers and a variable sum, if there is a value whose sum of any two items in the array is equal to sum, then true will be returned. Otherwise, return false. For example, the array [3,5,1,4] and sum = 9, the function should return true because 4 5 = 9.

Answer

A good way to solve this problem is to iterate through the array and create a Set to save the relative difference.

当我们遇到3时，我们可以把6加到Set中, 因为我们知道我们需要找到9的和。然后，每当我们接触到数组中的新值时，我们可以检查它是否在 Set 中。当遇到5时，在 Set 加上4。最后，当我们最终遇到4时，可以在Set中找到它，就返回true。

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;
};

简洁的版本：

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

因为Set.prototype.has()的时间复杂度仅为O(1)，所以使用 Set 来代替数组，最终使整个解决方案的线性运行时为O(N)。

如果使用 Array.prototype.indexOf()或Array.prototype.includes()，它们的时间复杂度都为 O(N)，则总运行时间将为O(N²)，慢得多！

原文地址：https://medium.com/@bretcameron/how-to-make-your-code-faster-using-javascript-sets-b432457a4a77

更多编程相关知识，请访问：编程入门！！

The above is the detailed content of Detailed explanation of how to use Set to improve the performance of JS code. For more information, please follow other related articles on the PHP Chinese website!