The Running Time of +=

Discussion in 'Python' started by MyHaz, Mar 22, 2005.

  1. MyHaz

    MyHaz Guest

    What is the running time of conactination on character strings.

    i.e.

    >> joe="123"
    >> joe+="99999999999999999"



    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
     
    MyHaz, Mar 22, 2005
    #1
    1. Advertising

  2. >>>>> "Haz" == MyHaz <> 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
    > 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
     
    Skip Montanaro, Mar 22, 2005
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. engsol
    Replies:
    2
    Views:
    964
    Dan Bishop
    Jan 26, 2004
  2. Replies:
    8
    Views:
    491
    Magnus Lycka
    Aug 5, 2005
  3. Peter Hansen
    Replies:
    0
    Views:
    724
    Peter Hansen
    Feb 22, 2006
  4. Peter Hansen
    Replies:
    0
    Views:
    614
    Peter Hansen
    Feb 22, 2006
  5. flamesrock
    Replies:
    8
    Views:
    502
    Hendrik van Rooyen
    Nov 24, 2006
Loading...

Share This Page