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 <ckay...@zindagigames.com> wrote: > On Thu, Aug 9, 2012 at 2:34 PM, Roman Vashkevich <vashkevic...@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. -- http://mail.python.org/mailman/listinfo/python-list