restriction on sum: intentional bug?

[Steven D'Aprano]

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