The Running Time of +=

[MyHaz]

What is the running time of conactination on character strings.

i.e.


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]

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

timeit.py -s 'a = "a"*'$i' ; b = "b"*10' 'a += b'
done

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

timeit.py -s 'a = "a"*10 ; b = "b"*'$i 'a += b'
done

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