How naive is Python?

[skip at pobox.com]

>>>>> "John" == John Machin <sjmachin at lexicon.net> writes:

    John> skip at pobox.com wrote:
    John> Sorry, Skip, but I find that very hard to believe. The foo()
    John> function would take quadratic time if it were merely adding on
    John> pieces of constant size -- however len(str(i)) is not a constant,
    John> it is O(log10(i)), so the time should be super-quadratic.
    >> 
    me> Sorry, I should have pointed out that I'm using the latest version
    me> of Python.  I believe += for strings has been optimized to simply
    me> extend s when there is only a single reference to it.

    John> Sorry, I should have pointed out that you need to read up about
    John> time.time() -- what is its resolution on your box? -- and
    John> time.clock() and the timeit module.

time.time() should be plenty good enough for this particular task on my
machine (Mac OSX).  time.time() has plenty of resolution:

    >>> import time
    >>> t = time.time() ; print time.time()-t
    3.79085540771e-05
    >>> t = time.time() ; print time.time()-t
    5.00679016113e-06
    >>> t = time.time() ; print time.time()-t
    5.96046447754e-06
    >>> t = time.time() ; print time.time()-t
    5.00679016113e-06

It's time.clock() on Unix-y systems that is too coarse:

    >>> t = time.clock() ; print time.clock()-t
    0.0
    >>> t = time.clock() ; print time.clock()-t
    0.0
    >>> t = time.clock() ; print time.clock()-t
    0.0
    >>> t = time.clock() ; print time.clock()-t
    0.0
    >>> t = time.clock() ; print time.clock()-t
    0.0

I ran the size of the loop to 2**24 and still only saw linear growth in the
later versions of Python.  The machine (my Mac laptop) was otherwise idle.
I only reduced the loop length in what I posted before because of the
quadratic growth in Python 2.2 and 2.3.  It took so long to run my script
using 2.2 and 2.3 I made a slight change so that it bailed out of the larger
loops:

    #!/usr/bin/env python

    from __future__ import division

    def foo(kcount):
        s = ''
        for i in xrange(kcount) :
            s += str(i) + ' '

    import time

    for i in xrange(5,25):
        t = time.time()
        foo(2**i)
        t = time.time() - t
        print "2**%d"%i, 2**i, t, t/2**i
        if t > 200:
            break

I then ran it using this shell command:

    for v in 2.6 2.5 2.4 2.3 2.2 ; do
        echo $v
        time python$v strcopy.py
    done 2>&1 \
    | tee strcopy.out

