restriction on sum: intentional bug?
Steven D'Aprano
steve at REMOVE-THIS-cybersource.com.au
Sun Oct 18 00:58:21 EDT 2009
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
More information about the Python-list
mailing list