Translator: Front-end wisdom

Original text: medium.com/@bretcamero…

Click “like” and then look, wechat search [Big Move the world] pay attention to this person without dACHang background, but with a positive attitude upward. In this paper, making github.com/qq449245884… Has been included, the article has been categorized, also organized a lot of my documentation, and tutorial materials.

Everyone said there was no project on your resume, so I found one and gave it away【 Construction tutorial 】.

I’m sure there are plenty of developers out there who insist on using basic global objects: numbers, strings, objects, arrays, and Bools. These are required for many use cases. But if you want your code to be as fast and extensible as possible, these basic types aren’t always good enough.

In this article, we’ll discuss how Set objects in JS can make code faster — and especially extensible. There is a lot of crossover between how Array and Set work. But using Set has an advantage over Array in terms of code speed.

Set is different

The fundamental difference is that an array is a collection of indexes, 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
Copy the code

By contrast, a set is a set of keys. Instead of using indexes, sets sort data using keys. The elements in a set are iterable in insertion order; it cannot contain any duplicate data. In other words, each entry in a set must be unique.

What are the main benefits

Sets have several advantages over arrays, especially in terms of runtime:

  • Viewing elements: Checking the presence of items in an array using indexOf() or includes() is slow.

  • Delete elements: In a Set, items can be deleted based on their value. In arrays, the equivalent is to use splice() based on an element index. As with the previous point, reliance on indexes is slow.

  • Save NaN: You cannot use indexOf() or includes() to find the value NaN, whereas Set can save this value.

  • Delete duplicates :Set objects store only unique values, which is a significant advantage over arrays if you don’t want duplicates, because arrays require extra code to handle duplicates.

Time complexity?

The methods used by arrays to search for elements have a time complexity of 0(N). In other words, the running time grows at the same rate as the data size.

By contrast, the methods Set uses to search, delete, and insert elements all have a time complexity of O(1), which means that the size of the data is actually independent of how long those methods run.

How fast is Set?

While the running time can vary widely, depending on the system used, the size of the data provided, and other variables, I hope my test results will give you a true idea of the speed of Set. I’m going to share three simple tests and the results I got.

Ready to test

Before running any tests, create an array and a Set, each with 1 million elements. For simplicity, I’m going to start at zero and count all the way up to 999999.

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

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');Copy the code
  • Array: 0.173 ms
  • Set: 0.023 ms

Set is 7.54 times faster

Test 2: Add elements

console.time('Array'); 
arr.push(n);
console.timeEnd('Array');
console.time('Set'); 
set.add(n);
console.timeEnd('Set');
Copy the code
  • Array: 0.018 ms
  • Set: 0.003 ms

Set is 6.73 times faster

Test 3: Delete elements

Finally, to delete an element, we first create an auxiliary function, since there are no built-in methods:

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

Here is the code for the test:

console.time('Array'); 
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set'); 
set.delete(n);
console.timeEnd('Set');
Copy the code
  • Array: 1.122 ms
  • Set: 0.015 ms

Set is 74.13 times faster

Overall, we can see that using Set greatly improves the runtime. Let’s look at some practical examples where sets are useful.

Case 1: Deleting duplicate values from an array

If you want to quickly remove duplicate values from an array, you can convert them to 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"} // Set(5) {"A", "B", "C", "D"} // Let uniqueCollection = [...new Set(duplicateCollection)]; console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]Copy the code

Case study 2: Google interview questions

Question:

Given an unordered array of integers and the variable sum, return true if the sum of any two entries in the array equals sum. 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 over a group of numbers and create a Set to hold the relative differences.

When we encounter 3, we can add 6 to Set, because we know we need to find the sum of 9. Then, whenever we touch a new value in the array, we can check if it is in the Set. When you hit a 5, you add 4 to Set. Finally, when we finally encounter 4, which can be found in Set, we return 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; };Copy the code

Concise version:

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

Because set.prototype.has () has a time complexity of O(1), we use sets instead of arrays, resulting in a linear runtime of O(N) for the entire solution.

If you use array.prototype.indexof () or array.prototype.includes (), both of which have O(N) time complexity, the total run time will be O(N²), much slower!

The bugs that may exist after code deployment cannot be known in real time. In order to solve these bugs, I spent a lot of time on log debugging. Incidentally, I recommend a good BUG monitoring tool for youFundebug.

communication

This article is updated every week, you can search wechat “big move the world” for the first time to read and urge more (one or two earlier than the blog hey), this article GitHub github.com/qq449245884… It has been included and sorted out a lot of my documents. Welcome Star and perfect. You can refer to the examination points for review in the interview.