캐 시 알고리즘 (FIFO, LRU, LFU 세 가지 알고리즘 의 차이)

1. FIFO 알고리즘
FIFO 알고리즘 은 비교적 실현 하기 쉬 운 알고리즘 이다.그것 의 사상 은 선진 적 인 선 출 (FIFO, 대열) 이다. 이것 은 가장 간단 하고 공평 한 사상 이다. 즉, 데이터 가 가장 먼저 들 어 오 면 미래 에 방문 할 가능성 이 적다 고 볼 수 있다.공간 이 꽉 찼 을 때 가장 먼저 들 어 온 데 이 터 는 가장 먼저 바 뀌 고 (도태) 떨어진다.
FIFO 알고리즘 에 대한 설명: 캐 시 구 조 를 설계 합 니 다. 이 구 조 는 구조 할 때 크기 를 정 하고 크기 를 K 로 가정 하 며 두 가지 기능 이 있 습 니 다.
set (key, value): 기록 (key, value) 을 이 구조 에 삽입 합 니 다.캐 시가 가득 찼 을 때 가장 먼저 캐 시 에 들 어간 데 이 터 를 교체 합 니 다.get (key): key 에 대응 하 는 value 값 을 되 돌려 줍 니 다.실현: FIFO 대기 열 을 유지 하고 시간 순서에 따라 각 데이터 (분 배 된 페이지) 를 연결 하여 대기 열 을 구성 하 며 포인터 가 대기 열 을 가리 키 는 팀 의 첫 번 째 를 바 꿉 니 다.다시 교체 할 때 는 포인터 가 가리 키 는 데이터 (페이지) 를 순서대로 바 꾸 고 새로 추 가 된 데 이 터 를 줄 끝 에 꽂 으 면 된다.
단점: 한 페이지 교체 알고리즘 의 우열 을 판단 하 는 지 표 는 결 페이지 율 이다. FIFO 알고리즘 의 현저 한 단점 은 특정한 시간 에 결 페이지 율 이 오히려 분배 페이지 의 증가 에 따라 증가 하 는 것 을 Belady 현상 이 라 고 한다.Belady 현상 이 발생 하 는 이 유 는 FIFO 교체 알고리즘 과 프로 세 스 가 메모리 에 접근 하 는 동적 특징 이 서로 어 울 리 지 않 기 때 문 입 니 다. 변 경 된 메모리 페이지 는 자주 방문 하거나 프로 세 스에 충분 한 페이지 를 할당 하지 않 기 때문에 FIFO 알고리즘 은 일부 페이지 를 자주 교체 하고 메모리 재 신청 하여 결 장 률 을 증가 시 킬 수 있 습 니 다.따라서 이제 FIFO 알고리즘 을 사용 하지 않 는 다.
2. LRU 알고리즘
LRU (The Least Recently Used, 최근 가장 오랫동안 알고리즘 을 사용 하지 않 음) 는 흔히 볼 수 있 는 캐 시 알고리즘 으로 많은 분포 식 캐 시 시스템 (예 를 들 어 Redis, Memcached) 에서 널리 사용 된다.
LRU 알고리즘 은 데이터 가 최근 한 동안 접근 되 지 않 았 다 면 앞으로 접근 할 가능성 도 적다 고 볼 수 있다 는 사상 이다.따라서 공간 이 가득 찼 을 때 가장 오랫동안 방문 하지 않 은 데이터 가 가장 먼저 바 뀌 었 다 (도태).
LRU 알고리즘 에 대한 설명: 캐 시 구 조 를 설계 합 니 다. 이 구 조 는 구조 할 때 크기 를 정 하고 크기 를 K 로 가정 하 며 두 가지 기능 이 있 습 니 다.
set (key, value): 기록 (key, value) 을 이 구조 에 삽입 합 니 다.캐 시가 가득 찼 을 때 가장 오래 사용 하지 않 은 데 이 터 를 교체 합 니 다.get (key): key 에 대응 하 는 value 값 을 되 돌려 줍 니 다.실현: 가장 소박 한 사상 은 배열 + 시간 스탬프 방식 이지 만 이렇게 하 는 것 은 효율 이 비교적 낮다.따라서 우 리 는 양 방향 링크 (LinkedList) + 해시 표 (HashMap) 로 (링크 는 위 치 를 표시 하고 해시 표 는 저장 하고 찾 는 데 사용) 를 실현 할 수 있 으 며 자바 에 해당 하 는 데이터 구조 인 LinkedHashMap 이 있 습 니 다.

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int cacheSize;

    public LRUCache(int cacheSize) {
        super(16, (float)0.75, true);
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }

    private static final Logger log = LoggerFactory.getLogger(LRUCache.class);
    private static LRUCache<String, Integer> cache = new LRUCache<>(10);


    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            cache.put("k" + i, i);
        }
        log.info("all cache :'{}'",cache);
        cache.get("k3");
        log.info("get k3 :'{}'", cache);
        cache.get("k4");
        log.info("get k4 :'{}'", cache);
        cache.get("k4");
        log.info("get k4 :'{}'", cache);
        cache.put("k" + 10, 10);
        log.info("After running the LRU algorithm cache :'{}'", cache);
    }
}

