Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CALvWhxt3t8c14RK8u04Ah14ukp2Gv7EuPV3AjPog0MFSUOfEOg@mail.gmail.com>
References: <930ab3d8-4ab9-446d-9970-ee811eb70a44@googlegroups.com> <F1B463BB-19A6-4DB1-99B3-929CCBFB5920@gmail.com> <50241F14.2060209@tim.thechases.com> <36EA3847-6713-4C12-B47B-9B5E10325F00@gmail.com> <502429C3.5000600@tim.thechases.com> <583C055C-9E99-4EAC-8F3A-D578C399826E@gmail.com> <CALvWhxt3t8c14RK8u04Ah14ukp2Gv7EuPV3AjPog0MFSUOfEOg@mail.gmail.com>
From: Chris Kaynor <ckaynor@zindagigames.com>
Date: Thu, 9 Aug 2012 14:51:17 -0700
Subject: Re: save dictionary to a file without brackets.
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3125.1344549099.4697.python-list@python.org>
Lines: 60
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:26821

I realized, I should have done 10, 100, 1000 rather than 1, 10, 100
for better results, so here are the results for 1000 items. It still
maintains the same pattern:

>>> timeit.timeit('for i in d: pass', 'd=dict.fromkeys(range(1000))')
10.166595947685153
>>> timeit.timeit('for i in d.iteritems(): pass', 'd=dict.fromkeys(range(1000))')
19.922474218828711
>>> timeit.timeit('for i in d: v=d[i]', 'd=dict.fromkeys(range(1000))')
31.007666660415282

Chris

On Thu, Aug 9, 2012 at 2:49 PM, Chris Kaynor <ckaynor@zindagigames.com> wrote:
> On Thu, Aug 9, 2012 at 2:34 PM, Roman Vashkevich <vashkevichrb@gmail.com> 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).
>>
>
> Using "in" as an operator such as: "if key in dict" or "result = key
> in dict" is O(1) as you say. Iterating on the dictionary requires
> touching every item, and so is O(n), even though it also using "in" in
> the command.
>
> Here are a few quick timing tests I just ran with Python 2.6:
>
>>>> timeit.timeit('for i in d: pass', 'd=dict.fromkeys(range(1))')
> 0.078683853332734088
>>>> timeit.timeit('for i in d: pass', 'd=dict.fromkeys(range(10))')
> 0.17451784110969015
>>>> timeit.timeit('for i in d: pass', 'd=dict.fromkeys(range(100))')
> 1.1708168159579486
>
>>>> timeit.timeit('for i in d.iteritems(): pass', 'd=dict.fromkeys(range(1))')
> 0.14186911440299355
>>>> timeit.timeit('for i in d.iteritems(): pass', 'd=dict.fromkeys(range(10))')
> 0.33836512561802579
>>>> timeit.timeit('for i in d.iteritems(): pass', 'd=dict.fromkeys(range(100))')
> 2.2544262854249268
>
>>>> timeit.timeit('for i in d: v=d[i]', 'd=dict.fromkeys(range(1))')
> 0.10009793211446549
>>>> timeit.timeit('for i in d: v=d[i]', 'd=dict.fromkeys(range(10))')
> 0.38825072496723578
>>>> timeit.timeit('for i in d: v=d[i]', 'd=dict.fromkeys(range(100))')
> 3.3020098061049339
>
>
> As can be seen here, a 1-item dictionary iterated in 0.07 seconds, 10
> items in 0.17 seconds, and 100 items in 1.17 seconds. That is fairly
> close to linear, especially when considering the overhead of a
> complete no-op
>
> Using iteritems, it appears to actually scale slightly better than
> linear, though it is slower than just the plain iteration.
>
> Doing a plain iteration, then looking up the keys to get the values
> also appears to be linear, and is even slower than iteritems.