Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #68514
| Path | csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.datemas.de!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail |
|---|---|
| Return-Path | <ian.g.kelly@gmail.com> |
| 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.90; '*S*': 0.00; 'bits': 0.09; 'python': 0.11; '2.7': 0.14; 'bucket': 0.16; 'once.': 0.16; 'shifts': 0.16; 'stumbled': 0.16; 'unequal': 0.16; 'unexpected': 0.16; 'url:file': 0.16; 'wrote:': 0.18; 'code,': 0.22; 'adds': 0.24; 'header:In- Reply-To:1': 0.27; 'am,': 0.29; 'compared': 0.30; 'message- id:@mail.gmail.com': 0.30; 'comments': 0.31; "d'aprano": 0.31; 'keys': 0.31; 'steven': 0.31; 'checked': 0.32; 'url:python': 0.33; 'received:google.com': 0.35; 'url:org': 0.36; 'starting': 0.37; 'sometimes': 0.38; 'to:addr:python-list': 0.38; 'to:addr:python.org': 0.39; 'most': 0.60; 'guarantee': 0.63; 'reached': 0.63; 'within': 0.65; 'mar': 0.68; 'upper': 0.74; 'dict,': 0.84; 'url:cpython': 0.84 |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=KYREHO4WFel8n57mHWeWEhpXiEdCABslwFz7k7uAbuE=; b=lz7ekWnwwe+aPGPZoGphwiX2A9tKvN6gkvq1+rf+sypeuBEzO5iwg0AntpAt0reXuJ m4uX64gO/06EputtO0GGTCsddN8ca2oTv+d98rXKcHZe9m5jOW2IbNCvY3ZBpD5qVSOh e0cNrfcP7gds3m/kVpI94R7rEeDX3hU6sjcOumTRzjn56hFmKlTV1WiOfcpSi1wz6nxo 4z4ApOAmzU5NyY9IOOzEhRVGus5TK/NUUn2QuSr/83511jpRFP8PvCj9RnEn8mLAhZij 2bCH+qeEpgASvX/4P4973IQy+He0VwDDzpuE+GClybiol5PqhlzxN46qGztl/++KP6dg rh6w== |
| X-Received | by 10.68.134.198 with SMTP id pm6mr35461386pbb.9.1395173771428; Tue, 18 Mar 2014 13:16:11 -0700 (PDT) |
| MIME-Version | 1.0 |
| In-Reply-To | <53285617$0$29994$c3e8da3$5496439d@news.astraweb.com> |
| References | <53285617$0$29994$c3e8da3$5496439d@news.astraweb.com> |
| From | Ian Kelly <ian.g.kelly@gmail.com> |
| Date | Tue, 18 Mar 2014 14:15:31 -0600 |
| Subject | Re: Unexpected comparisons in dict lookup |
| To | Python <python-list@python.org> |
| Content-Type | text/plain; charset=ISO-8859-1 |
| X-BeenThere | python-list@python.org |
| X-Mailman-Version | 2.1.15 |
| Precedence | list |
| List-Id | General discussion list for the Python programming language <python-list.python.org> |
| List-Unsubscribe | <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe> |
| List-Archive | <http://mail.python.org/pipermail/python-list/> |
| List-Post | <mailto:python-list@python.org> |
| List-Help | <mailto:python-list-request@python.org?subject=help> |
| List-Subscribe | <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.8258.1395173776.18130.python-list@python.org> (permalink) |
| Lines | 15 |
| NNTP-Posting-Host | 2001:888:2000:d::a6 |
| X-Trace | 1395173776 news.xs4all.nl 2834 [2001:888:2000:d::a6]:59028 |
| X-Complaints-To | abuse@xs4all.nl |
| Xref | csiph.com comp.lang.python:68514 |
Show key headers only | View raw
On Tue, Mar 18, 2014 at 8:20 AM, Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote: > I stumbled across this unexpected behaviour with Python 2.7 and 3.3. When > you look up a key in a dict, the key is sometimes compared against other > keys twice instead of just once. >From what I can see in the code, it adds a perturbation based on the upper bits of the hash value to the probing scheme, to reduce collisions for keys with unequal hashes. On the downside, this cancels the guarantee that each bucket can only be checked at most once. The perturbation gradually shifts to 0 after a few iterations, so every bucket can still be reached within O(n) iterations. See the comments starting at "Major subtleties ahead": http://hg.python.org/cpython/file/f8b40d33e45d/Objects/dictobject.c#l106
Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread
Unexpected comparisons in dict lookup Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-18 14:20 +0000 Re: Unexpected comparisons in dict lookup Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-18 14:15 -0600
csiph-web