Take the 2-minute tour ×
Ask Ubuntu is a question and answer site for Ubuntu users and developers. It's 100% free, no registration required.

I am creating a subclass of shelve allowing for searching for partial keys (e.g., key begins with substring, or key ends with substring), and the way that seems most intuitive is to use the db.keys() method, to get a list of keys, and the iterate through them testing for the partial key.

I am doing this to have a searchable multi-language dictionary within a program which returns multiple matching/related words for each word (I currently implement this by returning a list of values for a single key).

Because I intend to use this subclass and its database to hold large amounts of keys as a language dictionary, I believe this approach will be slow (relatively that is. I would like for no lag to be experienced) when iterating keys in numbers possibly exceeding hundreds of thousands.

To account for this slowness and waste of computation in iterating over the entire dictionary, I would want to have an easy way to only look at keys which have the possibility of having a matching key.

I know python has filter, but it would seem like when calling this filter it would have to iterate over the list to find which items match the filter, and I might as well do my iteration if that is the case.

Does anyone have any ideas?

I am thinking I could return sorted(db.keys) and make a "key" to hold the ranges of each word beginning with a respective letter (i.e., the letter "a" begins lines 0 through 56), and iterate over that range, so I could focus in that way, but this would only be useful when searching for keys beginning with a certain substring, and not for searching for keys ending with one or containing one.

I am using shelve because it can store lists as a value, but I am open to using any other type of data structure which supports this, if anyone knows of an alternate method to do this which would be more effective.

Thanks!

share|improve this question
    
As this programming question is not Ubuntu-specific in any way, it is probably off-topic for Ask Ubuntu. It would, however, be on-topic on Stack Overflow. –  Eliah Kagan Aug 5 '12 at 4:21
add comment

closed as off topic by Eliah Kagan, Jorge Castro, ajmitch, Martin Owens -doctormo-, izx Aug 18 '12 at 6:57

Questions on Ask Ubuntu are expected to relate to Ubuntu within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 0 down vote accepted

When you work with hundreds of thousands of key value pairs and you want to do complicated lookups, it is probably not advisable to use shelve and normal python structures with iteration.

If you have to use python and shelve, I would suggest a tree like structure of "keys". So that when searching for the substring "asku" you could walk the tree "a" -> "s" -> "k" -> "u". And return everything that is under this node recursively, e.g. "askubuntu".

However, what you describe is a typical use case for actual databases. Many programmers before you wanted to solve the exact same problem and have come up with efficient search algorithms, data structures and so on and put them in tools like postgresql, mysql, Nosql, etc.

share|improve this answer
    
Among postgresql, mysql, Nosql, and others, do you have experience using any of these? Which would you suggest for this project. –  Jobi Carter Aug 5 '12 at 17:37
    
how well a database fits depends on many things. you could start with the wikipedia comparison: en.wikipedia.org/wiki/…. I always suggest free software, so e.g. sqlite, mysql, postgresql would be a good start. –  xubuntix Aug 6 '12 at 6:14
    
Alright, thanks. I think for now I am going to tinker around with sqlite3, as it comes standard with python. Thanks! –  Jobi Carter Aug 6 '12 at 17:27
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.