Dijkstra on Python

[Skip Montanaro]

    Paul>    sum = ''
    Paul>    for i in range(n):
    Paul>      sum += f(i)

    Paul> Whoops!  The second example works, but has quadratic running time!
    Paul> So real Python programs end up full of hair like

    Paul>    sum = ''.join([f(i) for i in range(n)])

    Paul> which seems to me to require "decoding".

    Paul> I conclude from this that "one obvious way to do it" implies that
    Paul> Python needs a mutable (or at least extendable) string type, that
    Paul> supports += the way list objects support appending.  

There's always the UserString.MutableString class.  Not sure what
performance implications it has.

-- 
Skip Montanaro
skip at pobox.com
consulting: http://manatee.mojam.com/~skip/resume.html