[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