From f3b10e11d8253adb2a91318230952354dd77829e Mon Sep 17 00:00:00 2001 From: Jay Hutchinson Date: Tue, 1 Mar 2022 14:44:32 -0600 Subject: Small optimization to popitem(). --- pylru.py | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-) diff --git a/pylru.py b/pylru.py index 842c7bf..6e031a9 100644 --- a/pylru.py +++ b/pylru.py @@ -205,9 +205,27 @@ class lrucache(object): if len(self) < 1: raise KeyError - key = self.head.key - value = self.head.value - del self[key] + # Grab the head node + node = self.head + + # Save the key and value so that we can return them. + key = node.key + value = node.value + + # Remove the key from the hash table and mark the node as empty. + del self.table[key] + node.empty = True + + # Not strictly necessary. + node.key = None + node.value = None + + # Because this node is now empty we want to reuse it before any + # non-empty node. To do that we want to move it to the tail of the + # list. This node is the head node. Due to the list being circular, + # the ordering is already correct, we just need to adjust the 'head' + # variable. + self.head = node.next return key, value -- cgit v1.2.1