[New-bugs-announce] [issue18305] [patch] Fast sum() for non-numbers
Sergey
report at bugs.python.org
Wed Jun 26 08:33:59 CEST 2013
New submission from Sergey:
Problem
=======
Code:
sum([[1,2,3]]*1000000, [])
takes forever to complete.
Suggestion
==========
Patch sum() function so that it did not created 1000000 copies of result, but created just one. Attached patch does that.
Before patch:
$ ./python -mtimeit --setup="x=[[1,2,3]]*10000" "sum(x,[])"
10 loops, best of 3: 915 msec per loop
After patch:
$ ./python -mtimeit --setup="x=[[1,2,3]]*10000" "sum(x,[])"
1000 loops, best of 3: 469 usec per loop
200000% boost! :)
Details
=======
Built-in sum function could look like this:
def sum(seq, start = 0):
for item in seq:
start += item
return start
But that would be bad, becaust in cases like:
empty = []
result = sum(list_of_lists, empty)
content of "empty" would be modified.
So instead it looks like this:
def sum(seq, start = 0):
for item in seq:
start = start + item
return start
it creates a copy of the entire partial result on EVERY "start + item".
While instead it could look like this:
def sum(seq, start = 0):
start = start + seq[0:1]
for item in seq[1:]:
start += item
return start
create just ONE copy, and use it.
That's what attached patch is doing.
An alternative is something like this:
def sum(seq, start = 0):
start = copy.copy(start)
for item in seq:
start += item
return start
But I'm not sure how to make a copy of arbitrary object yet.
----------
components: Interpreter Core
files: fastsum.patch
keywords: patch
messages: 191896
nosy: Sergey
priority: normal
severity: normal
status: open
title: [patch] Fast sum() for non-numbers
type: performance
versions: Python 2.7
Added file: http://bugs.python.org/file30705/fastsum.patch
_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue18305>
_______________________________________
More information about the New-bugs-announce
mailing list