Motivation: I have a large number of large read-only dicts with large string keys mapped to tuples of two floats. They are taking up a large amount of heap space.
Proposed solution: a 3xn NumPy array, with the first column being the hash value of the key, and sorted by that column. Only contains and
getitem ops are required for my needs.
I realize that this solution is \$O(log(n))\$ rather than \$O(c)\$ but I assume that this isn't that big a problem for my application as there aren't that many lookups per request and my primary problem is memory constraints.
I'm not sure how well
searchsorted performs here though, or if I should try to change the stride somehow so that the first column is contiguous or something like that. I should also probably be using a record array.
import numpy class FCD(object): def __init__(self, d): data =  for key, value in d.iteritems(): data.append((hash(key), value, value)) data.sort() self.data = numpy.array(data) def __getitem__(self, key): hkey = hash(key) ix = numpy.searchsorted(self.data[:, 0], hkey) if ix < len(self.data) and self.data[ix] == hkey: return self.data[ix][1:] else: raise KeyError def __contains__(self, key): hkey = hash(key) ix = numpy.searchsorted(self.data[:, 0], hkey) return ix < len(self.data) and self.data[ix] == hkey