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?

@phooji: No. I just couldn't think of any could clean and good implementation of this and was looking for expert advice. — xyz-123
– xyz-123, Commented Apr 6, 2011 at 19:47
@phooji: I wondered that, too, but his other questions seem legit. — Kirk Strauser
– Kirk Strauser, Commented Apr 6, 2011 at 19:48
Are the objects mutable? Can object_123 get new keys or changed values or both? — S.Lott
– S.Lott, Commented Apr 6, 2011 at 19:49
@S.Lott: in this specific case they are immutable, but it would be interesting, how this is implemented with mutable objects? — xyz-123
– xyz-123, Commented Apr 6, 2011 at 19:52

Nicholas Riley · Accepted Answer · 2011-04-06 19:46:27Z

6

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.

answered Apr 6, 2011 at 19:46

Nicholas Riley

44.5k6 gold badges107 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ncoghlan Over a year ago

+1, although part of me is wondering if there is a way that namedtuple might help...

Håvard · Accepted Answer · 2011-04-06 19:45:25Z

0

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.

answered Apr 6, 2011 at 19:45

Håvard

10.1k1 gold badge43 silver badges46 bronze badges

Comments

Kirk Strauser · Accepted Answer · 2011-04-06 19:53:06Z

0

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.

edited Apr 6, 2011 at 19:53

answered Apr 6, 2011 at 19:46

Kirk Strauser

31.1k5 gold badges53 silver badges69 bronze badges

Collectives™ on Stack Overflow

Python data structure design

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related