Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.003 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'python.': 0.02; 'algorithm': 0.04; 'string': 0.09; 'key.': 0.09; 'lookup': 0.09; 'subject:keys': 0.09; 'subset': 0.09; 'cc:addr:python-list': 0.11; 'python': 0.11; '-tkc': 0.16; 'dict': 0.16; 'from:addr:python.list': 0.16; 'from:addr:tim.thechases.com': 0.16; 'from:name:tim chase': 0.16; 'iterates': 0.16; 'iteration': 0.16; 'prefix,': 0.16; 'roy': 0.16; 'subject:values': 0.16; 'throw': 0.16; 'wrote:': 0.18; 'differ': 0.19; 'code,': 0.22; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'subject:/': 0.26; 'header:In-Reply-To:1': 0.27; "doesn't": 0.30; 'asked': 0.31; 'allows': 0.31; 'probably': 0.32; 'run': 0.32; 'level.': 0.33; 'sense': 0.34; 'skip:d 20': 0.34; 'could': 0.34; 'problem': 0.35; 'done': 0.36; 'charset:us-ascii': 0.36; 'skip:o 20': 0.38; 'that,': 0.38; 'structure': 0.39; 'full': 0.61; "you're": 0.61; "you've": 0.63; 'term': 0.63; 'skip:n 10': 0.64; 'more': 0.64; 'specialized': 0.65; 'details': 0.65; 'believe': 0.68; 'smith': 0.68; 'special': 0.74; 'faster.': 0.84; 'received:50.22': 0.84; 'results,': 0.84 Date: Wed, 11 Dec 2013 09:42:53 -0600 From: Tim Chase To: Roy Smith Subject: Re: grab dict keys/values without iterating ?! In-Reply-To: References: <52A7AB8C.8030700@arcor.de> <52A7AB8C.8030700@arcor.de> <3efc283f-419d-41b6-ad20-c2901c3b9f78@googlegroups.com> X-Mailer: Claws Mail 3.8.1 (GTK+ 2.24.10; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - boston.accountservergroup.com X-AntiAbuse: Original Domain - python.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tim.thechases.com X-Get-Message-Sender-Via: boston.accountservergroup.com: authenticated_id: tim@thechases.com Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 26 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1386776501 news.xs4all.nl 2871 [2001:888:2000:d::a6]:53998 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:61585 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