I've implemented such an LRU Cache in Python. My technique was to
weave a doubly-linked list into the dict, so that it is O(dict) for all
LRU operations. I benchmarked it against someone's Python-list-based
implementation from the ActiveState cookbook and noted that on my
machine the better
zooko [EMAIL PROTECTED] writes:
I haven't benchmarked it against Evan Podromou's heap implementation
yet, but obviously inserting and removing things from a heapq heap is
O(N).
Good heavens, I should hope not. The whole point of heaps is that
those operations are O(log(N)).
--
Paul Rubin wrote:
zooko [EMAIL PROTECTED] writes:
I haven't benchmarked it against Evan Podromou's heap implementation
yet, but obviously inserting and removing things from a heapq heap is
O(N).
Good heavens, I should hope not. The whole point of heaps is that
those operations are
LRU caches are nice and simple, but if you want something fancier, with
support for squid-like expiry models (ie, using mtime and atime to
estimate a stale time, and IMS fetches), you can have a look at my
GCache;
http://minkirri.apana.org.au/~abo/projects/GCache
Even if you don't want something
Actually, after posting this I did some more work on the PQueue modules
I had, implementing both bisect and heapq versions. It turns out the
bisect version is heaps faster if you ever delete or re-set values in
the queue.
The problem is heapq is O(N) for finding a particular entry in the
Queue,
Laszlo Zsolt Nagy wrote:
Hello,
Do you know how to implement a really efficient self reordering list in
Python? (List with a maximum length. When an item is processed, it
becomes the first element in the list.) I would like to use this for
caching of rendered images.
I wonder why you don't
I wonder why you don't use a dictionary? The only time I used a
move-front algorithm I stored algorithms and had to evaluate a
condition to select the correct algo. That means no constant search key
was available for accessing the correct one. In case of an image list I
would implement a
On Friday 16 September 2005 06:03 am, Laszlo Zsolt Nagy wrote:
You are right in that holding a reference will have a better time
complexity. But holding a reference makes it impossible to free the
object. :-) As I said, my list has a maximum length. I just can't store
any number of images
Terry Hancock wrote:
This is actually the use-case for an LRU cache=least recently used
cache, which is probably already implemented in Python somewhere (or
even as a fast extension). I'd do a google search for it.
reposted, in case there are more people who cannot be bothered
to read other
Hello,
Do you know how to implement a really efficient self reordering list in
Python? (List with a maximum length. When an item is processed, it
becomes the first element in the list.) I would like to use this for
caching of rendered images. Of course I could implement this in pure
Python
Am Thu, 15 Sep 2005 15:14:09 +0200 schrieb Laszlo Zsolt Nagy:
Hello,
Do you know how to implement a really efficient self reordering list in
Python? (List with a maximum length. When an item is processed, it
becomes the first element in the list.) I would like to use
Laszlo Zsolt Nagy wrote:
Do you know how to implement a really efficient self reordering list in
Python? (List with a maximum length. When an item is processed, it
becomes the first element in the list.) I would like to use this for
caching of rendered images.
did you check the cheeseshop
On Thursday 15 September 2005 07:14, Laszlo Zsolt Nagy
[EMAIL PROTECTED]
([EMAIL PROTECTED]) wrote:
Do you know how to implement a really efficient self reordering list in
Python?
Yes.
(List with a maximum length. When an item is processed, it
becomes the first element in the list
13 matches
Mail list logo
