LRU Cache

Q: האם תוכל לבנות מטמון LRU באמצעות מילון מסודר?

כן. מפה ששומרת על סדר ההוספה, כמו OrderedDict של Python או LinkedHashMap של Java, יכולה להחליף את הרשימה: מעבירים מפתח לסוף בכל שימוש ומסלקים מההתחלה, ועדיין בזמן O(1). מראיינים בדרך כלל מצפים שתבנה את הרשימה בעצמך.

בינוניגיבוב רשימה מקושרת

+10

בנו מטמון שמכיל לכל היותר capacity מפתחות. get key מחזירה את ערך המפתח, או -1 אם הוא לא נמצא במטמון. put key value שומרת את הערך ומחליפה כל ערך ישן; אם המפתח חדש והמטמון מלא, היא מפנה תחילה את המפתח שבו נעשה השימוש הכי פחות לאחרונה. פעולת get שמוצאת את המפתח שלה וכל פעולת put נחשבות לשימוש.

פעולה i היא ops[i] ("get" או "put") על המפתח keys[i], עם הערך values[i] (0 עבור get). הריצו אותן לפי הסדר על מטמון ריק והחזירו מחרוזת אחת עבור כל פעולה: "null" עבור put, ואת הערך או "-1" עבור get.

פונקציה

lruCacheOps(capacity: integer, ops: string-array, keys: integer-array, values: integer-array) → string-array

capacityinteger: המספר המרבי של מפתחות שהמטמון יכול להכיל בו־זמנית
opsstring-array: הפעולות, לפי סדר הביצוע שלהן
keysinteger-array: המפתח שעליו כל פעולה פועלת
valuesinteger-array: הערך עבור כל put, 0 עבור כל get
מחזירהstring-array: תשובה אחת לכל פעולה, כטקסט

אילוצים

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
כל ops[i] הוא get או put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ עבור פעולת put, ו-values[i] == 0 עבור פעולת get.

דוגמאות

קלט: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
פלט: ["null", "null", "10", "null", "-1", "30"]
הסבר: הפעולה get הופכת את מפתח 1 למפתח שנעשה בו שימוש לאחרונה, ולכן put 3 מפנה את מפתח 2: get 2 מחזירה "-1" ו-get 3 מחזירה "30".

קלט: capacity = 2ops = ["put", "put", "put", "put", "get", "get", "get"]keys = [5, 6, 5, 7, 5, 6, 7]values = [1, 2, 3, 4, 0, 0, 0]
פלט: ["null", "null", "null", "null", "3", "-1", "4"]
הסבר: הפעולה השלישית put מעדכנת את המפתח 5, שכבר נמצא במטמון: שום דבר לא מפונה והמפתח 5 הופך לפריט שנעשה בו השימוש לאחרונה. לכן put 7 מפנה את המפתח 6, ולא את המפתח 5.

קלט: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
פלט: ["-1", "null", "0", "null", "-1", "8"]
הסבר: כשיש מקום למפתח אחד, כל מפתח חדש מפנה את מקומו של המפתח שקדם לו. פעולת ה־get הראשונה מחטיאה כשהמטמון ריק; לאחר מכן מפתח 0 מחזיק בערך האמיתי 0 עד ש־put 8 מפנה אותו.

שאלת המשך

איך היית משנה את המטמון כך שיפנה במקום זאת את המפתח שהשתמשו בו בתדירות הנמוכה ביותר, ובמקרה של תיקו — את המפתח שהשימוש האחרון בו היה הכי מזמן, ועדיין בזמן O(1) לכל פעולה?

פתרון

פעולת get חייבת למצוא מפתח במהירות, ופעולת פינוי חייבת למצוא במהירות את המפתח שהשימוש בו היה הכי פחות לאחרונה. מפת גיבוב עושה את הראשון, ורשימה המסודרת לפי סדר השימוש עושה את השני. השתמשו בשניהם: מיפו כל מפתח לצומת שלו ברשימה מקושרת כפולה המסודרת לפי שימוש.

סרוק טבלה של רשומות עם זמני השימוש האחרונים

האינטואיציה

אחסן עד capacity ערכים במערכים: מפתח, ערך וחותמת שימוש אחרון מתוך מונה שעולה בכל פעולה. מפתח חדש במטמון מלא מחליף את הערך עם החותמת הקטנה ביותר — המפתח שלא נעשה בו שימוש במשך הזמן הארוך ביותר. בדוגמה הראשונה, ב־put 3 למפתח 1 יש חותמת 3 ולמפתח 2 יש חותמת 2, ולכן מפתח 2 יוצא.

כל פעולה סורקת עד capacity ערכים: O(n × capacity) עבור n פעולות, מיליוני השוואות ב־3,000 פעולות במטמון של 1,500 מפתחות.

אלגוריתם

