Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #93950
| Path | csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!bcyclone03.am1.xlned.com!bcyclone03.am1.xlned.com!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!194.109.133.90.MISMATCH!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!post.news.xs4all.nl!not-for-mail |
|---|---|
| Return-Path | <skip.montanaro@gmail.com> |
| X-Original-To | python-list@python.org |
| Delivered-To | python-list@mail.python.org |
| X-Spam-Status | OK 0.005 |
| X-Spam-Evidence | '*H*': 0.99; '*S*': 0.00; '16,': 0.03; 'array.': 0.07; 'extent': 0.07; 'cc:addr:python-list': 0.09; 'subject:How': 0.09; 'lookup': 0.09; 'python': 0.10; 'thu,': 0.15; 'big,': 0.16; 'cc:name:python': 0.16; 'correctly,': 0.16; 'magic': 0.16; 'resize': 0.16; 'threads': 0.16; 'wrote:': 0.16; 'skip': 0.18; '2015': 0.20; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'constant': 0.22; 'nearly': 0.23; 'header:In-Reply-To:1': 0.24; 'message-id:@mail.gmail.com': 0.27; 'initial': 0.28; 'hash': 0.29; 'array': 0.29; 'operations.': 0.33; 'lists': 0.34; 'received:google.com': 0.35; 'done': 0.35; 'possible,': 0.35; "isn't": 0.35; 'but': 0.36; 'too': 0.36; 'subject:work': 0.36; 'subject:?': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'itself': 0.38; 'still': 0.40; 'avoid': 0.61; 'email addr:gmail.com': 0.62; 'linked': 0.63; 'places': 0.64; 'believe': 0.66; 'jul': 0.72; 'grow': 0.75; 'execution.': 0.84; 'memories': 0.84 |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=xipH2VE2CVYCE0WpeOu2Nu8wFY6Z1k8SLyoIYa5XrfU=; b=D9hCKcG3gTIANzDy5pS2EFH5Zj9sGZLi76cUmvvraZFmVRv1KUBfwajoiwKnn+JAjM 7HPl8WhmFNI8Er4rf68YfAQeiIFBxD5uDn0oqOTaKYx7kULC3kPavDRsuWUjYly4H8zE Ge5ZtC1g+K/WtuUcsBeG1mwRw+wIsgwHluqFvLdPmHc/YvpnlNACMUOU1viogrNyaPmm M43tLE3gCZUPG+UEYdcfRar+e8fC8/tu196G5N3caJIyEsJZL4a5j/CAONFaVzwvlGf9 s+KPIRw828vqpnW2qgIMtglrZGMzMruXgdMcynq4GCp+pZ0Gi4RWBOkKEf+aGqCTlgt7 uM4Q== |
| MIME-Version | 1.0 |
| X-Received | by 10.107.15.226 with SMTP id 95mr246059iop.44.1437073102399; Thu, 16 Jul 2015 11:58:22 -0700 (PDT) |
| In-Reply-To | <948FE9D4-63CF-4730-B5F0-675F780A2481@gmail.com> |
| References | <A2CB3AFE-ACB3-4AD3-B35B-4BC6BA3D729D@gmail.com> <CANc-5UwGj5uT_ZBZETQz25O5NeEResUg=P0zL_oHEdK14VkThQ@mail.gmail.com> <948FE9D4-63CF-4730-B5F0-675F780A2481@gmail.com> |
| Date | Thu, 16 Jul 2015 13:58:22 -0500 |
| Subject | Re: How does a dictionary work exactly? |
| From | Skip Montanaro <skip.montanaro@gmail.com> |
| To | "yoursurrogategod@gmail.com" <yoursurrogategod@gmail.com> |
| Cc | Python <python-list@python.org> |
| Content-Type | text/plain; charset=UTF-8 |
| X-BeenThere | python-list@python.org |
| X-Mailman-Version | 2.1.20+ |
| 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.603.1437073105.3674.python-list@python.org> (permalink) |
| Lines | 15 |
| NNTP-Posting-Host | 2001:888:2000:d::a6 |
| X-Trace | 1437073105 news.xs4all.nl 2845 [2001:888:2000:d::a6]:54709 |
| X-Complaints-To | abuse@xs4all.nl |
| X-Received-Bytes | 4212 |
| X-Received-Body-CRC | 4256662374 |
| Xref | csiph.com comp.lang.python:93950 |
Show key headers only | View raw
On Thu, Jul 16, 2015 at 1:36 PM, yoursurrogategod@gmail.com <yoursurrogategod@gmail.com> wrote: > If I understand correctly, lookup would not be a constant, yes? On the contrary, that's what you desire, nearly constant time execution. To the greatest extent possible, you want the linked lists to be of length zero or one. Part of the magic is in figuring out good places to expand the size of the hash array. You don't want it to grow too big, but you still want most linked lists to be very short. The resize operation isn't done too often because it itself is expensive. I believe Python dicts start out with an overly large initial hash array (again, dredging up old memories of threads on python-dev) as an optimization to avoid lots of early resize operations. Skip
Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread
Re: How does a dictionary work exactly? Skip Montanaro <skip.montanaro@gmail.com> - 2015-07-16 13:58 -0500
Re: How does a dictionary work exactly? Ned Batchelder <ned@nedbatchelder.com> - 2015-07-17 07:32 -0700
Re: How does a dictionary work exactly? Skip Montanaro <skip.montanaro@gmail.com> - 2015-07-17 10:58 -0500
csiph-web