title: Balance between dictionary size and memory consumption
body: <p>I'm using a <a href="http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize" rel="nofollow"><code>memoized</code> decorator</a> to cache repeated calls. I'm seeing about a 4x execution speedup due to memoization on some moderate-sized test cases.</p>
  
  <p>With larger test cases, the memoized dictionary mapping inputs to outputs takes up a considerable amount of memory, to the point where I'm getting <code>"java.lang.OutOfMemoryError: Java heap space"</code> errors (I'm using Jython).</p>
  
  <p>I can save some memory by using <code>memoized_cache[hash(key)] = value</code> rather than <code>memoized_cache[key]: value</code>, assuming that <code>hash(key)</code> is fewer bytes than <code>key</code>. As pointed out by @gnibbler, this will cause problems if there are hash collisions.</p>
  
  <p>The other memory savings I can introduce is limiting the size of the dictionary to a fixed number of items. Such a <a href="https://code.activestate.com/recipes/496842-sized-dictionary/?c=15571" rel="nofollow">SizedDict recipe</a> already exists, but I'd like to truncate elements that are accessed the least often.</p>
  
  <p>Here's what I have written:</p>
  
  <pre><code>from collections import Counter
  
  class FrequencySizedDict(dict):
      def __init__(self, size=1000):
          dict.__init__(self)
          self._maxsize = size
          self._counter = Counter()
      def __getitem__(self, key):
          self._counter[key] += 1
          return dict.__getitem__(self, key)
      def resize(self, size):
          keys = list(self._counter.most_common(size))
          items = [(key, dict.__getitem__(self, key)) for key in keys]
          self.clear()
          dict.update(self, items)
      def __setitem__(self, key, value):
          if len(self._queue) &gt;= self._maxsize:
              self.resize(self._maxsize/2)
          self._counter[key] += 1
          dict.__setitem__(self, key, value)
  </code></pre>
  
  <p>Is there a better data way to implement this with less memory or time overhead? <code>resize</code> is quite expensive: <code>O(n log n)</code></p>