Crawling Python

[MK]

On 18 Jun 1999 16:12:26 -0400, Michael Haggerty <mhagger at blizzard.harvard.edu>
wrote:

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

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. 





MK


--------------------------------------------------
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 127.0.0.1
root at 127.0.0.1
webmaster at 127.0.0.1