How naive is Python?

[John Machin]

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.

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

>
> Actually, it isn't until I work my way back to 2.3 that I start to see
> quadratic behavior:
>
>     % python2.6 strcopy.py
>     32 0.00022292137146 6.96629285812e-06
>     64 0.000907897949219 1.41859054565e-05
>     128 0.000649929046631 5.0775706768e-06
>     256 0.00111794471741 4.36697155237e-06
>     512 0.00260806083679 5.09386882186e-06
>     1024 0.00437998771667 4.27733175457e-06
>     2048 0.00921607017517 4.50003426522e-06
>     4096 0.0191979408264 4.68699727207e-06
>     8192 0.0694131851196 8.47328919917e-06
>     16384 0.0976829528809 5.96209429204e-06
>     32768 0.194766998291 5.94381708652e-06
>     % python2.5 strcopy.py
>     32 0.000439167022705 1.37239694595e-05
>     64 0.000303030014038 4.73484396935e-06
>     128 0.000631809234619 4.93600964546e-06
>     256 0.00112318992615 4.38746064901e-06
>     512 0.00279307365417 5.45522198081e-06
>     1024 0.00446391105652 4.35928814113e-06
>     2048 0.00953102111816 4.65381890535e-06
>     4096 0.0198018550873 4.83443727717e-06
>     8192 0.175454854965 2.14178289752e-05
>     16384 0.103327989578 6.30663998891e-06
>     32768 0.191411972046 5.84142981097e-06
[snip]

Your ability to "see" quadratic behavoiur appears to be impaired by (1)
the low resolution and/or erratic nature of time.time() on your system
(2) stopping the experiment just before the results become interesting.

Try this with the latest *production* release (2.5):

C:\junk>cat fookount.py
def foo(kcount):
    s = ''
    for i in xrange(kcount) :
        s += str(i) + ' '

C:\junk>for /L %n in (10,1,19) do \python25\python -mtimeit -s"from
fookount import foo" "foo(2**%n)"

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**10)"
100 loops, best of 3: 1.1 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**11)"
100 loops, best of 3: 2.34 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**12)"
100 loops, best of 3: 4.79 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**13)"
10 loops, best of 3: 9.57 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**14)"
10 loops, best of 3: 19.8 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**15)"
10 loops, best of 3: 40.7 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**16)"
10 loops, best of 3: 82.1 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**17)"
10 loops, best of 3: 242 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**18)"
10 loops, best of 3: 886 msec per loop

C:\junk>\python25\python -mtimeit -s"from fookount import foo"
"foo(2**19)"
10 loops, best of 3: 3.21 sec per loop

Cheers,
John