On 9/4/07, Nicholas Bastin <[EMAIL PROTECTED]> wrote: > 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).
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/) _______________________________________________ Python-3000 mailing list Python-3000@python.org http://mail.python.org/mailman/listinfo/python-3000 Unsubscribe: http://mail.python.org/mailman/options/python-3000/archive%40mail-archive.com
