Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #26943
| From | 88888 Dihedral <dihedral88888@googlemail.com> |
|---|---|
| Newsgroups | comp.lang.python |
| Subject | Re: save dictionary to a file without brackets. |
| Date | 2012-08-12 04:59 -0700 |
| Organization | http://groups.google.com |
| Message-ID | <a5bede18-ffa7-47d4-93c4-cd9d04d6587f@googlegroups.com> (permalink) |
| References | (5 earlier) <mailman.3120.1344548050.4697.python-list@python.org> <MsWUr.1183213$%k.489563@fx20.am4> <5024392D.3010306@davea.name> <mailman.3132.1344552827.4697.python-list@python.org> <5026416d$0$29978$c3e8da3$5496439d@news.astraweb.com> |
Steven D'Aprano於 2012年8月11日星期六UTC+8下午7時26分37秒寫道： > On Fri, 10 Aug 2012 08:53:43 +1000, Chris Angelico wrote: > > > > > On Fri, Aug 10, 2012 at 8:26 AM, Dave Angel <d@davea.name> wrote: > > >> On 08/09/2012 06:03 PM, Andrew Cooper wrote: > > >>> 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. > > >> > > >> 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? > > > > > > In vanilla CPython up to version (I think) 3.3, where it's possible to > > > DoS the hash generator. Hash collisions are always possible, just > > > ridiculously unlikely unless deliberately exploited. > > > > Not so unlikely actually. > > > > py> hash(3) > > 3 > > py> hash(2**64 + 2) > > 3 > > > > py> hash(-1) > > -2 > > py> hash(-2) > > -2 > > > > > > By its very nature, a hash function cannot fail to have collisions. The > > problem is that in general you have an essentially unlimited number of > > objects being mapped to a large but still finite number of hash values. > > > > > > > > -- > > Steven Steven D'Aprano於 2012年8月11日星期六UTC+8下午7時26分37秒寫道： > On Fri, 10 Aug 2012 08:53:43 +1000, Chris Angelico wrote: > > > > > On Fri, Aug 10, 2012 at 8:26 AM, Dave Angel <d@davea.name> wrote: > > >> On 08/09/2012 06:03 PM, Andrew Cooper wrote: > > >>> 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. > > >> > > >> 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? > > > > > > In vanilla CPython up to version (I think) 3.3, where it's possible to > > > DoS the hash generator. Hash collisions are always possible, just > > > ridiculously unlikely unless deliberately exploited. > > > > Not so unlikely actually. > > > > py> hash(3) > > 3 > > py> hash(2**64 + 2) > > 3 > > > > py> hash(-1) > > -2 > > py> hash(-2) > > -2 > > > > > > By its very nature, a hash function cannot fail to have collisions. The > > problem is that in general you have an essentially unlimited number of > > objects being mapped to a large but still finite number of hash values. > > > > > > > > -- > > Steven Lets check the basic operations of a hash table or so-called a dictionary first. If the dictionary is implemented toward faster in searching items, then it is slightly different in the insertion and the deletion operations of (key, value) pairs.
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
save dictionary to a file without brackets. giuseppe.amatulli@gmail.com - 2012-08-09 13:11 -0700
Re: save dictionary to a file without brackets. Roman Vashkevich <vashkevichrb@gmail.com> - 2012-08-10 00:22 +0400
Re: save dictionary to a file without brackets. Tim Chase <python.list@tim.thechases.com> - 2012-08-09 15:35 -0500
Re: save dictionary to a file without brackets. Giuseppe Amatulli <giuseppe.amatulli@gmail.com> - 2012-08-09 15:35 -0500
Re: save dictionary to a file without brackets. Gelonida N <gelonida@gmail.com> - 2012-08-09 22:35 +0200
Re: save dictionary to a file without brackets. Giuseppe Amatulli <giuseppe.amatulli@gmail.com> - 2012-08-09 15:38 -0500
Re: save dictionary to a file without brackets. Roman Vashkevich <vashkevichrb@gmail.com> - 2012-08-10 00:41 +0400
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-09 22:17 +0100
Re: save dictionary to a file without brackets. Tim Chase <python.list@tim.thechases.com> - 2012-08-09 16:21 -0500
Re: save dictionary to a file without brackets. Roman Vashkevich <vashkevichrb@gmail.com> - 2012-08-10 01:34 +0400
Re: save dictionary to a file without brackets. Andrew Cooper <amc96@cam.ac.uk> - 2012-08-09 23:03 +0100
Re: save dictionary to a file without brackets. Dave Angel <d@davea.name> - 2012-08-09 18:26 -0400
Re: save dictionary to a file without brackets. Andrew Cooper <amc96@cam.ac.uk> - 2012-08-09 23:54 +0100
Re: save dictionary to a file without brackets. Roy Smith <roy@panix.com> - 2012-08-09 19:05 -0400
Re: save dictionary to a file without brackets. Chris Angelico <rosuav@gmail.com> - 2012-08-10 09:14 +1000
Re: save dictionary to a file without brackets. Roy Smith <roy@panix.com> - 2012-08-09 19:24 -0400
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-10 00:33 +0100
Re: save dictionary to a file without brackets. Tim Chase <python.list@tim.thechases.com> - 2012-08-09 19:16 -0500
Re: save dictionary to a file without brackets. Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-10 08:54 +0000
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-10 10:37 +0100
Re: save dictionary to a file without brackets. Roy Smith <roy@panix.com> - 2012-08-10 08:29 -0400
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-10 15:47 +0100
Re: save dictionary to a file without brackets. alex23 <wuwei23@gmail.com> - 2012-08-12 17:15 -0700
Re: save dictionary to a file without brackets. Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-13 08:05 +0000
Re: save dictionary to a file without brackets. alex23 <wuwei23@gmail.com> - 2012-08-13 09:16 -0700
Re: save dictionary to a file without brackets. rusi <rustompmody@gmail.com> - 2012-08-13 08:55 -0700
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-13 13:37 +0100
Re: save dictionary to a file without brackets. alex23 <wuwei23@gmail.com> - 2012-08-13 09:14 -0700
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-13 18:07 +0100
Re: save dictionary to a file without brackets. Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-14 02:54 +0000
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-14 12:33 +0100
Re: save dictionary to a file without brackets. Alister <alister.ware@ntlworld.com> - 2012-08-14 15:05 +0000
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-14 19:15 +0100
Re: save dictionary to a file without brackets. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-08-13 18:43 +0100
Re: save dictionary to a file without brackets. alex23 <wuwei23@gmail.com> - 2012-08-13 18:32 -0700
Re: save dictionary to a file without brackets. Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-08-10 12:34 -0400
Re: save dictionary to a file without brackets. Dave Angel <d@davea.name> - 2012-08-09 20:27 -0400
Re: save dictionary to a file without brackets. Chris Angelico <rosuav@gmail.com> - 2012-08-10 10:31 +1000
Re: save dictionary to a file without brackets. Dave Angel <d@davea.name> - 2012-08-09 19:38 -0400
Re: save dictionary to a file without brackets. Tim Chase <python.list@tim.thechases.com> - 2012-08-09 17:39 -0500
Re: save dictionary to a file without brackets. Chris Kaynor <ckaynor@zindagigames.com> - 2012-08-09 15:37 -0700
Re: save dictionary to a file without brackets. Chris Angelico <rosuav@gmail.com> - 2012-08-10 08:53 +1000
Re: save dictionary to a file without brackets. Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-11 11:26 +0000
Re: save dictionary to a file without brackets. 88888 Dihedral <dihedral88888@googlemail.com> - 2012-08-12 04:59 -0700
Re: save dictionary to a file without brackets. Chris Angelico <rosuav@gmail.com> - 2012-08-10 09:01 +1000
Re: save dictionary to a file without brackets. Dave Angel <d@davea.name> - 2012-08-09 19:42 -0400
Re: save dictionary to a file without brackets. 88888 Dihedral <dihedral88888@googlemail.com> - 2012-08-09 22:35 -0700
Re: save dictionary to a file without brackets. Terry Reedy <tjreedy@udel.edu> - 2012-08-09 17:46 -0400
Re: save dictionary to a file without brackets. Dave Angel <d@davea.name> - 2012-08-09 17:47 -0400
Re: save dictionary to a file without brackets. 88888 Dihedral <dihedral88888@googlemail.com> - 2012-08-10 10:46 -0700
Re: save dictionary to a file without brackets. 88888 Dihedral <dihedral88888@googlemail.com> - 2012-08-10 10:46 -0700
Re: save dictionary to a file without brackets. Chris Kaynor <ckaynor@zindagigames.com> - 2012-08-09 14:49 -0700
Re: save dictionary to a file without brackets. Chris Kaynor <ckaynor@zindagigames.com> - 2012-08-09 14:51 -0700
Re: save dictionary to a file without brackets. Giuseppe Amatulli <giuseppe.amatulli@gmail.com> - 2012-08-09 16:53 -0500
Re: save dictionary to a file without brackets. Roman Vashkevich <vashkevichrb@gmail.com> - 2012-08-10 02:02 +0400
csiph-web