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 operat
"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)).
--
http://m
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 const
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, an
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 somethin
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
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 image
>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 self
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.
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 f
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 y
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 li
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
13 matches
Mail list logo
