Re: Why you care about this sort of Python bug.

["Michel Arboi" <michel.arboi () gmail com>]

On Sat, Apr 5, 2008 at 3:41 PM, Florian Weimer <fw () deneb enyo de> wrote:
>  Not really.  It's proportional to the number of characters copied.

Definitely not. The execution time of this program is O(n^2).
But it is normal, though.
I did not really look at the Python code first (I never wrote a single
line in this language)

If I understand it correctly, the program truncates the first byte of
the string and starts over until all characters are deleted.  It is
not surprising that it has to copy the string, thus giving a N^2 time
(n + n-1 + n-2 + ...)
No Python bug here, as far as I can understand what Python /should/ do.

[Dave Aitel]
> For example, in Python 2.5: 'string += another_string' or "string =
> string + anotherstring" is O(1) thanks to some optimization.

This is probably true as long as the heap is not fragmented and the
realloc call does not need to copy the buffer.
(once again, I'm just guessing how the Python interpreter is working)
_______________________________________________
Dailydave mailing list
Dailydave () lists immunitysec com
http://lists.immunitysec.com/mailman/listinfo/dailydave