On 2013-12-11 09:46, Roy Smith wrote: > The problem is, that doesn't make a whole lot of sense in Python. > The cited implementation uses dicts at each level. By the time > you've done that, you might as well just throw all the data into > one big dict and use the full search string as the key. It would > be a lot less code, and probably run faster.
You're right if the search term is a whole word, a single dict-to-result works ideally. However, the OP asked about prefixes, so the Python implementation I provided uses a dict-of-nested-dicts which allows any arbitrary prefix, and then iterates over only the subset of those that match. If you need O(length-of-prefix) iteration of all results, I believe that's the best way algorithm to use (implementation details could differ for a more space-efficient structure perhaps; normalization might help reduce dict-entries). It's a specialized use-case, and doesn't have the O(1) lookup for exact-matches (that's just a special case of prefix=word with no sub-iteration, so would be O(length-of-search-word)). -tkc -- https://mail.python.org/mailman/listinfo/python-list
