Path: csiph.com!usenet.pasdenom.info!dedibox.gegeweb.org!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!nerim.net!novso.com!news2.euro.net!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.050 X-Spam-Evidence: '*H*': 0.92; '*S*': 0.02; 'algorithm': 0.03; 'true,': 0.04; 'cpython': 0.05; 'subject:file': 0.07; 'dict': 0.09; 'lookup': 0.09; 'cc:addr:python-list': 0.10; 'datasets.': 0.16; 'dictionaries': 0.16; 'efficiency.': 0.16; 'entries,': 0.16; 'entry.': 0.16; 'wrote:': 0.17; 'cc:2**0': 0.23; 'cc:no real name:2**0': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply- To:1': 0.25; 'header:User-Agent:1': 0.26; 'common': 0.26; 'andrew': 0.27; 'entries': 0.27; 'dictionary': 0.29; 'hash': 0.29; 'sensible': 0.29; "i'm": 0.29; 'becomes': 0.30; 'function': 0.30; 'cases,': 0.33; 'wrong': 0.34; 'pm,': 0.35; 'table': 0.35; 'but': 0.36; 'too': 0.36; 'uses': 0.37; 'why': 0.37; 'subject:: ': 0.38; 'received:192': 0.39; 'where': 0.40; 'received:192.168': 0.40; 'header:Reply-To:1': 0.68; 'received:74.208': 0.71; 'reply-to:no real name:2**0': 0.72; 'topic,': 0.78; 'actually,': 0.84; 'collision': 0.84; 'difference.': 0.84; 'different.': 0.84; 'glad': 0.86; 'increases': 0.91; 'sensibly': 0.91; 'suffer': 0.91; 'poorly': 0.93; 'hundred': 0.95 Date: Thu, 09 Aug 2012 18:26:53 -0400 From: Dave Angel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120714 Thunderbird/14.0 MIME-Version: 1.0 To: Andrew Cooper Subject: Re: save dictionary to a file without brackets. References: <930ab3d8-4ab9-446d-9970-ee811eb70a44@googlegroups.com> <50241F14.2060209@tim.thechases.com> <36EA3847-6713-4C12-B47B-9B5E10325F00@gmail.com> <502429C3.5000600@tim.thechases.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Provags-ID: V02:K0:b3iEO4UyjMOx+RgOOLzy8vkpYWPH5+xmD3RDWLKGqai bIhlp/JdSCC8yodqUnz9m2nG9cCCrGDFccPbCGQOPsCGTocODY c21PMYaxSvdn/VRYZgM7/8FKd1gw7rDQv0RIxgk7Bth/xdW3Cp F465bbTL8KPJ79abhaS7EqDj8dXs1nik8B6IHxUWVm1f9I1aL6 42NnWt84643aB8PwaHSkbovHymGG8icuI+Pd5ebcQKy51u82Tu 46/if0dy4JANoVC+jhxQZgx/yN6orCc4V371UrVaLzIXmYGh7t gXFp/5+TOoWDN+T/lZdeM7rkAxxSGH/Nz+9xD0KosK3A0blyg= = Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: d@davea.name 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: 27 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1344551238 news.xs4all.nl 6852 [2001:888:2000:d::a6]:48143 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:26825 On 08/09/2012 06:03 PM, Andrew Cooper wrote: > On 09/08/2012 22:34, Roman Vashkevich wrote: >> Actually, they are different. >> Put a dict.{iter}items() in an O(k^N) algorithm and make it a hundred thousand entries, and you will feel the difference. >> Dict uses hashing to get a value from the dict and this is why it's O(1). >> > Sligtly off topic, but looking up a value in a dictionary is actually > O(n) for all other entries in the dict which suffer a hash collision > with the searched entry. > > True, a sensible choice of hash function will reduce n to 1 in common > cases, but it becomes an important consideration for larger datasets. > > ~Andrew I'm glad you're wrong for CPython's dictionaries. The only time the lookup would degenerate to O[n] would be if the hash table had only one slot. CPython sensibly increases the hash table size when it becomes too small for efficiency. Where have you seen dictionaries so poorly implemented? -- DaveA