On 9/4/07, "Martin v. Löwis" <[EMAIL PROTECTED]> 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 _______________________________________________ Python-3000 mailing list [email protected] http://mail.python.org/mailman/listinfo/python-3000 Unsubscribe: http://mail.python.org/mailman/options/python-3000/archive%40mail-archive.com
