[Python-3000] Default dict iterator should have been iteritems() (original) (raw)
Guido van Rossum guido at python.org
Tue Sep 4 18:17:36 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, Nicholas Bastin <nick.bastin at gmail.com> wrote:
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).
You shouldn't be using words whose meaning you don't understand.
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'.
Since this is the python-3000 list, d.items() is what you're looking for.
-- --Guido van Rossum (home page: http://www.python.org/~guido/)
- 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 ]