Efficient Data Structures & Algorithms
Choosing the right data structure dramatically impacts performance. Set.has() is O(1) vs Array.includes() which is O(n). Learn which structures to use for common operations.
Efficient Data Structures
- Set.has() — O(1) lookup vs Array.includes() O(n). 100x faster for large collections
- Map.get() — O(1) vs scanning object keys. Better for frequent lookups
- Object vs Map — Map is faster for frequent add/delete. Object is fine for static configs
- Sorting — Native sort is optimized (TimSort). Custom comparators are fine
- Search — For sorted data, binary search O(log n) vs linear search O(n)
- Caching — Memoize expensive functions: store results of previous compute
Data Structures Code
// Set vs Array for lookups
const size = 100000;
const array = Array.from({ length: size }, (_, i) => `item_${i}`);
const set = new Set(array);
// Array.includes — O(n) linear search
console.time("Array.includes");
for (let i = 0; i < 1000; i++) {
array.includes(`item_${size - 1}`);
}
console.timeEnd("Array.includes");
// Set.has — O(1) hash lookup
console.time("Set.has");
for (let i = 0; i < 1000; i++) {
set.has(`item_${size - 1}`);
}
console.timeEnd("Set.has");
// Set.has is ~100x faster!
// Memoization — cache expensive results
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
// Expensive fibonacci without memoization
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// Memoized version — exponentially faster!
const memoFib = memoize(function fib(n) {
if (n <= 1) return n;
return memoFib(n - 1) + memoFib(n - 2);
});
console.time("Regular fib(35)");
console.log("fib(35):", fib(35));
console.timeEnd("Regular fib(35)");
console.time("Memoized fib(35)");
console.log("memoFib(35):", memoFib(35));
console.timeEnd("Memoized fib(35)");Tip
Tip
Profile before you optimize. Don't memoize everything — measure first to find actual bottlenecks. The fastest code is code that doesn't run. Eliminate unnecessary work before optimizing what remains.
Map/Set for general use. Weak variants for memory-sensitive caching.
Common Mistake
Warning
Memoizing functions with frequently changing inputs. If the arguments are always different, the cache never hits and you're just wasting memory storing unused results. Memoize only when repeated calls with the same arguments are common.
Practice Task
Note
Caching: (1) Memoize an expensive Fibonacci function and measure the speedup. (2) Implement an LRU cache with a max size. (3) Add expiration times to cached values.
Quick Quiz
Key Takeaways
- Choosing the right data structure dramatically impacts performance.
- Set.has() — O(1) lookup vs Array.includes() O(n). 100x faster for large collections
- Map.get() — O(1) vs scanning object keys. Better for frequent lookups
- Object vs Map — Map is faster for frequent add/delete. Object is fine for static configs