On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <[EMAIL PROTECTED]> wrote: > This is interesting. I had never attempted to verify a big O > statement > before, and decided that it would be worth trying. So I wrote some > code to > collect data, and I can't find that it goes quadratic. I have the > graph > at > > http://kasterma.wordpress.com/2008/06/16/complexity-of-string-concatenation/ > > It looks piecewise linear to me.
I don't think there's any question that it's quadratic. Just look at the C code, and you'll see that every time you concatenate the entire string has to be copied. Remember that the copy code uses memcpy from the C library, though, so it's quite fast. If you're not seeing it for relatively small strings, it's probably that the major time component is the Python looping construct, not the copy operation. I tried it at lengths of multiples of 10, and it remained linear up until 1E6. At 1E7, it appears to turn quadratic. I tried 1E8, but it hasn't finished yet. I expect it to take the better part of an hour. >>> from timeit import Timer >>> a = Timer("a += 'a'", "a = ''") >>> a.timeit(10) 6.9841280492255464e-006 >>> a.timeit(100) 2.7936511287407484e-005 >>> a.timeit(1000) 0.00043525084856810281 >>> a.timeit(10000) 0.0049266038004134316 >>> a.timeit(100000) 0.046758456731367914 >>> a.timeit(1000000) 0.38496261396358022 >>> a.timeit(10000000) 20.320074199374631 Even though it doesn't become quadratic until 1E7, it's still up to an order of magnitude faster to use str.join for smaller strings, though: >>> b = Timer("''.join(['a'] * 1000000)") >>> b.timeit(1) 0.044094989726346512 -Ian -- http://mail.python.org/mailman/listinfo/python-list