3

I am trying to implement a data structure which allows rapid look-ups based on keys.

The python dict is great when my look-ups involve an equality
(e.g. key == somevalue translates to datadict[somevalue].

The problem is that I also need to be able to efficiently look up keys based on a more complex comparison, e.g. key > 50, or key.startswith('abc').

Obviously I can't use the same solution in both cases, but at the moment I can't figure out how to solve either case. Can anyone suggest a way of doing this?

TheCodeArtist
  • 21,479
  • 4
  • 69
  • 130
aquavitae
  • 17,414
  • 11
  • 63
  • 106

2 Answers2

4

It doesn't sound like you want a hash algorithm - instead some form of binary tree. Or even a list which you use the bisect module with. It'd be worth looking at: Python's standard library - is there a module for balanced binary tree?

Another option (depending on your data), would be to use use an in-memory sqlite3 database and create appropriate indices for possible lookups -- but you'll trade performance/memory and SQL syntax for flexibility...

Community
  • 1
  • 1
Jon Clements
  • 138,671
  • 33
  • 247
  • 280
  • Yes, that's exactly what I want! sqite3 has way to much overhead for what I need, but `bisect`, coupled with a binary search tree should do the trick. – aquavitae Nov 28 '12 at 13:18
3
  • Put all data items in a list.
  • Sort the list on the key.
  • Use binary search to efficiently find items where key > 50 or where key.startswith('abc').

Of course, this only pays off if you have really very many data items. If you have not so many, simply loop through the list and apply your condition to every key.

Sjoerd
  • 74,049
  • 16
  • 131
  • 175
  • I have many items, and lots of insertions and queries happening in rapid succession, so sorting the list every time is not really an option. Good suggestion though! – aquavitae Nov 28 '12 at 13:19