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