How naive is Python?

[skip at pobox.com]

    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.

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
    % python2.4 strcopy.py 
    32 0.000230073928833 7.18981027603e-06
    64 0.000307083129883 4.79817390442e-06
    128 0.00114107131958 8.91461968422e-06
    256 0.00116014480591 4.53181564808e-06
    512 0.00231313705444 4.51784580946e-06
    1024 0.00459003448486 4.48245555162e-06
    2048 0.00974178314209 4.75673004985e-06
    4096 0.019122838974 4.66866185889e-06
    8192 0.0717267990112 8.75571276993e-06
    16384 0.112125873566 6.84362021275e-06
    32768 0.188065052032 5.73928991798e-06
    % python2.3 strcopy.py 
    32 0.000223875045776 6.99609518051e-06
    64 0.000385999679565 6.03124499321e-06
    128 0.000766038894653 5.98467886448e-06
    256 0.00154304504395 6.02751970291e-06
    512 0.00309181213379 6.03869557381e-06
    1024 0.0065929889679 6.43846578896e-06
    2048 0.0147500038147 7.20215030015e-06
    4096 0.14589214325 3.56181990355e-05
    8192 0.778324127197 9.50102694333e-05
    16384 3.20213103294 0.000195442567929
    32768 14.7389230728 0.000449796236353
    % python2.2 strcopy.py
    32 0.00031590461731 9.87201929092e-06
    64 0.000494003295898 7.71880149841e-06
    128 0.00090217590332 7.04824924469e-06
    256 0.00173211097717 6.76605850458e-06
    512 0.00362610816956 7.08224251866e-06
    1024 0.00711607933044 6.94929622114e-06
    2048 0.0158200263977 7.7246222645e-06
    4096 0.152237892151 3.71674541384e-05
    8192 0.89648604393 0.000109434331534
    16384 3.14483094215 0.000191945247934
    32768 13.3367011547 0.000407003819419

Skip