grab dict keys/values without iterating ?!

[Dan Stromberg]

On Tue, Dec 10, 2013 at 4:02 PM, Tamer Higazi <tameritoke2 at arcor.de> wrote:

> Hi people!
>
> Is there a way to get dict by search terms without iterating the entire
> dictionary ?!
>
> Let us assume I have:
>
> {'Amanda':'Power','Amaly':'Higgens','Joseph':'White','
> Arlington','Black','Arnold','Schwarzenegger'}
>
> I want to grab the dict's key and values started with 'Ar'...
>
> I could make an iterator and look if it's inside.
> I wasn't able to find it, but I am asking myself if dict has a builtin
> method to get me these key/values on the fly.
>
> Why do I ask you?! I am working with the ZODB Database, where I make use
> of a PersistentDict and PersistentList, and I want
>
>
> I would thank you for a short reply.
>

A treap or red-black tree could be made to do this in O(logn) time.  They
can be made to look like dictionaries, but they keep things ordered by key
every step of the way.

I can tell you right now though, that the following two implementations
aren't quite all the way there for this task:
https://pypi.python.org/pypi/treap
https://pypi.python.org/pypi/red-black-tree-mod

The treap implementation doesn't have a successor method and won't do a
prefix search out of the box.  The red-black tree implementation has a
successor method, but won't do a prefix search out of the box.

I believe you want something with both successor and prefix search.

And if you want to work on adding this to either of the aforementioned
modules, I'm interested in merging your patch.  ^_^

There may be other implementations that'll do this already; I don't know
about that.  Other things that may help are BTrees and things of that ilk.

Finally, if your dictionaries aren't very big, you might find it easier to
just get a list of keys and do a binary search on them.  It's O(n)
(assuming you do it only once - doing it in a loop would be expensive), but
sometimes that's not a problem.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20131211/48a8ecfa/attachment.html>