[Algorithm][Kotlin] LRU 알고리즘

캐시

• 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 저장소로, 리소스에 대한 중복 요청을 막거나 바뀌지 않는 데이터를 새로 불러오는 비용을 줄이기 위해 사용된다.

[CS] 캐시 (Cache)

---

LRU(Least Recently Used) 알고리즘

• 가장 오랫동안 사용되지 않은 데이터를 제거하여 새로운 데이터를 저장하는 방식으로, 메모리 사용량을 효율적으로 관리할 수 있도록 도와준다.
• 최근에 사용되지 않은 데이터는 앞으로도 사용될 가능성이 낮기 때문에, 데이터에 대한 접근 시간을 기록하고, 가장 오래된 데이터를 찾아 제거한다.
• 캐시의 일관성을 유지하기 위해 Write-Through 또는 Write-Behind 전략을 사용할 수 있다.
• LRU 알고리즘은 다음과 같은 단계를 거쳐 동작한다.
  1. 데이터가 캐시에 접근될 때마다 해당 데이터의 접근 시간을 갱신한다.
  2. 캐시가 가득 찼을 때 새로운 데이터를 추가하려면 가장 오래된 데이터를 제거한다.
  3. 새로운 데이터를 캐시에 추가하고 접근 시간을 기록한다.

class Node(val data: String, var prev: Node? = null, var next: Node? = null)

class DoublyLinkedList(private val cacheSize: Int) {
    private val head = Node("")
    private val tail = Node("")

    init {
        head.next = tail
        tail.prev = head
    }

    fun LRU(data: String) {
        print("[Put $data] ")
        var node = head.next
        while (node?.data != "") {
            if (node?.data == data) {
                cacheHit(node, data)
                return
            }
            node = node?.next
        }
        cacheMiss(data)
    }

    // 원소 맨앞으로 이동
    private fun cacheHit(node: Node, data: String) {
        removeNode(node)
        addFront(data)
        print("[Hit ] ")
        printAll()
    }

    // node 삭제
    private fun removeNode(node: Node) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    // head 의 바로 뒤에 원소 넣기
    private fun addFront(data: String) {
        val newNode = Node(data)
        head.next?.prev = newNode
        newNode.next = head.next
        head.next = newNode
        newNode.prev = head
    }

    // 원소의 맨앞에 추가 (cacheSize 보다 커지면 tail에 가까운 노드 삭제)
    private fun cacheMiss(data: String) {
        addFront(data)
        if (totalLen() > cacheSize) {
            removeTail()
        }
        print("[Miss] ")
        printAll()
    }

    // linked list 의 총 길이 반환
    private fun totalLen(): Int {
        var answer = 0
        var node = head.next
        while (node?.data != "") {
            answer++
            node = node?.next
        }
        return answer
    }

    // tail 에 가장 가까운 원소 삭제
    private fun removeTail() {
        tail.prev?.prev?.next = tail
        tail.prev = tail.prev?.prev
    }

    // For Debug
    // head 부터 tail 까지 순환하면서 date 전부 출력
    fun printAll() {
        var node = head.next
        while (node?.data != "") {
            print(node?.data)
            node = node?.next
            if (node?.data != "") {
                print(" -> ")
            }
        }
        println()
    }
}

fun main() {
    val test = DoublyLinkedList(3)
    val inputArray = listOf("1", "2", "1", "3", "4", "1", "5", "4")
    for (input in inputArray) {
        test.LRU(input)
    }
}

---

효율적인 캐시 설계와 구현 전략

LRU 캐시 알고리즘의 이해와 구현

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법