LFU – algorytm najrzadziej używanego (Least Frequently Used)

LFU (ang. Least Frequently Used) to metoda zarządzania pamięcią podręczną oraz innymi strukturami danych polegająca na usuwaniu elementów o najniższej częstotliwości odwołań. Algorytm ten jest jedną z klasycznych strategii zastępowania wyposażenia w systemach informatycznych, szczególnie w systemach operacyjnych, bazach danych i przeglądarkach internetowych.

Historia

Pierwsze koncepcje algorytmu LFU pojawiły się w latach 70. XX wieku w kontekście zarządzania pamięcią w systemach multiprogramowych. Został on sformalizowany w pracach badawczych poświęconych strategiom zastępowania stron w pamięci wirtualnej, a później adaptowany do nowoczesnych rozwiązań cache’owych w językach programowania i systemach plików.

Założenia i zasada działania

Każdemu elementowi przechowywanemu w cache przydzielana jest liczba odwołań (licznik użycia).
Po każdym odczycie elementu jego licznik jest inkrementowany.
Gdy pamięć podręczna osiąga maksymalny rozmiar i wymagana jest zwolnienie miejsca, usuwany jest element o najniższej wartości licznika.
W sytuacji, gdy istnieje więcej niż jeden element o takim samym najniższym liczniku, najczęściej stosuje się dodatkowy kryterium, np. LRU (Least Recently Used) lub datę wstawienia.

Implementacje

W praktyce algorytm LFU można realizować na kilka sposobów:

Tablica liczników – każdy element ma powiązany licznik przechowywany w strukturze tablicy haszującej.
Drzewa uporządkowane – elementy są przechowywane w drzewie binarnym lub drzewie B, posortowane według licznika użycia.
Listy częstotliwości – użycie wielopoziomowych list, gdzie każdy poziom odpowiada określonej wartości licznika (tzw. frequency list).

Zalety

Skutecznie eliminuje rzadko wykorzystywane dane, co może zwiększyć skuteczność cache’a w aplikacjach o nieregularnym wzorze dostępu.
Łatwość adaptacji do wymagań systemów wysokiej wydajności, w których priorytetem jest przechowywanie „gorących” danych.

Wady

Wymaga przechowywania dodatkowych liczników, co zwiększa zużycie pamięci.
Może prowadzić do tzw. pamięci zombie – danych, które były intensywnie używane w przeszłości, ale nie są już potrzebne, a ich licznik pozostaje wysoki.
Aktualizacja liczników przy każdym odwołaniu może generować dodatkowy narzut obciążenia systemu.

Zastosowania

Algorytm LFU znajduje zastosowanie w wielu dziedzinach:

Przeglądarki internetowe – do buforowania najczęściej odwiedzanych zasobów.
Systemy baz danych – w buforach indeksów i wyników zapytań.
Systemy operacyjne – w zarządzaniu pamięcią wirtualną i buffer cache.
Kompresja danych – w algorytmach takich jak LZW, gdzie rastrowane są najczęściej występujące ciągi znaków.

Warianty i hybrydy

W praktyce często łączy się LFU z innymi strategiami, tworząc hybrydowe algorytmy:

LFU‑LRU – najpierw wybiera element o najniższym liczniku, a w przypadku remisu stosuje regułę LRU.
LFU‑DLRU (Dynamic LRU) – dynamicznie dostosowuje wagę licznika i czasu ostatniego użycia w zależności od charakterystyki obciążenia.

Przykładowy kod (Python)

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.val = {}
        self.freq = {}
        self.count = {}
        self.min_freq = 0

    def get(self, key):
        if key not in self.val:
            return -1
        self._update(key)
        return self.val[key]

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.val:
            self.val[key] = value
            self._update(key)
            return
        if len(self.val) >= self.cap:
            # usuń element o najniższej częstotliwości
            old_key = self.count[self.min_freq].pop()
            del self.val[old_key]
            del self.freq[old_key]
        self.val[key] = value
        self.freq[key] = 1
        self.min_freq = 1
        self.count.setdefault(1, set()).add(key)

    def _update(self, key):
        f = self.freq[key]
        self.count[f].remove(key)
        if not self.count[f]:
            del self.count[f]
            if self.min_freq == f:
                self.min_freq += 1
        self.freq[key] = f + 1
        self.count.setdefault(f + 1, set()).add(key)

Patrz także

Algorytm LFU pozostaje ważnym elementem narzędzi projektanta systemów informatycznych, zwłaszcza w środowiskach, w których dostęp do danych musi być szybki, a zasoby pamięciowe ograniczone.