As a JavaScript developer, improving code performance is a primary objective. Well-performing code not only results in better user experiences but is also vital to program scalability. In this article, we will discuss multiple useful algorithms that can help you optimize the performance of your JavaScript code.
General
Debouncing
Debouncing is a technique used to limit the rate at which a function is executed. It delays the execution of a function until a certain period has passed without any more events. This is useful when dealing with events that are dispatched rapidly, such as keyboard or mouse events. Here's an example of a debounce function:
function debounce(func, wait) {
let timeout;
return function () {
const context = this, args = arguments;
clearTimeout(timeout);
timeout = setTimeout(function () {
func.apply(context, args);
}, wait);
}
}
In this function, we pass in the function that we want to debounce and the wait time in milliseconds. The returned function is a closure that holds a reference to the original function and the wait time. When the returned function is called, it sets a timer using setTimeout. If the function is called again before the timer has expired, the timer is reset. This ensures that the function is only executed once after the specified wait time has elapsed without any more calls. Here's an example of how to use the debounce function:
const searchInput = document.getElementById('search-input');
const searchResult = document.getElementById('search-result');
function search() {
const searchTerm = searchInput.value;
// Perform search operation
searchResult.innerHTML = `Searching for '${searchTerm}'...`;
}
const debouncedSearch = debounce(search, 500);
searchInput.addEventListener('keyup', debouncedSearch);
Throttling
Throttling is a technique used to limit the rate at which a function is executed. It allows the function to execute at fixed intervals. This is useful when dealing with events that are dispatched rapidly, such as scroll or resize events. Here's an example of a throttle function:
function throttle(func, limit) {
let inThrottle;
return function () {
const context = this, args = arguments;
if (!inThrottle) {
func.apply(context, args);
inThrottle = true;
setTimeout(function () {
inThrottle = false;
}, limit);
}
}
}
In this function, we pass in the function that we want to throttle and the time interval in milliseconds. The returned function is a closure that holds a reference to the original function and the time interval. When the returned function is called, it checks if the function has been called recently by checking the inThrottle flag. If the flag is not set, it calls the function and sets the flag to true. It then sets a timer using setTimeout to reset the flag after the specified time interval has elapsed. Here's an example of how to use the throttle function:
function handleScroll() {
// Perform scroll-related operations
console.log('Scrolled!');
}
const throttledScroll = throttle(handleScroll, 500);
window.addEventListener('scroll', throttledScroll);
Memoization
Memoization is a technique that involves caching the results of expensive function calls and returning the cached result when the same inputs are provided. This significantly reduces the number of calculations performed and boosts overall performance.
Here is an example using a recursive Fibonacci function with memoization:
function fibonacciWithMemoization(n, memo = {}) {
if (n in memo) {
return memo[n];
}
if (n === 0 || n === 1) {
return n;
}
memo[n] = fibonacciWithMemoization(n - 1, memo) + fibonacciWithMemoization(n - 2, memo);
return memo[n];
}
// fibonacciWithMemoization(30) => 1143868.97 ops/s
function fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
// fibonacci(30) => 73.5 ops/s
Here is an example of memoization useful for caching previous results
function memoize(func) {
const cache = new Map();
return function (...args) {
const key = JSON.stringify(args);
if (!cache.has(key)) {
cache.set(key, func.apply(this, args));
}
return cache.get(key);
};
}
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
// Calling memoizedFibonacci repetetivly
memoizedFibonacci(10)
memoizedFibonacci(10)
memoizedFibonacci(10)
// 776019 ops/s
// Calling fibonacci repetetivly
fibonacci(10)
fibonacci(10)
fibonacci(10)
// 496203 ops/s
// fibonacci is 40% slower
Lazy Evaluation
Lazy evaluation is a strategy that allows you to defer the computation of the value of an expression until it is needed. This can improve performance by avoiding unnecessary computations. Here’s an example of lazy evaluation using generator functions:
function* fibonacciGenerator() {
let a = 0, b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
const fibGen = fibonacciGenerator();
console.log(fibGen.next().value); // 0
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 2
Search
Binary Search
A Binary Search is an efficient search algorithm that can be used to replace the linear search when searching through sorted arrays. It repeatedly divides the array in half until the target element is found or the remaining search space is empty. Here’s an example of a binary search function in JavaScript:
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29];
const target1 = 13;
const target2 = 20;
const index1 = binarySearch(sortedArray, target1);
const index2 = binarySearch(sortedArray, target2);
console.log(`Index of ${target1} in the sorted array: ${index1}`); // Output: Index of 13 in the sorted array: 6
console.log(`Index of ${target2} in the sorted array: ${index2}`); // Output: Index of 20 in the sorted array: -1
Quickselect
Quickselect is an efficient algorithm for finding the k-th smallest element in an unordered list. It is related to the quick sort algorithm and provides an efficient in-place sorting solution. Here's an example of a quickselect algorithm:
function quickselect(arr, k) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const pivot = partition(arr, left, right);
if (pivot === k) {
return arr[pivot];
} else if (pivot < k) {
left = pivot + 1;
} else {
right = pivot - 1;
}
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
const unorderedArray = [10, 3, 8, 1, 5, 9, 2, 7, 6, 4];
const k1 = 4;
const k2 = 7;
const kthSmallest1 = quickselect(unorderedArray.slice(), k1 - 1);
const kthSmallest2 = quickselect(unorderedArray.slice(), k2 - 1);
console.log(`The ${k1}-th smallest element in the unordered array is: ${kthSmallest1}`); // Output: The 4-th smallest element in the unordered array is: 4
console.log(`The ${k2}-th smallest element in the unordered array is: ${kthSmallest2}`); // Output: The 7-th smallest element in the unordered array is: 7
Sorting
Quick Sort
Quick Sort is one of the most efficient sorting algorithms, especially for large datasets. This algorithm uses a divide-and-conquer approach that sorts an array by breaking the array into smaller chunks and recursively sorting them. Here is a simple implementation of Quick Sort:
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const less = arr.filter(x => x < pivot);
const equal = arr.filter(x => x === pivot);
const greater = arr.filter(x => x > pivot);
return [...quickSort(less), ...equal, ...quickSort(greater)];
}
Merge Sort
Merge Sort is another efficient sorting algorithm that can help you optimize your code. It works by dividing an array in half, recursively sorting each half, and then merging the sorted halves back together. Here's a simple implementation of Merge Sort:
function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] < right[0]) result.push(left.shift());
else result.push(right.shift());
}
return result.concat(left, right);
}
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
Here's an example of how to use Quick Sort and Merge Sort to sort an unsorted array of numbers:
// Unsorted array of numbers
const unsortedArray = [34, 7, 23, 32, 5, 62, 19, 45, 28];
// Test case: sorting the unsorted array using Quick Sort
const sortedArrayUsingQuick = quickSort(unsortedArray);
// Test case: sorting the unsorted array using Merge Sort
const sortedArrayUsingMerge = mergeSort(unsortedArray);
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array using quick sort:", sortedArray);
console.log("Sorted array using merge sort:", sortedArray);
// Output: Unsorted array: [34, 7, 23, 32, 5, 62, 19, 45, 28]
// Sorted array using quicl sort: [5, 7, 19, 23, 28, 32, 34, 45, 62]
// Sorted array using merge sort: [5, 7, 19, 23, 28, 32, 34, 45, 62]
Trees & Graphs
Depth-First Search (DFS) and Breadth-First Search (BFS)
When traversing a tree or graph data structure, DFS and BFS are two common algorithms that can be used. Both algorithms can help locate certain nodes or perform optimizations relating to data structure traversal.
DFS starts at the root node and explores each branch as deeply as possible before backtracking. It can be implemented using recursion or an iterative approach. Here's an example of a recursive DFS algorithm:
function depthFirstSearchRecursive(node, targetValue) {
if (!node) return null;
if (node.value === targetValue) {
return node;
}
const leftSearchResult = depthFirstSearchRecursive(node.left, targetValue);
const rightSearchResult = depthFirstSearchRecursive(node.right, targetValue);
return leftSearchResult || rightSearchResult;
}
BFS explores all the neighbors of a node before moving on to the next-level neighbors. It uses a queue to keep track of nodes to visit. Here's an example of a BFS algorithm:
function breadthFirstSearch(root, targetValue) {
const queue = [root];
while (queue.length > 0) {
const currentNode = queue.shift();
if (currentNode.value === targetValue) {
return currentNode;
}
if (currentNode.left) queue.push(currentNode.left);
if (currentNode.right) queue.push(currentNode.right);
}
return null;
}
Here's an example of how to use this Depth-First Search (DFS) and Breadth-First Search (BFS) implementations with a simple binary tree and test cases to find nodes with specific target values:
// Simple binary tree
const tree = {
value: 1,
left: {
value: 2,
left: { value: 4 },
right: { value: 5 }
},
right: {
value: 3,
left: { value: 6 },
right: { value: 7 }
}
};
// Test cases: finding nodes with target values 4 and 7
const dfsTargetValue = 4;
const bfsTargetValue = 7;
const dfsResult = depthFirstSearchRecursive(tree, dfsTargetValue);
console.log(`DFS found node with value ${dfsTargetValue}:`, dfsResult);
const bfsResult = breadthFirstSearch(tree, bfsTargetValue);
console.log(`BFS found node with value ${bfsTargetValue}:`, bfsResult);
In this example, we have a simple binary tree with nodes containing values from 1 to 7. We use test cases to search for nodes with target values of 4 and 7 using both DFS and BFS algorithms. The depthFirstSearchRecursive function is called with the tree and target value 4, returning the node with that value. Similarly, the breadthFirstSearch function is called with the tree and target value 7, returning the corresponding node. This example demonstrates how DFS and BFS can be used to locate specific nodes in tree or graph data structures.
Dijkstra's Algorithm
Dijkstra's Algorithm is an efficient method for finding the shortest path between a starting node and all other nodes in a weighted graph with non-negative edge weights. It works by iteratively selecting the unvisited node with the smallest known distance, updating its neighbors' distances, and marking the node as visited. Here's a simple JavaScript implementation:
function dijkstra(graph, startNode) {
const distances = {};
const visited = new Set();
// Initialize distances
for (const node in graph) {
distances[node] = node === startNode ? 0 : Infinity;
}
let currentNode = startNode;
while (currentNode) {
visited.add(currentNode);
// Update neighbors' distances
for (const neighbor in graph[currentNode]) {
const newDistance = distances[currentNode] + graph[currentNode][neighbor];
if (newDistance < distances[neighbor]) {
distances[neighbor] = newDistance;
}
}
// Select the next unvisited node with the smallest distance
currentNode = Object.keys(distances).reduce((minNode, node) => {
return !visited.has(node) && distances[node] < distances[minNode] ? node : minNode;
}, null);
}
return distances;
}
This implementation can be used to find the shortest paths in various applications, such as GPS navigation systems or computer network routing.
Here's an example of how to use Dijkstra's Algorithm with a simple graph and a test case to find the shortest path distances from node 'A' to all other nodes:
// Sample graph represented as an adjacency list
const graph = {
A: { B: 1, C: 4 },
B: { A: 1, C: 2, D: 5 },
C: { A: 4, B: 2, D: 1 },
D: { B: 5, C: 1, E: 3 },
E: { D: 3 }
};
// Test case: finding the shortest path distances from node A to all other nodes
const shortestPathDistances = dijkstra(graph, 'A');
console.log("Shortest path distances from A: ", shortestPathDistances);
// Output: { A: 0, B: 1, C: 3, D: 4, E: 7 }
In this example, the graph is represented as an adjacency list, with each key representing a node and its corresponding value containing the neighboring nodes and their distances. The test case calls the dijkstra function with the graph and start node 'A'. The resulting object contains the shortest path distances from node 'A' to all other nodes in the graph. This example demonstrates how Dijkstra's Algorithm implementation can be used effectively in various.
A* Search Algorithm
A* Search Algorithm is an efficient pathfinding algorithm that combines the strengths of Dijkstra's Algorithm and greedy best-first search by considering both the distance from the starting node and an estimated distance to the goal node. A* directs the search towards the most promising paths, making it optimal for many problems. Here's a simple JavaScript implementation:
function aStarSearch(graph, startNode, goalNode, heuristic) {
const distances = {};
const fScores = {};
const visited = new Set();
const pq = new PriorityQueue();
// Initialize distances and fScores
for (const node in graph) {
distances[node] = node === startNode ? 0 : Infinity;
fScores[node] = node === startNode ? heuristic(startNode, goalNode) : Infinity;
pq.enqueue(node, fScores[node]);
}
while (!pq.isEmpty()) {
const currentNode = pq.dequeue();
// Goal reached
if (currentNode === goalNode) {
return distances[goalNode];
}
visited.add(currentNode);
// Update neighbors' distances and fScores
for (const neighbor in graph[currentNode]) {
if (visited.has(neighbor)) continue;
const newDistance = distances[currentNode] + graph[currentNode][neighbor];
if (newDistance < distances[neighbor]) {
distances[neighbor] = newDistance;
fScores[neighbor] = newDistance + heuristic(neighbor, goalNode);
pq.update(neighbor, fScores[neighbor]);
}
}
}
// Path not found
return null;
}
This example demonstrates how A* can be used to find the shortest path in various applications, such as game pathfinding or GPS navigation systems. The heuristic function estimates the remaining distance to the goal node and should be provided by the user.
Here's an example of how to use A* Search Algorithm with a simple graph, a Manhattan distance heuristic function, and a test case to find the shortest path from node 'A' to node 'E':
// Sample graph represented as an adjacency list
const graph = {
A: { B: 1, C: 4 },
B: { A: 1, C: 2, D: 5 },
C: { A: 4, B: 2, D: 1 },
D: { B: 5, C: 1, E: 3 },
E: { D: 3 }
};
// Manhattan distance heuristic function
function manhattanDistance(node1, node2) {
const coords = {
A: [0, 0],
B: [1, 0],
C: [1, 1],
D: [2, 1],
E: [3, 1]
};
const [x1, y1] = coords[node1];
const [x2, y2] = coords[node2];
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
// Test case: finding the shortest path from node A to node E
const shortestPathDistance = aStarSearch(graph, 'A', 'E', manhattanDistance);
console.log("Shortest path distance from A to E: ", shortestPathDistance); // Output: 6
This example demonstrates using the A* Search Algorithm to find the shortest path from node 'A' to node 'E' in a simple graph. The graph is represented as an adjacency list, with each key representing a node and its corresponding value containing the neighboring nodes and their distances. The Manhattan distance heuristic function calculates the remaining distance to the goal node by summing the absolute differences between the node coordinates. The test case calls the aStarSearch function with the graph, start node 'A', goal node 'E', and the Manhattan distance heuristic function. The resulting shortest path distance is 6, which is the output of the example. This showcases how the A* Search Algorithm can be used effectively in various applications like game pathfinding, GPS navigation systems, or routing in computer networks.