On Sat, 17 Oct 2009 07:27:44 -0700, Aahz wrote: >>(For the record, summing lists is O(N**2), and unlike strings, there's >>no optimization in CPython to avoid the slow behaviour.) > > Are you sure?
Not 100% -- I haven't read the CPython source code. But I have done timing tests for repeated concatenation of strings, and demonstrated to my own satisfaction that CPython can avoid O(N**2) behaviour under certain circumstances (but not all). I've repeated those same tests using lists instead of strings, and seen O(N**2) behaviour under all circumstances. This was under Python 2.5 or 2.6, not 3.1. The situation may have changed. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
