[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list