Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #16923

Re: order independent hash?

Path csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!newsfeed.CARNet.hr!gregory.BNet.hr!busola.homelinux.net!not-for-mail
From Hrvoje Niksic <hniksic@xemacs.org>
Newsgroups comp.lang.python
Subject Re: order independent hash?
Date Fri, 09 Dec 2011 17:51:06 +0100
Organization B.net Hrvatska d.o.o.
Lines 14
Message-ID <87ty59adtx.fsf@xemacs.org> (permalink)
References <jb57p7$b1j$1@dough.gmane.org> <mailman.3156.1322657239.27778.python-list@python.org> <30715729.411.1322753732534.JavaMail.geo-discussion-forums@pret21> <4ED7A2CE.6070306@davea.name> <mailman.3203.1322756312.27778.python-list@python.org> <6366868.86.1322800180523.JavaMail.geo-discussion-forums@pret21> <mailman.3216.1322802013.27778.python-list@python.org> <87k46fb8pg.fsf@xemacs.org> <mailman.3239.1322862043.27778.python-list@python.org> <87aa78bfvv.fsf@xemacs.org> <CAPTjJmqrYLnhgCCDW3FdjOyqyUttW3cZu-=S1eW30217djgY8Q@mail.gmail.com> <mailman.3277.1323025080.27778.python-list@python.org> <87y5un9zs6.fsf@xemacs.org> <4ee1f093$0$29977$c3e8da3$5496439d@news.astraweb.com>
NNTP-Posting-Host cpezg-94-253-138-239-cbl.xnet.hr
Mime-Version 1.0
Content-Type text/plain; charset=us-ascii
X-Trace gregory.bnet.hr 1323450002 5232 94.253.138.239 (9 Dec 2011 17:00:02 GMT)
X-Complaints-To abuse@globalnet.hr
NNTP-Posting-Date Fri, 9 Dec 2011 17:00:02 +0000 (UTC)
User-Agent Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux)
Cancel-Lock sha1:6w0KXVk8pKJKAMF9uNPjcqtjLMY=
Xref x330-a1.tempe.blueboxinc.net comp.lang.python:16923

Show key headers only | View raw

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:

> Except for people who needed dicts with tens of millions of items.

Huge tree-based dicts would be somewhat slower than today's hash-based
dicts, but they would be far from unusable.  Trees are often used to
organize large datasets for quick access.

The case of dicts which require frequent access, such as those used to
implement namespaces, is different, and more interesting.  Those dicts
are typically quite small, and for them the difference between O(log n)
and O(1) is negligible in both theory (since n is "small", i.e. bounded)
and practice.  In fact, depending on the details of the implementation,
the lookup in a small tree could even be marginally faster.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: order independent hash? Peter Otten <__peter__@web.de> - 2011-11-30 13:47 +0100
  Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 07:35 -0800
  Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 07:35 -0800
    Re: order independent hash? Dave Angel <d@davea.name> - 2011-12-01 10:52 -0500
      Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 08:17 -0800
      Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 08:17 -0800
    Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-02 03:18 +1100
      Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 20:29 -0800
        Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-02 16:00 +1100
          Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 21:48 -0800
            Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-05 00:40 +1100
          Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 21:48 -0800
            Re: order independent hash? Roel Schroeven <rschroev_nospam_ml@fastmail.fm> - 2011-12-04 14:41 +0100
              Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 07:39 -0800
                Re: order independent hash? Ian Kelly <ian.g.kelly@gmail.com> - 2011-12-04 10:41 -0700
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 10:06 -0800
                Re: order independent hash? Ian Kelly <ian.g.kelly@gmail.com> - 2011-12-04 13:13 -0700
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 15:17 -0800
                Re: order independent hash? Matt Joiner <anacrolix@gmail.com> - 2011-12-05 10:21 +1100
                Re: order independent hash? Ian Kelly <ian.g.kelly@gmail.com> - 2011-12-04 16:24 -0700
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 16:52 -0800
                Re: order independent hash? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-12-05 02:00 +0000
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 16:52 -0800
                Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-05 12:59 +1100
                Re: order independent hash? Ethan Furman <ethan@stoneleaf.us> - 2011-12-04 18:08 -0800
                Re: order independent hash? Ben Finney <ben+python@benfinney.id.au> - 2011-12-05 15:52 +1100
                Re: order independent hash? Matt Joiner <anacrolix@gmail.com> - 2011-12-05 14:02 +1100
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-06 21:24 -0800
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-06 21:24 -0800
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 15:17 -0800
                Re: order independent hash? Terry Reedy <tjreedy@udel.edu> - 2011-12-04 19:28 -0500
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 10:06 -0800
          Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-02 10:53 +0100
            Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-02 03:48 -0800
            Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-02 09:00 -0800
            Re: order independent hash? Terry Reedy <tjreedy@udel.edu> - 2011-12-02 16:40 -0500
              Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-04 14:55 +0100
                Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-05 01:08 +1100
                Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-07 14:28 +0100
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-07 09:48 -0800
                Re: order independent hash? Tim Chase <python.list@tim.thechases.com> - 2011-12-04 12:57 -0600
                Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-08 10:30 +0100
                Re: order independent hash? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-12-09 11:27 +0000
                Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-09 17:51 +0100
                Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-10 04:13 +1100
                Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-11 10:58 +1100
                Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-11 11:17 +1100
                Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-11 14:04 +1100
        Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-05 00:29 +1100
      Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 20:29 -0800
      Re: order independent hash? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-12-02 04:33 +0000

csiph-web