<div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">On Tue, Dec 10, 2013 at 4:02 PM, Tamer Higazi <span dir="ltr"><<a href="mailto:tameritoke2@arcor.de" target="_blank">tameritoke2@arcor.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi people!<br>
<br>
Is there a way to get dict by search terms without iterating the entire dictionary ?!<br>
<br>
Let us assume I have:<br>
<br>
{'Amanda':'Power','Amaly':'<u></u>Higgens','Joseph':'White','<u></u>Arlington','Black','Arnold','<u></u>Schwarzenegger'}<br>
<br>
I want to grab the dict's key and values started with 'Ar'...<br>
<br>
I could make an iterator and look if it's inside.<br>
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.<br>
<br>
Why do I ask you?! I am working with the ZODB Database, where I make use of a PersistentDict and PersistentList, and I want<br>
<br>
<br>
I would thank you for a short reply.<span class=""><font color="#888888"><br></font></span></blockquote><div><br></div><div>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.<br>
<br>I can tell you right now though, that the following two implementations aren't quite all the way there for this task:<br><a href="https://pypi.python.org/pypi/treap">https://pypi.python.org/pypi/treap</a><br></div>
</div><a href="https://pypi.python.org/pypi/red-black-tree-mod">https://pypi.python.org/pypi/red-black-tree-mod</a><br><br></div><div class="gmail_extra">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.<br>
<br>I believe you want something with both successor and prefix search.<br><br></div><div class="gmail_extra">And if you want to work on adding this to either of the aforementioned modules, I'm interested in merging your patch.  ^_^<br>
<br></div><div class="gmail_extra">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.<br><br></div><div class="gmail_extra">
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.<br>
<br></div></div>