[Python-ideas] Fast sum() for non-numbers

[Steven D'Aprano]

On 04/07/13 19:54, Sergey wrote:
> On Jul 04, 2013 Steven D'Aprano wrote:
>
> This message is long, so here's its short summary:
> * Unfortunately list.extend does not look like the obvious way, and
>    its slower than alternatives.

[snip]


I'm not going to get into a long and tedious point-by-point argument about this, but I will just re-iterate:

I don't accept that using sum on non-numbers ought to be encouraged, although I don't think it should be prohibited either. So I'm at best neutral on speeding up sum for lists. However, some things do need to be said:

1) Alex Martelli is, or at least was, against using sum on non-numbers:

[quote]
I was responsible for designing sum and doing its first implementation in the Python runtime, and I still wish I had found a way to effectively restrict it to summing numbers (what it's really good at) and block the "attractive nuisance" it offers to people who want to "sum" lists;-). – Alex Martelli Jun 4 '09 at 21:07
[end quote]

This quote is from the Stackoverflow question you linked to earlier:

http://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python


2) You should not be benchmarking against 2.7, but 3.3. On my machine, using 3.3, list.extend is just as fast as using itertools, and both are faster than a list comprehension. (I have not tested your patched version of sum.) Augmented assignment is faster, but faster still is an optimized version using extend that avoids a name look-up:

The tests I ran:

python3.3 -mtimeit --setup="x=[[1,2,3]]*100000" "[i for l in x for i in l]"

python3.3 -mtimeit --setup="x=[[1,2,3]]*100000" \
   --setup="from itertools import chain" \
   "list(chain.from_iterable(x))"

python3.3 -mtimeit --setup="x=[[1,2,3]]*100000" \
     --setup="from itertools import chain" \
     "list(chain(*x))"

python3.3 -mtimeit --setup="x=[[1,2,3]]*100000" --setup="l = []" \
     "for i in x: l += i"

python3.3 -mtimeit --setup="x=[[1,2,3]]*100000" --setup="l = []" \
     "for i in x: l.extend(i)"

python3.3 -mtimeit --setup="x=[[1,2,3]]*100000" --setup="l = []" \
     --setup="extend=l.extend" \
     "for i in x: extend(i)"


with results, from slowest to fastest:

list comp: 32.8 msec per loop
chain: 21 msec per loop
extend: 20.4 msec per loop
chain_from_iterable: 19.8 msec per loop
augmented assignment: 12.8 msec per loop
optimized extend: 11.7 msec per loop


On your machine, results may differ.


-- 
Steven