Напиши LRU кэш через class в JavaScript с применением Typescript и коротко, но понятно…
- User
Напиши LRU кэш через class в JavaScript с применением Typescript и коротко, но понятно объясни принцип работы
- Assistant
Конечно! Вот пример простой реализации LRU (Least Recently Used) кэша на TypeScript с использованием класса:
✅ Принцип работы LRU-кэша:
LRU-кэш хранит ограниченное количество элементов и удаляет наименее недавно используемый элемент, когда кэш переполнен.
Ключевая идея: каждый раз, когда элемент используется, он считается "свежим" и перемещается в начало ("голову"). При превышении лимита удаляется элемент из "конца" ("хвоста").
🧠 Структура данных:
- Map хранит пары
ключ => значение, и при этом сохраняет порядок вставки. - Для LRU мы каждый раз:
- Удаляем ключ и вставляем заново — тем самым переносим его в конец Map (как "самый недавно использованный").
📦 Простой TypeScript код LRU-кэша:
class LRUCache<K, V> { private cache: Map<K, V>; private capacity: number; constructor(capacity: number) { this.capacity = capacity; this.cache = new Map(); } get(key: K): V | undefined { if (!this.cache.has(key)) return undefined; // Обновляем порядок: удаляем и вставляем заново const value = this.cache.get(key)!; this.cache.delete(key); this.cache.set(key, value); return value; } put(key: K, value: V): void { if (this.cache.has(key)) { this.cache.delete(key); // Удаляем старое значение } else if (this.cache.size >= this.capacity) { // Удаляем самый старый (наименее недавно использованный) const oldestKey = this.cache.keys().next().value; this.cache.delete(oldestKey); } this.cache.set(key, value); } }
🔍 Пример использования:
const cache = new LRUCache<string, number>(2); cache.put("a", 1); // ["a"] cache.put("b", 2); // ["a", "b"] cache.get("a"); // ["b", "a"] cache.put("c", 3); // ["a", "c"] — "b" удаляется
Если нужно — могу улучшить кэш с использованием двусвязного списка для более эффективных операций (O(1) на вставку и удаление), как в "производственных реализациях".
Надеюсь, стало понятнее!
- Map хранит пары
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.