In a recent project, I came across a function whose efficiency left something to be desired. This function performed two map loops, three filters (each accompanied by a Array.includes) and an additional map with a find built-in, totaling 12 iterations. Although some of these methods, such as filters, did not need to traverse the entire array, the operation was still quite costly, especially for large quantities of items.
The complexity of this function was O(n * m), which could quickly become a problem as the project scaled.
So I decided to optimize this function. The first step I took was to replace the two key arrays with a Set. In JavaScript, a Set is a structure that stores unique data and offers much faster presence checking than an array. While checking an array has O(n) complexity, in Set it is O(1). Furthermore, the performance of the Set.has method does not decrease with the increase in the number of data in Set, unlike Array.includes.
This change has already provided a significant improvement in the filters that operated on the arrays. However, in one of the maps, there was an Array.find that could also be optimized, changing Array.find to Map.get. In JavaScript, a Map is an indexed list, while Array.find performs a linear search, and can be 2,100 to 12,000 times slower than Map, depending on the performance of the processor where the code is being executed.
By replacing Array.find with Map.get in one of the loops, I was able to reduce the total number of iterations from 12 to 9. While a reduction of three loops may not seem significant, the complexity of the algorithm became O(n + m), and the function execution time was reduced by an impressive 96%!
In tests carried out on an Intel Core i7-10510U, executing the function with arrays took 28 times longer than executing it with Map and Set, using arrays of 5,000 items: 191.19 ms to 6.80 ms.
It is worth mentioning that, while the original algorithm with arrays had O(n * m) complexity, the execution time increased exponentially with the number of items. In a software development scenario, it is crucial to consider business growth and the limitations of the machines on which the code will be executed. For example, if the arrays grew to 50,000 items, the execution time of the original algorithm would be 13,585 ms, while the optimized algorithm with Set and Map would only take 135 ms. In this case, the original algorithm would be 100 times slower, showing a 99% reduction in execution time with optimization.
Conclusion
Given the speed superiority of Set and Map compared to Array for information retrieval, the cost of iterating to create a Set or a Map is justified when it is necessary to check this information in iterations like Array.filter or Array.find.
However, the use of Set may not always be viable due to some disadvantages, such as the lack of sequential ordering, the impossibility of direct access to elements by index and the restriction of not storing duplicate elements.
Despite these limitations, in many situations, replacing arrays with Set or Map can bring significant advantages in terms of performance and efficiency.
Top comments (0)