3.4. Cache - 3.4.3 MFU Cache

CS - 3. Common Algorithms - 3.4. Cache - 3.4.3 MFU Cache

 

💡MFU Cache is another cache algorithm. The difference is that instead of deleting the least frequently used entry, the MFU Cache deletes the most frequently used entry.

MFU 캐시는 또 다른 캐시 알고리즘입니다. 차이점은 사용 빈도가 가장 낮은 항목을 삭제하는 대신 가장 자주 사용되는 항목을 삭제한다는 점입니다.

 

MFU(Most Frequently Used) Cache는 이름에서 알 수 있듯이 
가장 자주 사용되는 항목을 캐시에 보관하는 캐싱 알고리즘입니다.

이 알고리즘은 각 항목의 사용 빈도를 추적하며, 캐시가 가득 찼을 때 가장 자주 사용된 항목을 캐시에 유지하고 가장 적게 사용된 항목을 제거합니다.
이는 자주 사용되는 항목이 미래에도 계속 사용될 가능성이 높다는 가정에 기반을 두고 있습니다.

 

In Python

from collections import Counter

class MFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.counter = Counter()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.counter[key] += 1
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if len(self.cache) >= self.capacity and key not in self.cache:
            mfu_key = self.counter.most_common(1)[0][0]
            del self.cache[mfu_key]
            del self.counter[mfu_key]
        self.cache[key] = value
        self.counter[key] += 1

 

MFU 캐쉬를 파이썬에서 구현해보았습니다.

get 함수는 특정 키의 값을 반환하고 사용 빈도를 증가시킵니다.

put 함수는 새로운 값을 캐시에 추가합니다.

캐시의 용량이 초과되면 가장 빈번하게 사용된 항목을 캐시에서 제거합니다.

Counter 클래스는 항목의 사용 빈도를 추적하는데 사용합니다.

 

 

MFU Cache는 데이터의 사용 패턴이 일정하고 예측 가능한 경우에 특히 효과적입니다. 
예를 들어, 특정 웹 페이지가 자주 조회되거나 특정 데이터셋이 자주 사용되는 경우 등이 있습니다.

 

 

LFU 와 MFU 의 차이

LFU(Least Frequently Used)와 MFU(Most Frequently Used)는 둘 다 사용 빈도에 기반한 캐시 교체 알고리즘이지만, 이 두 알고리즘은 캐시에서 어떤 항목을 제거할지 결정하는 방식에서 차이가 있습니다.

 

LFU (Least Frequently Used) 캐시: LFU 알고리즘은 가장 적게 사용된 항목을 캐시에서 제거합니다. 

즉, 캐시에 저장된 항목 중에서 사용 빈도가 가장 낮은 항목을 제거하는 방식입니다. 

이 알고리즘은 자주 사용되는 항목이 미래에도 계속 사용될 가능성이 높다는 가정에 기반을 두고 있습니다. 

그러나, 한 번 많이 사용된 후로는 사용되지 않는 항목이 캐시에 계속 남아있을 수 있는 단점이 있습니다.

MFU (Most Frequently Used) 캐시: MFU 알고리즘은 가장 자주 사용된 항목을 캐시에 유지합니다. 

즉, 캐시에 저장된 항목 중에서 사용 빈도가 가장 높은 항목을 제거하는 방식입니다. 

이는 빈도가 높은 항목이 빈도가 낮은 항목보다 덜 중요하다는 가정에 기반을 두고 있습니다. 

그러나, 일시적으로 빈도가 높아진 항목이 캐시에 오래 남아있을 수 있는 단점이 있습니다.

LFU와 MFU는 모두 사용 빈도를 고려하는 알고리즘입니다만, 어떤 데이터를 캐시에서 제거할지에 대한 기준에서 차이가 있습니다.