LRU Cache
أنشئ ذاكرة تخزين مؤقت تحتوي على capacity مفاتيح كحد أقصى. تُرجع get key قيمة المفتاح، أو -1 إذا لم يكن مخزّنًا مؤقتًا. تخزّن put key value القيمة، مستبدلةً أي قيمة أقدم؛ وإذا كان المفتاح جديدًا وكانت الذاكرة ممتلئة، فإنها تُخرج أولًا المفتاح الأقل استخدامًا مؤخرًا. يُحتسب العثور على المفتاح عند تنفيذ get، وكل put، استخدامًا.
العملية i هي ops[i] ("get" أو "put") على المفتاح keys[i]، مع القيمة values[i] (0 لعملية get). نفّذها بالترتيب على ذاكرة تخزين مؤقت فارغة، وأعِد سلسلة نصية واحدة لكل عملية: "null" لعملية put، والقيمة أو "-1" لعملية get.
الدالة
- capacityinteger
- أكبر عدد من المفاتيح التي يمكن أن تحتفظ بها ذاكرة التخزين المؤقت في الوقت نفسه
- opsstring-array
- العمليات، بالترتيب الذي تُنفَّذ به
- keysinteger-array
- المفتاح الذي تعمل عليه كل عملية
- valuesinteger-array
- القيمة لكل عملية وضع، و0 لكل عملية جلب
- تُرجعstring-array
- إجابة واحدة لكل عملية، كنص
القيود
1 ≤ capacity ≤ 30001 ≤ ops.length ≤ 3000keys.length == values.length == ops.length- كل
ops[i]إماgetأوput. 0 ≤ keys[i] ≤ 1090 ≤ values[i] ≤ 109لعملية الإضافة، وvalues[i] == 0لعملية الاسترجاع.
أمثلة
- المدخلات
- 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) لكل عملية؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لإزالة المفتاح الصحيح، تحتاج إلى معرفة الترتيب الذي استُخدمت به المفاتيح آخر مرة. ما البنية التي تحفظ ترتيبًا وتتيح لك نقل أي عنصر إلى المقدمة، أو إزالة عنصر من المؤخرة، دون تحريك العناصر الأخرى؟
تفصل القائمة المرتبطة المزدوجة عقدةً، أو تُدرج عقدةً في المقدمة، بتغيير أربع روابط، ولكن فقط بعد أن تصبح العقدة بحوزتك. وتمنحك خريطة تجزئة من كل مفتاح إلى عقدته تلك العقدة في O(1).
أبقِ العقدة الأكثر استخدامًا مؤخرًا في المقدمة، والأقل استخدامًا مؤخرًا في الخلف. عند نجاح عملية get أو عند أي عملية put، انقل العقدة إلى المقدمة. عندما يصل مفتاح جديد وتكون ذاكرة التخزين المؤقت ممتلئة، أزل العقدة الخلفية من القائمة ومفتاحها من الخريطة. تُغنيك عقدتا الحراسة عند الطرفين عن كل فحص للقائمة الفارغة.
الحل
يجب أن يعثر طلب 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جدول تجزئة بالإضافة إلى قائمة مترابطة مزدوجة
الفكرة
ترتبط كل عقدة في القائمة بالعقدتين المجاورتين لها، لذا يمكنك، بمجرد أن تكون العقدة بين يديك، فصلها عن القائمة أو إدراجها في المقدمة بتغيير أربع روابط. تعطيك الخريطة العقدة، لذا لا تتطلب أي عملية اجتياز القائمة.
عند العثور على مفتاح باستخدام get، أو عند تنفيذ put لمفتاح مخزّن مؤقتًا، تنتقل العقدة إلى المقدمة. إذا أُضيف مفتاح جديد إلى ذاكرة تخزين مؤقت ممتلئة، تُزال العقدة الخلفية ويُحذف مفتاحها من الخريطة، ولهذا تخزّن كل عقدة مفتاحها الخاص. تبقى العقدتان الحارستان 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
أخطاء شائعة وحالات حدّية
- عدم نقل المفتاح إلى المقدمة عند العثور عليه في عملية get. في المثال الأول، ستُخرج
put 3المفتاح 1 بدلًا من المفتاح 2. - الإخلاء قبل التحقق مما إذا كان المفتاح مخزّنًا مؤقتًا. بسعة 2، ستُخرج العمليات
put 1وput 2وput 2المفتاح 1. - فصل عقدة مع الإبقاء على مفتاحها في الخريطة، أو العكس. عندها تُرجع الخريطة عقدة مفصولة، ويؤدي نقلها إلى إفساد الروابط مع جيرانها السابقين.
- اعتبار القيمة 0 المخزّنة إخفاقًا في العثور على العنصر. في المثال الثالث، يجب أن تُرجع
get 0القيمة"0".
أسئلة شائعة3
ما هو التعقيد الزمني لذاكرة التخزين المؤقت LRU؟
باستخدام خريطة تجزئة وقائمة مترابطة مزدوجة، تعمل عمليتا get وput في زمن 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"]