Шаг 1

Самая частая проблема для использования Map — кеширование. Про него мы уже говорили во втором разделе, когда познакомились с Map. Теперь пришло время и самим написать кеш! Напомним, что кеш — это некая структура данных, с помощью которой мы «запоминаем» результаты выполнения долгих функций (запрос с API или просто тяжёлые вычисления) и потом переиспользуем их вместо того, чтобы заново всё высчитывать. Было бы хорошо, чтобы кеш работал за O(1) на чтение и запись (что Map нам и позволяет сделать). Писать будем так называемый LRU-кеш или Least Recently Used кеш. Суть его в том, чтобы запоминать только последние несколько записей (сколько — дело нашей настройки), а как только в него пытаются записать больше — удалять самую старую. Такой кеш хорошо подходит для случаев, когда параметров может быть очень много, а памяти мы хотим или можем выделять только определённое количество.

class Cache {
  constructor(size) {
    // размер кеша в ключах, которые он может сохранить.
    this.size = size;
  }

  // Получение из кеша по ключу
  // (обычно ключом как раз выступает аргумент функции, которую мы хотим кешировать)
  get(key) {

  }

  // Запись в кеш
  set(key, value) {

  }

  // Удаление по ключу, если вдруг нам это пригодится
  delete(key) {

  }
}

Шаг 2

Для начала создадим непосредственно хеш-таблицу и опишем самые простые методы. Описание удаления и чтения из кеша очень просты — это всего лишь «обёртки» над встроенными в Map функциями.

class Cache {
  constructor(size) {
    // размер кеша в ключах, которые он может сохранить.
    this.size = size;
    this._map = new Map();
  }

  // Получение из кеша по ключу
  // (обычно ключом как раз выступает аргумент функции, которую мы хотим кешировать)
  get(key) {
    return this._map.get(key);
  }

  // Запись в кеш
  set(key, value) {

  }

  // Удаление по ключу, если вдруг нам это пригодится
  delete(key) {
    this._map.delete(key);
  }
}

Шаг 3

А вот с заполнением кеша не всё так просто — хотя с реализацией Map в JavaScript нам повезло больше, чем другим языкам. Перед тем, как положить новый ключ в таблицу, нам нужно убедиться, что она не переполнена. И если так есть, то удалить самый первый ключ. К счастью, Map хранит ключи итератором (получаемым методом keys()) в порядке добавления, а размер — отдельным полем size. Так что нам не придётся мучиться ни с поддержкой собственного счётчика размера, ни с организацией ключей в самописный связный список (хотя это мы уже можем делать).

class Cache {
  constructor(size) {
    // размер кеша в ключах, которые он может сохранить.
    this.size = size;
    this._map = new Map();
  }

  // Получение из кеша по ключу
  // (обычно ключом как раз выступает аргумент функции, которую мы хотим кешировать)
  get(key) {
    return this._map.get(key);
  }

  // Запись в кеш
  set(key, value) {
    if (this._map.size === this.size) {
      this.delete(this._first());
    }

    this._map.set(key, value);
  }

  _first() {
    return this._map.keys().next().value;
  }

  // Удаление по ключу, если вдруг нам это пригодится
  delete(key) {
    this._map.delete(key);
  }
}

Шаг 4

Можно убедиться в работоспособности нашего кеша на «игрушечных данных», но на самом деле он помогает решить настоящие проблемы.

import {logDelete, logSet, logGet} from './logger';

class Cache {
  constructor(size) {
    // размер кеша в ключах, которые он может сохранить.
    this.size = size;
    this._map = new Map();
  }

  // Получение из кеша по ключу
  // (обычно ключом как раз выступает аргумент функции, которую мы хотим кешировать)
  get(key) {
    const value = this._map.get(key);

    logGet(key, value);

    return value;
  }

  // Запись в кеш
  set(key, value) {
    if (this._map.size === this.size) {
      this.delete(this._first());
    }

    logSet(key, value);
    this._map.set(key, value);
  }

  _first() {
    return this._map.keys().next().value;
  }

  // Удаление по ключу, если вдруг нам это пригодится
  delete(key) {
    logDelete(key);
    this._map.delete(key);
  }
}

const cache = new Cache(2);

cache.set(1, 'foo');
cache.set(2, 'bar');

cache.get(1); // foo

cache.set(3, 'baz');

cache.get(1); // undefined

Шаг 5

Одним из частых применений кеша, помимо кеширования ответов запросов с API, является кеширование результата функций «Разделяй и властвуй». Как правило, они «скатываются» если не к одним и тем же, то к очень похожим случаям. Можно, например, написать гораздо более быструю реализацию функции для получения чисел Фибоначчи, просто скопировав её рекурсивную версию и внедрив в неё кеш! Посмотрите на сравнение быстродействия нашей старой функции для подсчета Фибоначчи и её же, но с кешем!

import {benchmark} from './benchmarker';

class Cache {
  constructor(size) {
    // размер кеша в ключах, которые он может сохранить.
    this.size = size;
    this._map = new Map();
  }

  // Получение из кеша по ключу
  // (обычно ключом как раз выступает аргумент функции, которую мы хотим кешировать)
  get(key) {
    return this._map.get(key);
  }

  // Запись в кеш
  set(key, value) {
    if (this._map.size === this.size) {
      this.delete(this._first());
    }

    this._map.set(key, value);
  }

  _first() {
    return this._map.keys().next().value;
  }

  // Удаление по ключу, если вдруг нам это пригодится
  delete(key) {
    this._map.delete(key);
  }
}

function cachedFibonacci() {
  const cache = new Cache(300);

  return function fibonacci(index) {
    if (index < 1 || !Number.isInteger(index)) {
      throw new Error("Индекс должен быть целым числом больше или равным единице!");
    }

    if (index === 1) {
      return 0;
    }

    if (index === 2) {
      return 1;
    }

    const cached = cache.get(index);

    if (cached) {
      return cached;
    }

    const calculated = fibonacci(index - 1) + fibonacci(index - 2);

    cache.set(index, calculated);

    return calculated;
  }
}

const fibonacci = cachedFibonacci();

function uncachedFibonacci(index) {
  if (index < 1 || !Number.isInteger(index)) {
    throw new Error("Индекс должен быть целым числом больше или равным единице!");
  }

  if (index === 1) {
    return 0;
  }

  if (index === 2) {
    return 1;
  }

  return uncachedFibonacci(index - 1) + uncachedFibonacci(index - 2);
}

benchmark(() => fibonacci(300));
benchmark(() => uncachedFibonacci(42));

File benchmarker.js

const results = document.getElementById('results')

export function benchmark(callback) {
  const start = performance.now();

  const result = callback();

  const end = performance.now();

  const time = (end - start) / 1000;

  log(`Получили ${result} за ${time.toFixed(5)} секунд`);
}

function log(message) {
  const result = document.createElement('li');

  result.innerHTML = message;

  results.appendChild(result);
}

File logger.js

const results = document.getElementById('results')

export function logDelete(key) {
  log(`Удалили ключ ${key}`);
}

export function logSet(key, value) {
  log(`Сохранили ${value} по ключу ${key}`);
}

export function logGet(key, value) {
  log(`Получили ${value} по ключу ${key}`);
}

function log(message) {
  const result = document.createElement('li');

  result.innerHTML = message;

  results.appendChild(result);
}