Efficient Data Structures & Algorithms

// 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)");