Crawling Python

MK mark at
Sat Jun 19 11:37:59 CEST 1999

On 18 Jun 1999 16:12:26 -0400, Michael Haggerty <mhagger at>

>mark at (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.  

I don't complain about Python's speed. The speed of Python is fine with me. 
What I rather meant to test was performance of anydbm. Now I do know
that daemon of speed it is not. I only wanted to get a grasp how _actually_
it perfoms.

>The above algorithm is O(n^2),
>which means that if you have n keys the time it takes is proportional
>to n squared.  

Now I am not _that_ lame not to know what O(n^2) means.

>That's because each time you add to the end of the
>string, the whole string has to be copied.  

Oh shit, you're right, only know I realized that s=s+d[i] actually does that
which results in given class of algorithm.

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

Thanks. I suspected that .append does not have to copy but was not sure.

>For large n the second algorithm will
>beat the first one every time, by an increasingly huge margin.

Well, good performance of this thing was not important to
me in first place, I actually tried to do some 'crash tests' in
order to find out limits of the system. If I meant performance,
I would write this thing in a different way definitely.

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

Version of IDLE is still 0.4. It works surprisingly good for such an early
version. I would like a few things here and there (for example, the only thing I
sorely miss in IDLE are breakpoints), but overally it's already fine. 


Reality is something that does not disappear after 
you cease believing in it - VALIS, Philip K. Dick

Delete _spamspamlovelyspam_ from address to email me

postmaster at
root at
webmaster at

More information about the Python-list mailing list