output:

16:59:25.312 [main] INFO com.example.springdemo.test.lru.LRUCache - all cache :'{k0=0, k1=1, k2=2, k3=3, k4=4, k5=5, k6=6, k7=7, k8=8, k9=9}'
16:59:25.316 [main] INFO com.example.springdemo.test.lru.LRUCache - get k3 :'{k0=0, k1=1, k2=2, k4=4, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3}'
16:59:25.316 [main] INFO com.example.springdemo.test.lru.LRUCache - get k4 :'{k0=0, k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4}'
16:59:25.316 [main] INFO com.example.springdemo.test.lru.LRUCache - get k4 :'{k0=0, k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4}'
16:59:25.316 [main] INFO com.example.springdemo.test.lru.LRUCache - After running the LRU algorithm cache :'{k1=1, k2=2, k5=5, k6=6, k7=7, k8=8, k9=9, k3=3, k4=4, k10=10}'

3. LFU 알고리즘
LFU (Least Frequently Used, 최근 최소 알고리즘 사용) 도 흔히 볼 수 있 는 캐 시 알고리즘 이다.
말 그대로 LFU 알고리즘 은 데이터 가 최근 에 거의 접근 되 지 않 으 면 앞으로 접근 할 가능성 도 적다 고 볼 수 있다 는 사상 이다.따라서 공간 이 가득 찼 을 때 최소 주파수 로 접근 하 는 데이터 가 가장 먼저 도태 된다.
LFU 알고리즘 설명:
캐 시 구 조 를 설계 합 니 다. 이 구 조 는 구조 할 때 크기 를 정 하고 크기 를 K 로 가정 하 며 두 가지 기능 이 있 습 니 다.
set (key, value): 기록 (key, value) 을 이 구조 에 삽입 합 니 다.캐 시가 가득 찼 을 때 접근 빈도 가 가장 낮은 데 이 터 를 교체 합 니 다.get (key): key 에 대응 하 는 value 값 을 되 돌려 줍 니 다.알고리즘 구현 전략: LFU 가 접근 빈도 가 가장 작은 데 이 터 를 도태 시 킬 수 있 음 을 고려 하여 데이터 접근 빈 도 를 크기 순 으로 유지 하 는 적절 한 방법 이 필요 합 니 다.LFU 알고리즘 은 본질 적 으로 주파수 가 가장 작은 요 소 를 선택 하 는 top K 문제 (K = 1) 로 볼 수 있 기 때문에 주파수 가 가장 작은 요 소 를 두 가지 로 쌓 아 올 릴 수 있다 는 생각 이 들 기 쉬 워 효율 적 이다.최종 실현 전략 은 작은 지붕 + 해시 표 입 니 다.
참고:https://www.cnblogs.com/hongdada/p/10406902.html