Regular expression as dictionary key?

[Luke]

Daniel Yoo wrote:

> Luke <LLoeffler at home.com> wrote:
> : Let's say you have a dict of words like
> : words = {"dogs":1,"cats":2}
> 
> : Let's say I'm given a singular form of a word and want to match it with 
> : plurals still, but words["dog"] will obviously raise a KeyError.
> 
> : Without doing a linear substring search on every element in words.key(), 
> : is there a way to take advantage of the dict's binary tree layout 
> : properties (e.g. speed) like:
> 
> : words["dog*"]   # where dog* is a Regex
> 
> : Nonexistant syntax, I know, but you get the idea...  I smell a PEP
> 
> Hmmm... Interesting!  Let's see:
--snip--

Cool, but still a linear search.  Plus it short circuits.

What about this case:
words = {"dogs":32,"donuts":41}
words["do*"] should return [32,41]

So you add a few lines to go exhaustively through the keys and 
accumulate matches... Still linear.  I admitedly don't know much about 
the C implementation of dicts, but it seems there should be a way to 
leverage the dict's arrangement for fast regex keys.

Luke