Кэш LRU, LFU
Кэш LRU и LFU — это две популярные стратегии управления кэшем, которые используются для определения того, какие данные нужно удалять из кэша, чтобы освободить место для новых данных.
1. LRU (Least Recently Used)
Суть алгоритма:
Удаляется элемент, который дольше всех не использовался.
- Механизм работы:
- Когда элемент добавляется или запрашивается из кэша, он помечается как недавно использованный.
- Если кэш заполнен, удаляется элемент, к которому дольше всего не было доступа.
- Преимущества:
- Простота реализации.
- Хорошо работает, если часто используются одни и те же данные.
- Недостатки:
- Неэффективен, если одни данные используются редко, но равномерно, а другие — одноразово.
- Реализация: Обычно реализуется с помощью связного списка и хэш-таблицы:
- Связный список поддерживает порядок элементов от самого недавно использованного до самого старого.
- Хэш-таблица обеспечивает быстрый доступ к элементам.
- Пример использования:
- Веб-браузеры для хранения истории посещённых страниц.
2. LFU (Least Frequently Used)
Суть алгоритма:
Удаляется элемент, который реже всего использовался.
- Механизм работы:
- У каждого элемента кэша есть счётчик частоты использования.
- При каждом обращении к элементу его счётчик увеличивается.
- Если кэш заполнен, удаляется элемент с наименьшим счётчиком.
- Преимущества:
- Эффективен для данных, которые часто используются в течение долгого времени.
- Недостатки:
- Не учитывает временной фактор: элемент, часто использовавшийся в прошлом, может оставаться в кэше, даже если сейчас он больше не нужен.
- Усложнённая реализация.
- Реализация:
- Хэш-таблица для хранения элементов.
- Дополнительные структуры данных (например, дерево или список) для отслеживания минимальных счётчиков.
- Пример использования:
- Системы с чёткими требованиями к частоте доступа, например, в базах данных.
Сравнение LRU и LFU
| Критерий | LRU | LFU |
|---|---|---|
| Принцип удаления | Наименее недавно использованный | Наименее часто использованный |
| Учет времени | Учитывает временной порядок | Не учитывает временной порядок |
| Сложность | Простая | Более сложная |
| Сценарий использования | Данные, часто меняющиеся со временем | Данные с высокой долговременной ценностью |
Выбор между LRU и LFU
- Используйте LRU, если:
- Вы работаете с данными, которые имеют временную локальность (например, одни данные используются короткое время, а потом заменяются новыми).
- Вам нужна простая и быстрая стратегия.
- Используйте LFU, если:
- Важно сохранять данные, которые используются с определённой частотой.
- Ваши данные не зависят сильно от времени использования, а их актуальность определяется частотой обращений.
Примерная реализация на Go
LRU:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
type LRUCache struct { capacity int cache map[int]*list.Element list *list.List } type Pair struct { key, value int } func NewLRUCache(capacity int) *LRUCache { return &LRUCache{ capacity: capacity, cache: make(map[int]*list.Element), list: list.New(), } } func (l *LRUCache) Get(key int) (int, bool) { if elem, found := l.cache[key]; found { l.list.MoveToFront(elem) return elem.Value.(Pair).value, true } return -1, false } func (l *LRUCache) Put(key, value int) { if elem, found := l.cache[key]; found { l.list.MoveToFront(elem) elem.Value = Pair{key, value} } else { if l.list.Len() == l.capacity { back := l.list.Back() l.list.Remove(back) delete(l.cache, back.Value.(Pair).key) } elem := l.list.PushFront(Pair{key, value}) l.cache[key] = elem } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
type LFUCache struct { capacity int cache map[int]int // key -> value freq map[int]int // key -> frequency } func NewLFUCache(capacity int) *LFUCache { return &LFUCache{ capacity: capacity, cache: make(map[int]int), freq: make(map[int]int), } } func (l *LFUCache) Get(key int) (int, bool) { if value, found := l.cache[key]; found { l.freq[key]++ return value, true } return -1, false } func (l *LFUCache) Put(key, value int) { if len(l.cache) == l.capacity { l.evict() } l.cache[key] = value l.freq[key]++ } func (l *LFUCache) evict() { minFreq := int(^uint(0) >> 1) // Максимальное значение int var keyToEvict int for key, freq := range l.freq { if freq < minFreq { minFreq = freq keyToEvict = key } } delete(l.cache, keyToEvict) delete(l.freq, keyToEvict) } |
Эти примеры можно расширить для повышения производительности, используя более сложные структуры данных.
Recommended Posts
Golang Sarama: настройка Partitioner
20.03.2024