title: What is the best datastructure for a small and simple cache
body: <p>I often need relatively small (&lt;10000 entries &lt;1kb) caches for speeding up calculations. My usual code looks like this:</p>
  
  <pre><code>cache = {}
  def calculate_caches(parms):
      if parms not in cache:
          cache[parms] = calculate(parms)
      return cache[parms]
  </code></pre>
  
  <p>Works fine but for longer running processes I'm afraid of memory leaks. So I often implement brute force memory clamping like this:</p>
  
  <pre><code>if len(cache) &gt; 1000:
      cache = {}
  </code></pre>
  
  <p>Works reasonably well in most cases and still is clean, simple code. But If I want a real <a href="http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used" rel="nofollow noreferrer">LRU strategy</a> I need timestamps together with the cache entry. The problem of using a dict for this is, that expiring the cache now means traversing the whole cache which is neither elegant nor efficient.</p>
  
  <pre><code>cache = {}
  def calculate_caches(parms):
      if parms not in cache:
          cache[parms] = (time.time(), calculate(parms))
      expire()
      return cache[parms][1]
  
  def expire()
      if len(cache) &gt; 1000:
          mintime = time.time()
          time2key = {}
          for key, (timestamp, val) in cache.items():
              mintime = min([mintime, timestamp])
              time2key[timestamp] = key
          if mintime in time2key:
              del cache[time2key[mintime]]
  </code></pre>
  
  <p>Are there preferable approaches / datastructures to implement ad-hoc caching?</p>
  
  <p>My problem is quite similar to <a href="https://stackoverflow.com/questions/1072847/looking-for-datastructure-that-maintains-a-size-purges-older-elements-in-the-pr">this question</a> but I don't need the list to be sorted by time and I don't want dupes.</p>