On Oct 17, 3:27 pm, a...@pythoncraft.com (Aahz) wrote:
> In article <0062f568$0$26941$c3e8...@news.astraweb.com>,
> Steven D'Aprano <st...@remove-this-cybersource.com.au> 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?
The O(N**2) claim surprised me too, but it certainly looks that
way. Here's a script to produce some timings:
def concat1(list_of_lists):
return sum(list_of_lists, [])
def concat2(list_of_lists):
acc = []
for l in list_of_lists:
acc = acc + l
return acc
def concat3(list_of_lists):
acc = []
for l in list_of_lists:
acc += l
return acc
def concat4(list_of_lists):
acc = []
for l in list_of_lists:
acc.extend(l)
return acc
test_list = [[i] for i in xrange(100000)]
from timeit import Timer
for fn in ["concat1", "concat2", "concat3", "concat4"]:
t = Timer(fn + "(test_list)", "from __main__ import test_list, " +
fn)
print fn, t.timeit(number=3)/3.0
On my machine (OS X 10.5/Core 2 Duo), under Python 2.7 svn I get:
newton:trunk dickinsm$ ./python.exe ~/time_list_sum.py
concat1 48.1459733645
concat2 48.4200883706
concat3 0.0146766503652
concat4 0.0184679826101
For some reason that I don't really understand, the CPython source
does
the equivalent of concat2 instead of concat3. See the builtin_sum
function in
http://svn.python.org/view/python/trunk/Python/bltinmodule.c?view=markup
and scroll past the special cases for ints and floats. After a one-
line
source change, replacing the PyNumber_Add call with
PyNumber_InPlaceAdd,
I get the following results:
newton:trunk dickinsm$ ./python.exe ~/time_list_sum.py
concat1 0.0106019973755
concat2 48.0212899844
concat3 0.0138022899628
concat4 0.0179653167725
--
Mark
--
http://mail.python.org/mailman/listinfo/python-list
