LRU cache?

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • Paul Rubin
    #1

    LRU cache?

    Anyone got a favorite LRU cache implementation? I see a few in google
    but none look all that good. I just want a dictionary indexed by
    strings, that remembers the last few thousand entries I put in it.

    It actually looks like this is almost a FAQ. A well-written
    implementation would probably make a good standard library module.
    Tags: None
    • Thomas Wittek
      #2
      Re: LRU cache?

      Paul Rubin schrieb:
      Anyone got a favorite LRU cache implementation? I see a few in google
      but none look all that good. I just want a dictionary indexed by
      strings, that remembers the last few thousand entries I put in it.
      I don't know a module for that (although it might exist), but I could
      imagine how to implement it.

      Generally a LRU cache could be implemented as a (linked) list with a
      max. size of N.
      On usage of an object this object will be moved to the top of the list
      (and removed from the old position).
      If it's not yet stored in the cache, you (fetch it from the source and)
      add it on top and remove the last one, if the list exceeds N entries.

      So you need to do two things:
      1) Maintain a list: Use a (linked) list.
      2) Random access to that list: Use a dict (hash), that also has to be
      updated on removal/addition of objects.

      --
      Thomas Wittek
      Web: http://gedankenkonstrukt.de/
      Jabber: streawkceur@jab ber.i-pobox.net
      GPG: 0xF534E231

        Comment

        • Steve Holden
          #3
          Re: LRU cache?

          Thomas Wittek wrote:
          Paul Rubin schrieb:
          >Anyone got a favorite LRU cache implementation? I see a few in google
          >but none look all that good. I just want a dictionary indexed by
          >strings, that remembers the last few thousand entries I put in it.
          >
          I don't know a module for that (although it might exist), but I could
          imagine how to implement it.
          >
          Generally a LRU cache could be implemented as a (linked) list with a
          max. size of N.
          On usage of an object this object will be moved to the top of the list
          (and removed from the old position).
          If it's not yet stored in the cache, you (fetch it from the source and)
          add it on top and remove the last one, if the list exceeds N entries.
          >
          So you need to do two things:
          1) Maintain a list: Use a (linked) list.
          2) Random access to that list: Use a dict (hash), that also has to be
          updated on removal/addition of objects.
          >
          Paul's an old enough hand that he's well able to determine this for
          himself. He's also polite enough not to reply along those lines :-)

          *I* don't know of module for tracking how plants grow, but I could
          imagine how to implement it ...

          regards
          Steve
          --
          Steve Holden +1 571 484 6266 +1 800 494 3119
          Holden Web LLC/Ltd http://www.holdenweb.com
          Skype: holdenweb http://del.icio.us/steve.holden
          --------------- Asciimercial ------------------
          Get on the web: Blog, lens and tag the Internet
          Many services currently offer free registration
          ----------- Thank You for Reading -------------

            Comment

            • Alex Martelli
              #4
              Re: LRU cache?

              Paul Rubin <http://phr.cx@NOSPAM.i nvalidwrote:
              Anyone got a favorite LRU cache implementation? I see a few in google
              but none look all that good. I just want a dictionary indexed by
              strings, that remembers the last few thousand entries I put in it.
              So what's wrong with Evan Prodromou's lrucache.py module that's in pypi?
              Haven't used it, but can't see anything wrong at a glance.


              Alex

                Comment

                • Nikita the Spider
                  #5
                  Re: LRU cache?

                  In article <7x8x8ixomj.fsf _-_@ruckus.brouha ha.com>,
                  Paul Rubin <http://phr.cx@NOSPAM.i nvalidwrote:
                  Anyone got a favorite LRU cache implementation? I see a few in google
                  but none look all that good. I just want a dictionary indexed by
                  strings, that remembers the last few thousand entries I put in it.
                  >
                  It actually looks like this is almost a FAQ. A well-written
                  implementation would probably make a good standard library module.
                  This one works for me:
                  http://www.webfast.com/~skip/python/Cache.py


                  --
                  Philip
                  Nikita the Spider
                  http://NikitaTheSpider.com/
                  The ultimate life protection

                  Whole-site HTML validation, link checking and more

                    Comment

                    • Paul Rubin
                      #6
                      Re: LRU cache?

                      Nikita the Spider <NikitaTheSpide r@gmail.comwrit es:
                      This one works for me:
                      http://www.webfast.com/~skip/python/Cache.py
                      Thanks, this one keeps track of the actual clock time rather than just
                      the relative age of cache entries, and has kind of a weird ageing
                      mechanism, building and sorting an O(n) sized list when the cache gets
                      95% full, giving amortized O(log n) operations per update. But the
                      license is ok and I guess the functionality I need is there. So I may
                      use it and/or code something.

                        Comment

                        Previous template Next
                        Working...