RetroSearch Browse

Mon Mar 10 23:31:53 CET 2008 · https://mail.python.org/pipermail/python-dev/2008-March/077534.html

On Mon, Mar 10, 2008 at 5:06 PM, "Martin v. Löwis" <martin at v.loewis.de> wrote:
> > 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.

Certainly.  I am hoping that this thread will soon wind down and
future nitpicking can come in the form of edits to the wiki page with
footnotes or links to other pages for anything non-obvious.

>  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.

I have updated the wiki page accordingly.

I assume there is a reason that PyDict_DelItem never calls dictresize?

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC

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

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

[Python-Dev] Complexity documentation request