Python data structure design

Question

The data structure should meet the following purpose:

• each object is unique with certain key-value pairs
• the keys and values are not predetermined and can contain any string value
• querying for objects should be fast

Example:

• object_123({'stupid':True, 'foo':'bar', ...})
• structure.get({'stupid':True, 'foo':'bar', ...}) should return object_123

Optimally this structure is implemented with the standard python data structures available through the standard library.

How would you implement this?

Answer 1

Say object_123 is a dict, which it pretty much looks like. Your structure seems to be a standard dict with keys like (('foo', 'bar'), ('stupid', True)); in other words, tuple(sorted(object_123.items())) so that they're always listed in a defined order.

The reason for the defined ordering is because dict.items() isn't guaranteed to return a list in a given ordering. If your dictionary key is (('foo', 'bar'), ('stupid', True)), you don't want a false negative just because you're searching for (('stupid', True),('foo', 'bar')). Sorting the values is probably the quickest way to protect against that.

Answer 2

The simplest solution I can think of is to use sorted tuple keys:

def key(d): return tuple(sorted(d.items()))

x = {}
x[key({'stupid':True, 'foo':'bar', ...})] = object_123

x.get(key({'stupid':True, 'foo':'bar', ...})) => object_123

Another option would be to come up with your own hashing scheme for your keys (either by wrapping them in a class or just using numeric keys in the dictionary), but depending on your access pattern this may be slower.

Answer 3

I think SQLite or is what you need. It may not be implemented with standard python structures but it's available through the standard library.