The output is:

    2.6
    2**5 32 0.000240802764893 7.52508640289e-06
    2**6 64 0.000278949737549 4.3585896492e-06
    2**7 128 0.000599145889282 4.68082726002e-06
    2**8 256 0.00878977775574 3.43350693583e-05
    2**9 512 0.00221586227417 4.32785600424e-06
    2**10 1024 0.00433588027954 4.23425808549e-06
    2**11 2048 0.00897288322449 4.38129063696e-06
    2**12 4096 0.0197570323944 4.82349423692e-06
    2**13 8192 0.0359501838684 4.38845017925e-06
    2**14 16384 0.0721030235291 4.40081930719e-06
    2**15 32768 0.146120071411 4.45923069492e-06
    2**16 65536 0.292731046677 4.46672129328e-06
    2**17 131072 0.692205905914 5.28111195308e-06
    2**18 262144 1.20644402504 4.60221872345e-06
    2**19 524288 3.34210991859 6.37456878394e-06
    2**20 1048576 6.86596488953 6.54789437249e-06
    2**21 2097152 10.0534589291 4.79386278585e-06
    2**22 4194304 21.4015710354 5.1025321568e-06
    2**23 8388608 40.8173680305 4.86580944425e-06
    2**24 16777216 84.5512800217 5.039649011e-06

    real        2m50.195s
    user        2m26.258s
    sys 0m2.998s
    2.5
    2**5 32 0.000205039978027 6.40749931335e-06
    2**6 64 0.000274896621704 4.29525971413e-06
    2**7 128 0.000594139099121 4.64171171188e-06
    2**8 256 0.00110697746277 4.32413071394e-06
    2**9 512 0.00236988067627 4.62867319584e-06
    2**10 1024 0.0045051574707 4.39956784248e-06
    2**11 2048 0.00938105583191 4.58059366792e-06
    2**12 4096 0.0197520256042 4.82227187604e-06
    2**13 8192 0.0375790596008 4.58728754893e-06
    2**14 16384 0.0780160427094 4.76172135677e-06
    2**15 32768 0.148911952972 4.54443215858e-06
    2**16 65536 0.307368040085 4.69006408821e-06
    2**17 131072 0.703125953674 5.36442530574e-06
    2**18 262144 1.22114300728 4.6582908908e-06
    2**19 524288 2.62232589722 5.00168971485e-06
    2**20 1048576 5.06462287903 4.83000076201e-06
    2**21 2097152 10.3055510521 4.9140696774e-06
    2**22 4194304 24.6841719151 5.88516519429e-06
    2**23 8388608 42.5984380245 5.07812953288e-06
    2**24 16777216 89.6156759262 5.34151052989e-06

    real        2m58.236s
    user        2m29.354s
    sys 0m2.978s
    2.4
    2**5 32 0.000231981277466 7.24941492081e-06
    2**6 64 0.000316858291626 4.95091080666e-06
    2**7 128 0.000571966171265 4.46848571301e-06
    2**8 256 0.00112700462341 4.40236181021e-06
    2**9 512 0.00228881835938 4.47034835815e-06
    2**10 1024 0.00619387626648 6.04870729148e-06
    2**11 2048 0.00927710533142 4.52983658761e-06
    2**12 4096 0.0188140869141 4.593282938e-06
    2**13 8192 0.0386338233948 4.71604289487e-06
    2**14 16384 0.0761170387268 4.64581535198e-06
    2**15 32768 0.153247117996 4.67673089588e-06
    2**16 65536 0.306257009506 4.67311110697e-06
    2**17 131072 0.724220991135 5.52536766918e-06
    2**18 262144 1.23747801781 4.7206040108e-06
    2**19 524288 2.69648981094 5.1431461543e-06
    2**20 1048576 5.20070004463 4.9597740599e-06
    2**21 2097152 10.6776590347 5.09150459038e-06
    2**22 4194304 21.149684906 5.04247782374e-06
    2**23 8388608 46.8901240826 5.58973837883e-06
    2**24 16777216 110.079385042 6.56124264253e-06

    real        3m19.593s
    user        2m32.932s
    sys 0m3.100s
    2.3
    2**5 32 0.000223159790039 6.97374343872e-06
    2**6 64 0.000349998474121 5.46872615814e-06
    2**7 128 0.000737905502319 5.76488673687e-06
    2**8 256 0.00150609016418 5.88316470385e-06
    2**9 512 0.00307989120483 6.01541250944e-06
    2**10 1024 0.00642395019531 6.27338886261e-06
    2**11 2048 0.0161211490631 7.87165481597e-06
    2**12 4096 0.110109090805 2.68821022473e-05
    2**13 8192 0.787949800491 9.61852783803e-05
    2**14 16384 3.3133919239 0.000202233393793
    2**15 32768 14.3907749653 0.000439171599282
    2**16 65536 60.2394678593 0.000919181333302
    2**17 131072 295.17253089 0.00225198769294

    real        6m15.110s
    user        1m54.907s
    sys 3m26.747s
    2.2
    2**5 32 0.000303030014038 9.46968793869e-06
    2**6 64 0.000451803207397 7.05942511559e-06
    2**7 128 0.00087308883667 6.82100653648e-06
    2**8 256 0.00233697891235 9.12882387638e-06
    2**9 512 0.00344800949097 6.73439353704e-06
    2**10 1024 0.00730109214783 7.12997280061e-06
    2**11 2048 0.017196893692 8.39692074805e-06
    2**12 4096 0.112847805023 2.75507336482e-05
    2**13 8192 0.840929031372 0.00010265246965
    2**14 16384 3.05718898773 0.000186596007552
    2**15 32768 13.0093569756 0.000397014067858
    2**16 65536 57.9497959614 0.00088424371279
    2**17 131072 294.361263037 0.00224579821042

    real        6m9.514s
    user        1m55.257s
    sys 3m26.943s

It's clear that the behavior of the 2.4, 2.5 and 2.6 (cvs) versions is
substantially different than the 2.2 and 2.3 versions, and grows linearly as
the string length grows.  I believe any slight nonlinearity in the 2.4-2.6
versions is just due to quadratic behavior in the Mac's realloc function.

Skip