The Running Time of +=

[MyHaz]

What is the running time of conactination on character strings.

i.e.
[color=blue][color=green]
>> joe="123"
>> joe+="999999999 99999999"[/color][/color]


is it Amortized Constant time? I don't think it would be O((number of
chars)^2) but i really don't know.

Teach me how to fish, where would i find out more about the internal
representations of data types in python (and guarenteed run times, im
think of something like sgi.com 's info on the STL) . I have looked
through the docs but i don't seem to see these types of specifications.


thanks * 100
- Haz

[Skip Montanaro]

Re: The Running Time of +=

>>>>> "Haz" == MyHaz <support.servic es.complaints@g mail.com> writes:

Haz> Teach me how to fish, where would i find out more about the
Haz> internal representations of data types in python

The source.

Experimentally you can use the timeit command to see how it performs:

% for i in 10 20 40 80 160 320 640 1280 ; do[color=blue]
> timeit.py -s 'a = "a"*'$i' ; b = "b"*10' 'a += b'
> done[/color]
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.826 usec per loop

% for i in 10 20 40 80 160 320 640 1280 ; do[color=blue]
> timeit.py -s 'a = "a"*10 ; b = "b"*'$i 'a += b'
> done[/color]
1000000 loops, best of 3: 0.826 usec per loop
1000000 loops, best of 3: 0.909 usec per loop
1000000 loops, best of 3: 1.11 usec per loop
1000000 loops, best of 3: 1.52 usec per loop
100000 loops, best of 3: 1.97 usec per loop
100000 loops, best of 3: 3.18 usec per loop
100000 loops, best of 3: 5.54 usec per loop
100000 loops, best of 3: 10.5 usec per loop

Skip