RetroSearch Browse

Mon Mar 10 23:06:44 CET 2008 · https://mail.python.org/pipermail/python-dev/2008-March/077533.html

> I just created a very basic one at
> http://wiki.python.org/moin/TimeComplexity?action=show

I just knew that this could be a field of endless nitpicking.

I think the dict.copy classification is incorrect. A dict.copy
can take unbounded time, if the dict has seen many recent
deletions (which didn't shrink it). Copying will have to iterate
over all slots of the dictionary, and the ratio of slots to
keys can grow unbounded if you have just deletions without
insertions.

IOW, if you do

d = {}
for i in xrange(N):
   d[i]=i
for i in xrange(N-1):
   del d[i]

then doing

d.copy()

takes O(N), not constant time (even though there is only
one key in the dictionary).

> I wasn't sure about many of the set() operations, so I didn't include those.

set is just implemented like a dictionary, without keys.

Regards,
Martin

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://mail.python.org/pipermail/python-dev/2008-March/077533.html below:

[Python-Dev] Complexity documentation request