Crawling Python

[Michael Haggerty]

mark at _spamspamlovelyspam_btweng.krakow.pl (MK) writes:

> >>> s=''
> >>> for i in d.keys():
> 	s=s+d[i]

Please, before you complain about Python's speed, think twice about
the algorithm that you are using.  The above algorithm is O(n^2),
which means that if you have n keys the time it takes is proportional
to n squared.  That's because each time you add to the end of the
string, the whole string has to be copied.  (Unless there is a
nontrivial optimization built into Python for this special case, but I
don't think so.)

But if instead you do

>>> import string
>>> s = []
>>> for i in d.keys():
>>>   s.append(d[i])
>>> s = string.join(s, '')

then you get exactly the same result in O(n) time, because s.append()
doesn't have to copy each time.  For large n the second algorithm will
beat the first one every time, by an increasingly huge margin.

It may be that idle has problems too, but at least part of this
problem can be blamed on the algorithm.

Michael

-- 
Michael Haggerty
mhagger at blizzard.harvard.edu