LRU and LFU Cache in Scala way with Advanced Data Structure Design


  • 0
    F

    for data structure design, seperate the CacheObj with encapsulated State _capacity

    from StrategyInterceptor then by applying the type polymorphisim on different Cache Strategies.

      1. LRU 2. LFU

    for O(1) access complexity. combine HashMap and SortedLinkedList

    (Node, AccessCount)
    (A, 1),(B, 2), (C, 3), (D, 6), (E, 11)

    HashMap[K,Int] = (A, 1),(B, 2), (C, 3), (D, 6), (E, 11)
    CycledSortedLinkedList = 1 -> 2 -> 3 -> 6 -> 11 -> 1(header)

    the HashMap ensured the access complexity is O(1)
    the CycledSortedLinkedList Ensured the Visit Order Change time complexity is O(1)

    so the total visit order's time complexity is O(1)
    when visit A 1 more time so the Map Entry is (A, 2)
    then the CycledSortedLinkedList = 2 -> 2 -> 3 -> 6 -> 11 -> 2(header)

    when visit A 1 more time so the Map Entry is (A, 3)
    the temp CycledSortedLinkedList = 3 -> 2 -> 3 -> 6 -> 11 -> 2(header)
    then process to the reverse node 3 and 2 op

    This Op is also O(1) and the final result is : B -> A -> C -> D -> E -> (B)
    and Finally got the solution

    '''
    trait CacheInterceptor[K] {

      val visitCountMap = mutable.LinkedHashMap[K,Int]()
      val visitFrequencyMap = mutable.LinkedHashMap[K,Double]()
      val totalVisitCountMap = mutable.LinkedHashMap[K,Int]()
      var totalVisitCount = 0
    
    
      type CacheStrategyFn = Cache[K,Int] => K
    
      val leastRecentlyUsedCacheStrategy:CacheStrategyFn = leastRecentlyUsedCacheStrategyFn
      val leastFrequentlyUsedCacheStrategy:CacheStrategyFn = leastFrequentlyUsedCacheStrategyFn
    
      //TODO:
      def leastRecentlyUsedCacheStrategyFn(c:Cache[K,Int]):K = {
    
      }
    
      //TODO:
      def leastFrequentlyUsedCacheStrategyFn(c:Cache[K,Int]):K = {
    
      }
    
      def visit(key:K) = {
    
          totalVisitCount = totalVisitCount + 1
    
          val visitCount = visitCountMap.getOrElseUpdate(key ,0) + 1
          visitCountMap.update(key, visitCount)
    
          val visitFrequency = visitCount / totalVisitCount
          visitFrequencyMap.put(key, visitFrequency)
    
      }
    
      def validate(cache:Cache[K,Int], violationFn:CacheStrategyFn => K):Option[K] = {
          cache._cache.size >= cache._capacity
          Some(violationFn(cache))
      }
    

    }
    class Cache[K,Int] (capacity:Int) {

    type AccessStrategyFn = Map[K,Int] => K

    val fn:AccessStrategyFn

    lazy val _capacity:Int = capacity

    val _cache = mutable.HashMapK,Int

    def get(key: K):Int = {
    _cache.getOrElse(key, -1)
    }

    def put(key:K, value:Int) = {

      if (_cache.size == _capacity) {
          val key = fn(_cache)
          _cache - key
      }
    
       _cache.+=((key, value))
    

    }

    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.