[Python-3000] Default dict iterator should have been iteritems() (original) (raw)
Nicholas Bastin nick.bastin at gmail.com
Tue Sep 4 17:39:00 CEST 2007
- Previous message: [Python-3000] Default dict iterator should have been iteritems()
- Next message: [Python-3000] Default dict iterator should have been iteritems()
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On 9/4/07, "Martin v. Löwis" <martin at v.loewis.de> wrote:
> (assuming d[x] is O(log n))
In Python, d[x] is typically considered to be O(1) (unlike in C++, where it is O(log n)). Of course, with Python using a hashtable, performance may decrease in the presence of collisions. In the normal case, dict((x, d[x]) for x in d) will be O(n) in Python.
Even if we suppose that d[x] is O(1) (and I don't have real data to say whether most uses of it actually conform to this, besides keyword argument passing), that still makes:
[(x, d[x]) for x in d]
O(2n), which is O(n), but only pedantically. In the real world, 2n is still worse than n (and the hashtable means that it can devolve into O(n**2) in the worst case). However, all that said, you'd probably never write the above line of code, and d.iteritems() will continue to suffice if there are concerns about 'for (k,v) in d' being materially different than 'if x in d'.
-- Nick
- Previous message: [Python-3000] Default dict iterator should have been iteritems()
- Next message: [Python-3000] Default dict iterator should have been iteritems()
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]