Changeset 1011:566222014b88


Ignore:
Timestamp:
Jan 2, 2011, 6:25:45 PM (11 years ago)
Author:
Stefan Schwarzer <sschwarzer@…>
Branch:
default
Message:
Reduced calls to `heapify`, making many operations much faster.

The former implementation maintained the heap queue ordering invariant
as much as possible. While that made for a clear implementation it
slowed down getting values from large caches significantly.

The change only calls `heapify` before operations which rely on the
heap queue ordering. In some situations this makes the code using the
cache ten times faster.

All the unit tests distributed with the lrucache module still pass.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lrucache.py

    r1010 r1011  
    22
    33# Copyright 2004 Evan Prodromou <evan@bad.dynu.ca>
     4# Copyright 2009-2011 Stefan Schwarzer <sschwarzer@sschwarzer.net>
     5#  (some changes to the original version)
     6
    47# Licensed under the Academic Free License 2.1
    58
     
    4144from __future__ import generators
    4245import time
    43 from heapq import heappush, heappop, heapify
     46from heapq import heappop, heapify
    4447
    4548# the suffix after the hyphen denotes modifications by the
    4649#  ftputil project with respect to the original version
    47 __version__ = "0.2-5"
     50__version__ = "0.2-6"
    4851__all__ = ['CacheKeyError', 'LRUCache', 'DEFAULT_SIZE']
    4952__docformat__ = 'reStructuredText en'
     
    140143        The `size` attribute of the cache isn't modified.
    141144        """
     145        # pylint: disable=W0201
    142146        self.__heap = []
    143147        self.__dict = {}
     
    170174            node.mtime = node.atime
    171175            node._sort_key = self._sort_key()
    172             heapify(self.__heap)
    173176        else:
    174177            # size of the heap can be at most the value of
     
    177180            #  need a loop _here_
    178181            if len(self.__heap) == self.size:
     182                heapify(self.__heap)
    179183                lru = heappop(self.__heap)
    180184                del self.__dict[lru.key]
    181185            node = self.__Node(key, obj, time.time(), self._sort_key())
    182186            self.__dict[key] = node
    183             heappush(self.__heap, node)
     187            self.__heap.append(node)
    184188
    185189    def __getitem__(self, key):
     
    191195            node.atime = time.time()
    192196            node._sort_key = self._sort_key()
    193             heapify(self.__heap)
    194197            return node.obj
    195198
     
    201204            del self.__dict[key]
    202205            self.__heap.remove(node)
    203             heapify(self.__heap)
    204206            return node.obj
    205207
    206208    def __iter__(self):
     209        heapify(self.__heap)
    207210        copy = self.__heap[:]
    208211        while len(copy) > 0:
     
    220223            if size <= 0:
    221224                raise ValueError("cache size (%d) must be positive" % size)
     225            heapify(self.__heap)
    222226            while len(self.__heap) > value:
    223227                lru = heappop(self.__heap)
Note: See TracChangeset for help on using the changeset viewer.