החזק את המערכים keys, values ו-used, מונה מילוי ושעון שמתחיל ב-0.
כל פעולה מוסיפה 1 לשעון וסורקת את הרשומות המלאות כדי למצוא את המפתח שלה.
get: במקרה של החטאה, החזר -1; במקרה של התאמה, הגדר את used לשעון והחזר את הערך.
put: במקרה של התאמה, שמור את הערך ואת השעון. במקרה של החטאה, כתוב את המפתח, הערך והשעון ברשומה פנויה, או ברשומה שבה used הוא הקטן ביותר.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        # Entry i holds keys[i] -> values[i] and was last used at time used[i].
        self.keys = [0] * capacity
        self.values = [0] * capacity
        self.used = [0] * capacity
        self.size = 0
        self.time = 0

    def _find(self, key):
        for i in range(self.size):
            if self.keys[i] == key:
                return i
        return -1

    def get(self, key):
        self.time += 1
        i = self._find(key)
        if i == -1:
            return -1
        self.used[i] = self.time
        return self.values[i]

    def put(self, key, value):
        self.time += 1
        i = self._find(key)
        if i == -1:
            if self.size < self.capacity:
                i = self.size
                self.size += 1
            else:
                # Full: scan for the entry used longest ago and take its place.
                i = 0
                for j in range(1, self.capacity):
                    if self.used[j] < self.used[i]:
                        i = j
            self.keys[i] = key
        self.values[i] = value
        self.used[i] = self.time

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

מפת גיבוב ועוד רשימה מקושרת כפולה

האינטואיציה

כל צומת ברשימה מקושר לשני השכנים שלו, כך שכשיש לך את הצומת ביד, אפשר לנתק אותו או להוסיף אותו בתחילת הרשימה באמצעות שינוי של ארבעה קישורים. המפה מספקת לך את הצומת, ולכן שום פעולה לא עוברת על פני הרשימה.

פגיעה בחיפוש או הוספה של מפתח שמור במטמון מעבירה את הצומת לתחילת הרשימה. מפתח חדש במטמון מלא מסיר את הצומת שבסוף ומוחק את המפתח שלו מהמפה, ולכן כל צומת שומר את המפתח שלו. צומתי הזקיף head ו-tail נשארים בקצוות, כך שניתוק והוספה לעולם לא מצריכים בדיקה אם שכן חסר. כל פעולה היא חיפוש אחד ועוד כמה שינויים בקישורים: O(1).

אלגוריתם

קשרו את זקיפי הגבול head ו-tail; התחילו עם מפה ריקה ממפתחות לצמתים.
get key: החזירו -1 אם המפתח אינו במפה; אחרת העבירו את הצומת שלו אחרי head והחזירו את הערך שלו.
put של מפתח שמור במטמון: שמרו את הערך והעבירו את הצומת אחרי head.
put של מפתח חדש: אם המפה מכילה capacity מפתחות, נתקו את הצומת שלפני tail ומחקו את המפתח שלו מהמפה. הכניסו צומת חדש אחרי head ומפו את המפתח לצומת הזה.

class ListNode:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}            # key -> its node in the list
        # Sentinels: head.next is the most recently used node,
        # tail.prev the least recently used one.
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                # Full: drop the least recently used node.
                oldest = self.tail.prev
                self._unlink(oldest)
                del self.nodes[oldest.key]
            node = ListNode(key, value)
            self.nodes[key] = node
        self._push_front(node)

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

מלכודות ומקרי קצה

לא להעביר מפתח לחזית כשיש פגיעה במטמון בעקבות קריאה. בדוגמה הראשונה, put 3 יפנה אז את מפתח 1, ולא את מפתח 2.
לפנות מקום לפני שבודקים אם המפתח נמצא במטמון. בקיבולת 2, הרצף put 1, put 2, put 2 יפנה את מפתח 1.
לנתק צומת אך להשאיר את המפתח שלו במפה, או להפך. המפה תחזיר אז צומת מנותק, והעברתו תפגום בקישורים של השכנים הקודמים שלו.
להתייחס לערך 0 שמאוחסן כאל החטאה. בדוגמה השלישית, get 0 חייב להחזיר "0".

שאלות נפוצות3

מהי סיבוכיות הזמן של מטמון LRU?

בעזרת מפת גיבוב ורשימה מקושרת כפולה, פעולות השליפה וההוספה פועלות שתיהן בזמן O(1): חיפוש אחד ועוד כמה שינויים בקישורים. המקום הנדרש הוא O(capacity), צומת אחד ורשומה אחת במפה לכל מפתח.

למה מטמון LRU משתמש ברשימה מקושרת כפולה?

המטמון מעביר מפתחות מכל מקום בסדר אל החזית ומשמיט את המפתח שבסוף. רשימה מקושרת כפולה מבצעת את שתי הפעולות בעזרת כמה שינויים בקישורים, כי כל צומת מכיר את הצומת שלפניו. ברשימה מקושרת יחידה צריך לעבור מהראש כדי למצוא את הצומת הזה, פעולה שעלותה O(capacity).

האם תוכל לבנות מטמון LRU באמצעות מילון מסודר?

כן. מפה ששומרת על סדר ההוספה, כמו OrderedDict של Python או LinkedHashMap של Java, יכולה להחליף את הרשימה: מעבירים מפתח לסוף בכל שימוש ומסלקים מההתחלה, ועדיין בזמן O(1). מראיינים בדרך כלל מצפים שתבנה את הרשימה בעצמך.

def lruCacheOps(capacity, ops, keys, values):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

capacity = 2
ops = ["put", "put", "get", "put", "get", "get"]
keys = [1, 2, 1, 3, 2, 3]
values = [10, 20, 0, 30, 0, 0]

הפלט הצפוי

["null", "null", "10", "null", "-1", "30"]