Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: restriction on sum: intentional bug?

Reply
Thread Tools

Re: restriction on sum: intentional bug?

 
 
Steven D'Aprano
Guest
Posts: n/a
 
      10-18-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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: restriction on sum: intentional bug? Steve Python 3 10-27-2009 09:12 PM
Re: restriction on sum: intentional bug? Ethan Furman Python 6 10-20-2009 02:42 AM
Re: restriction on sum: intentional bug? Benjamin Peterson Python 3 10-17-2009 11:42 PM
Re: restriction on sum: intentional bug? Carl Banks Python 2 10-17-2009 10:46 AM
Re: restriction on sum: intentional bug? Tim Chase Python 4 10-17-2009 07:34 AM



Advertisments