Author Sergey
Recipients Sergey
Date 2013-06-26.06:33:58
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1372228439.5.0.789865081817.issue18305@psf.upfronthosting.co.za>
In-reply-to
Content
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.
History
Date User Action Args
2013-06-26 06:33:59Sergeysetrecipients: + Sergey
2013-06-26 06:33:59Sergeysetmessageid: <1372228439.5.0.789865081817.issue18305@psf.upfronthosting.co.za>
2013-06-26 06:33:59Sergeylinkissue18305 messages
2013-06-26 06:33:58Sergeycreate