Velocity Reviews > sum for sequences?

# sum for sequences?

Alf P. Steinbach
Guest
Posts: n/a

 03-25-2010
* Neil Cerutti:
> On 2010-03-25, Steven D'Aprano <(E-Mail Removed)> wrote:
>>> You might not want to be so glib. The sum doc sure doesn't
>>> sound like it should work on lists.
>>>
>>> Returns the sum of a sequence of numbers (NOT strings) plus the
>>> value of parameter 'start' (which defaults to 0).

>> What part of that suggested to you that sum might not be polymorphic?
>> Sure, it says numbers (which should be changed, in my opinion), but it
>> doesn't specify what sort of numbers -- ints, floats, or custom types
>> that have an __add__ method.

>
> WTF.

I think Steven's argument is that it would be pointless for 'sum' to distinguish
between user-defined numerical types and other types that happen to support '+'.

It could make such a distinction since there's a type hierarchy for numbers, but
then that should IMHO be more clearly documented.

However, given that it isn't restricted to numbers, the restriction wrt. strings
is a bit perplexing in the context of modern CPython. But for Python
implementations that don't offer the '+=' optimization it might help to avoid
gross inefficiencies, namely quadratic time string concatenation. E.g., here's a
natural implementation of sum -- with unoptimized '+=' yielding quadratic time
for the string concatenation (with modern CPython it's linear time, though):

<example>
>>> def sum_all( values, start = 0 ):

... s = start
... for v in values: s += v
... return s
...
>>> sum_all( (1, 2, 3, 4) )

10
>>> sum_all( ("a", "b", "c", "d"), "" )

'abcd'
>>> sum_all( ((1, 2), (3, 4), (5, 6)), () )

(1, 2, 3, 4, 5, 6)
>>> _

</example>

However, if that hypothesis about the rationale is correct, then 'sum' should
also be restricted to not handle tuples or lists, so forth, but at least the
CPython implementation does.

So perhaps the documentation needs to be more clear?

Cheers,

- Alf

Steven D'Aprano
Guest
Posts: n/a

 03-25-2010
On Thu, 25 Mar 2010 14:02:05 +0100, Alf P. Steinbach wrote:

> * Neil Cerutti:
>> On 2010-03-25, Steven D'Aprano <(E-Mail Removed)>
>> wrote:
>>>> You might not want to be so glib. The sum doc sure doesn't sound
>>>> like it should work on lists.
>>>>
>>>> Returns the sum of a sequence of numbers (NOT strings) plus the
>>>> value of parameter 'start' (which defaults to 0).
>>> What part of that suggested to you that sum might not be polymorphic?
>>> Sure, it says numbers (which should be changed, in my opinion), but it
>>> doesn't specify what sort of numbers -- ints, floats, or custom types
>>> that have an __add__ method.

>>
>> WTF.

>
> I think Steven's argument is that it would be pointless for 'sum' to
> distinguish between user-defined numerical types and other types that
> happen to support '+'.

Before Python2.6, which introduced a numeric tower, Python *couldn't*
reliably distinguish between numeric types and other types that
overloaded +. Since Python discourages type-checking in favour of duck-
typing and try...except, this is seen as a good thing.

My argument is that sum isn't hard-coded to only work on the built-ins
ints or floats, but it supports any object that you can use the +
operator on. The *sole* exceptions are str and unicode (not even
UserString), and even there it is very simple to overcome the restriction:

>>> sum(['a', 'b'], '')

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: sum() can't sum strings [use ''.join(seq) instead]
>>> class S:

.... return other
....
>>> sum(['a', 'b'], S())

'ab'

[...]
> However, given that it isn't restricted to numbers, the restriction wrt.
> strings is a bit perplexing in the context of modern CPython. But for
> Python implementations that don't offer the '+=' optimization it might
> help to avoid gross inefficiencies, namely quadratic time string
> concatenation.

I agree -- the Python philosophy is to allow the user to shoot themselves
in the foot if they wish to. You're responsible for the Big Oh behaviour
of your code, not the compiler.

[...]
> However, if that hypothesis about the rationale is correct, then 'sum'
> should also be restricted to not handle tuples or lists, so forth, but
> at least the CPython implementation does.

The reasoning is that naive users are far, far more likely to try summing
a large list of strings than to try summing a large list of lists, and
therefore in practical terms the consequences of allowing sum on lists is
slight enough and rare enough to not be worth the check.

I suspect that this is just an after the fact rationalisation, and that
the real reason is that those responsible for the hand-holding in sum
merely forgot, or didn't know, that repeated addition of lists and tuples
is also O(N**2). But I've never cared enough to dig through the archives
to find out.

--
Steven

Steve Howell
Guest
Posts: n/a

 03-26-2010
On Mar 24, 4:19*pm, Paul Rubin <(E-Mail Removed)> wrote:
> kj <(E-Mail Removed)> writes:
> > Is there a sequence-oriented equivalent to the sum built-in? *E.g.:
> > * seq_sum(((1, 2), (5, 6))) --> (1, 2) + (5, 6) --> (1, 2, 5, 6)

>
> use itertools.chain for this. *A few people have mentioned that sum will
> also work, but I think for that purpose it could have O(n**2)
> complexity.

I agree on the practical matter that itertools.chain and other
solutions are usually the way to go for most tasks that involve
iterating through several lists.

From a purely academic standpoint, I'm not convinced that sum() is
inefficient in terms of big-O complexity, though.

showell@showell-laptop:~\$ python
Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41)
[GCC 4.3.3] on linux2
>>> class StupidList:

... def __init__(self, lst):
... print 'creating', lst
... self.lst = lst
... self.lst += '|'
... self.lst.extend(other.lst)
... return self
...
>>> result = sum([StupidList([1, 2]), StupidList([3,4]),

StupidList([5,6])], StupidList([0]))
creating [1, 2]
creating [3, 4]
creating [5, 6]
creating [0]
>>> result.lst

[0, '|', 1, 2, '|', 3, 4, '|', 5, 6]

If I'm interpreting the above program correctly, then sum() is doing
the most efficient thing under the hood--it appears to do the
equivalent of += without creating unnecessary objects for intermediate
sums.

I think the special-case error message might be a case where
practicality simply beats out purity. It would be nice if sum() were
completely duck-typed-let-you-shoot-yourself-in-foot-if-you-know-what-
you-are-doing, but maybe this was such a pitfall at one time, that
extra safeguards were put into sum(). I wonder how severely sum(),
without the restriction, would underperform join() on modern versions
of Python, though.

>>> sum('1', '2')

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: sum() can't sum strings [use ''.join(seq) instead]

Note that you can easily fake out sum() to get duck typing.

>>> class EmptyStringStarter:

... def __add__(self, other): return other
...
>>> empty = EmptyStringStarter()
>>> sum(['hello ', 'world'], empty)

'hello world'

Steve Howell
Guest
Posts: n/a

 03-26-2010
On Mar 26, 7:31*am, Steve Howell <(E-Mail Removed)> wrote:
> On Mar 24, 4:19*pm, Paul Rubin <(E-Mail Removed)> wrote:
>
> > kj <(E-Mail Removed)> writes:
> > > Is there a sequence-oriented equivalent to the sum built-in? *E.g.:
> > > * seq_sum(((1, 2), (5, 6))) --> (1, 2) + (5, 6) --> (1, 2, 5, 6)

>
> > use itertools.chain for this. *A few people have mentioned that sum will
> > also work, but I think for that purpose it could have O(n**2)
> > complexity.

>
> I agree on the practical matter that itertools.chain and other
> solutions are usually the way to go for most tasks that involve
> iterating through several lists.
>
> From a purely academic standpoint, I'm not convinced that sum() is
> inefficient in terms of big-O complexity, though.
>
> *showell@showell-laptop:~\$ python
> *Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41)
> *[GCC 4.3.3] on linux2
> *>>> class StupidList:
> *... * def __init__(self, lst):
> *... * * print 'creating', lst
> *... * * self.lst = lst
> *... * def __add__(self, other):
> *... * * self.lst += '|'
> *... * * self.lst.extend(other.lst)
> *... * * return self
> *...
> *>>> result = sum([StupidList([1, 2]), StupidList([3,4]),
> StupidList([5,6])], StupidList([0]))
> *creating [1, 2]
> *creating [3, 4]
> *creating [5, 6]
> *creating [0]
> *>>> result.lst
> *[0, '|', 1, 2, '|', 3, 4, '|', 5, 6]
>
> If I'm interpreting the above program correctly, then sum() is doing
> the most efficient thing under the hood--it appears to do the
> equivalent of += without creating unnecessary objects for intermediate
> sums.
>
> I think the special-case error message might be a case where
> practicality simply beats out purity. *It would be nice if sum() were
> completely duck-typed-let-you-shoot-yourself-in-foot-if-you-know-what-
> you-are-doing, but maybe this was such a pitfall at one time, that
> extra safeguards were put into sum(). *I wonder how severely sum(),
> without the restriction, would underperform join() on modern versions
> of Python, though.
>
> *>>> sum('1', '2')
> *Traceback (most recent call last):
> * *File "<stdin>", line 1, in <module>
> *TypeError: sum() can't sum strings [use ''.join(seq) instead]
>
> Note that you can easily fake out sum() to get duck typing.
>
> *>>> class EmptyStringStarter:
> *... * def __add__(self, other): return other
> *...
> *>>> empty = EmptyStringStarter()
> *>>> sum(['hello ', 'world'], empty)
> *'hello world'

Looking at the code answers my own questions:

http://svn.python.org/view/python/tr....c?view=markup

Look for builtin_sum().

First you see the guard against strings:

/* reject string values for 'start' parameter */
if (PyObject_TypeCheck(result, &PyBaseString_Type)) {
PyErr_SetString(PyExc_TypeError,
"sum() can't sum strings [use ''.join(seq) instead]");
Py_DECREF(iter);
return NULL;
}
Py_INCREF(result);

Also, Paul's suspicion that sum() works in O(N squared) for lists is
confirmed by this comment:

when doing 'sum(list_of_lists, [])'. However, this
would produce a change in behaviour: a snippet like
empty = []
sum([[x] for x in range(10)], empty)
would change the value of empty. */

It's interesting, though, that you can construct classes pretty
easily, as I did above, that avoid the quadratic behavior, as long as
you do not mind mutating the start value, which I think is usually
fine, since the original start value usually is not useful afterward
anyway.

Steven D'Aprano
Guest
Posts: n/a

 03-27-2010
On Fri, 26 Mar 2010 07:31:17 -0700, Steve Howell wrote:

> From a purely academic standpoint, I'm not convinced that sum() is
> inefficient in terms of big-O complexity, though.
>
> showell@showell-laptop:~\$ python
> Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41) [GCC 4.3.3] on
> linux2
> >>> class StupidList:

[...]

But it's not *sum* that is inefficient, it is sum *with a particular data
structure*.

Sure, if you create your own data structure, you can make it as efficient
as you like. Obviously the sum algorithm itself has to perform one
addition per item, or O(N), which scales tolerably well. But each
addition has a cost. If the cost is constant, then sum() as a whole
remains O(N). But if the cost of addition varies with N, sum() degrades

We can compare the performance of sum with different data structures,
starting with plain integers versus long integers:

>>> from timeit import Timer
>>> setup = 'data = [%d]*%d'
>>> for i in range(6):

.... t1 = Timer('sum(data, 0)', setup % (1, 10**i))
.... t2 = Timer('sum(data, 0)', setup % (10**50, 10**i))
.... print min(t1.repeat(number=1000)),
.... print min(t2.repeat(number=1000))
....
0.00179290771484 0.00263810157776
0.00340414047241 0.00854396820068
0.0190401077271 0.0502791404724
0.155302047729 0.645124912262
0.794432878494 2.55748295784
7.97877693176 25.3812758923

Both scale about as well, but the cost varies significantly: arithmetic
on very large longints is expensive.

Strings, with a trick to fool sum into accepting them, versus lists. Note
that I changed the number of iterations from 6 down to 5. The reason why
will become obvious:

>>> class EmptyStringStarter:

.... return other
....
>>> empty = EmptyStringStarter()
>>> setup = """from __main__ import empty; data = [%r]*%d"""
>>>
>>> for i in range(5):

.... t1 = Timer('sum(data, empty)', setup % ('a', 10**i))
.... t2 = Timer('sum(data, [])', setup % ([1], 10**i))
.... print min(t1.repeat(number=1000)),
.... print min(t2.repeat(number=1000))
....
0.00849103927612 0.00226998329163
0.0121459960938 0.0082700252533
0.0489149093628 0.186735153198
0.428920030594 5.28623914719
14.6552250385 589.102822065

Strings perform tolerably well, up to a point, but lists perform
terribly. And in fact, the relatively good performance of strings is an
older versions of CPython, it will behave as poorly as lists.

> I wonder how severely sum(), without
> the restriction, would underperform join() on modern versions of Python,
> though.

Take note that, in order to get an answer in reasonable time, I've
reduced the number of timing iterations drastically:

>>> for i in range(6):

.... t1 = Timer('sum(data, empty)', setup % ('a', 10**i))
.... t2 = Timer('"".join(data)', setup % ('a', 10**i))
.... print min(t1.repeat(number=10)),
.... print min(t2.repeat(number=10))
....
8.89301300049e-05 1.09672546387e-05
0.000131845474243 2.19345092773e-05
0.000591993331909 9.29832458496e-05
0.0101289749146 0.00082802772522
0.365957021713 0.00884819030762
24.2072279453 0.0421011447906

Note the performance degradation of sum. It gets worse. Much worse:

>>> for i in range(4, 7):

.... t1 = Timer('sum(data, empty)', setup % ('a', 10**i))
.... t2 = Timer('"".join(data)', setup % ('a', 10**i))
.... print min(t1.repeat(number=1)), # note fewer iterations
.... print min(t2.repeat(number=1))
....
0.031229019165 0.000817060470581
2.45445990562 0.00365781784058
1024.79705095 0.0398509502411

This is absolutely catastrophic performance degradation.

--
Steven

Steve Howell
Guest
Posts: n/a

 03-28-2010
On Mar 27, 3:18*am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
> On Fri, 26 Mar 2010 07:31:17 -0700, Steve Howell wrote:
> > From a purely academic standpoint, I'm not convinced that sum() is
> > inefficient in terms of big-O complexity, though.

>
> > *showell@showell-laptop:~\$ python
> > *Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41) [GCC 4.3.3] on
> > *linux2
> > *>>> class StupidList:

>
> [...]
>
> But it's not *sum* that is inefficient, it is sum *with a particular data
> structure*.
>

Yep, the implied context was with particular data structures.

> Sure, if you create your own data structure, you can make it as efficient
> as you like. Obviously the sum algorithm itself has to perform one
> addition per item, or O(N), which scales tolerably well. But each
> addition has a cost. If the cost is constant, then sum() as a whole
> remains O(N). But if the cost of addition varies with N, sum() degrades
> ba
>

The surprising part of sum() is not that the outer loop to do the sums
is O(N). It is hard to imagine any other implementation (without
parallelizing it).

The mildly surprising part of sum() is that is does add vs. add-in-
place, which leads to O(N) vs. O(1) for the inner loop calls, for
certain data structures, notably lists, even though none of the
intermediate results get used by the caller. For lists, you could
make a more efficient variant of sum() that clones the start value and

I could guess pretty confidently that the reason this optimization was
never tried is that sum() has always been intended to be used on
numerics, since other alternatives exist for strings (join), lists
(chain), and hand-coded data classes that support add-in-place (roll-
your-own loop).

The documentation is pretty clear on the intention that sum() is
intended for numbers:

http://docs.python.org/library/functions.html#sum

Except for strings, the docs are not explicit about efficiency
concerns for other data structures, or the fact that the reference

http://docs.python.org/library/functions.html#sum

Steven D'Aprano
Guest
Posts: n/a

 03-28-2010
On Sun, 28 Mar 2010 07:16:10 -0700, Steve Howell wrote:

> The mildly surprising part of sum() is that is does add vs. add-in-
> place, which leads to O(N) vs. O(1) for the inner loop calls, for
> certain data structures, notably lists, even though none of the
> intermediate results get used by the caller. For lists, you could make
> a more efficient variant of sum() that clones the start value and does

I have no doubt that you could make a version of sum for lists which is
more efficient than the existing one. After all, join more or less does
the same sort of thing, and it's very efficient. But don't think that add-
in-place is necessarily cheap. List appends are amortized O(1) each; if
you are adding M lists of N items each, that gives you O(M*N).

It's possible to improve the performance a tad if you can make multiple
appends in roughly constant time, which is what list.extend (probably?)
does, but only up to a point. Lists are over-allocated, but if you try to
add more items than there is room for, you need to make the list bigger,
and that means reallocating memory, which could easily be O(N**2) or
worse, depending on how good your OS's memory management is. Under Linux,
at least by default, malloc will never fail, but there's no guarantee how
long it will take to return. If the OOM killer has to start shutting down
other applications, and paging more and more memory to disk, eventually
malloc will return (or the system will core dump), but it could take a
while...

--
Steven

Steve Howell
Guest
Posts: n/a

 03-28-2010
On Mar 28, 8:17*am, Duncan Booth <(E-Mail Removed)> wrote:
> Steve Howell <(E-Mail Removed)> wrote:
> > The mildly surprising part of sum() is that is does add vs. add-in-
> > place, which leads to O(N) vs. O(1) for the inner loop calls, for
> > certain data structures, notably lists, even though none of the
> > intermediate results get used by the caller. *For lists, you could
> > make a more efficient variant of sum() that clones the start value and

>
> Doing add-in-place isn't the only way to make sum more efficient: if you
> assume that addition is associative (which of course the builtin sum can't)
> then you can form partial sums. e.g. instead of calculating:
>
> * (((((((a + b) + c) + d) + e) + f) + g) + h)
>
> you calculate:
>
> * (((a + b) + (c + d)) + ((e + f) + (g + h)))
>
> Obviously this requires more space than the naive sum, but not as much as
> you might at first expect: you only need to hold log(n) intermediates
> values at any time.
>

Yep, I did mention in my post that the outer loop does not *have* to
be O(N), if you can parallelize it. Apart from reducing
intermediates, the divide-and-conquer method does not reduce overall
computation time unless you have multiple processors, correct?

> > I could guess pretty confidently that the reason this optimization was
> > never tried is that sum() has always been intended to be used on
> > numerics, since other alternatives exist for strings (join), lists
> > (chain), and hand-coded data classes that support add-in-place (roll-
> > your-own loop).

>
> Doing it this way helps summing lists or strings (though not as much as
> str.join), but it also helps if you need to sum a long list of similarly
> sized floats as you'll get a more accurate answer.
>

Interesting! That makes sense. The docs for math.fsum() suggest that
partial sums are used to maintain precision.

http://docs.python.org/library/math.html#math.fsum

> faf92f532e/027cef7d4429aa3a
> for an earlier discussion of this, or just Google comp.lang.python for
> 'pairwise sum'.
>
> Here's the code I posted in that thread:
>
> def sumpairs(seq):
> * * tmp = []
> * * for i,v in enumerate(seq):
> * * * * if i&1:
> * * * * * * tmp[-1] = tmp[-1] + v
> * * * * * * i = i + 1
> * * * * * * n = i & -i
> * * * * * * while n > 2:
> * * * * * * * * t = tmp.pop(-1)
> * * * * * * * * tmp[-1] = tmp[-1] + t
> * * * * * * * * n >>= 1
> * * * * else:
> * * * * * * tmp.append(v)
> * * while len(tmp) > 1:
> * * * * t = tmp.pop(-1)
> * * * * tmp[-1] = tmp[-1] + t
> * * return tmp[0]
>
> and I claimed that my Python coded sumpairs function was faster than the
> builtin sum on a list of lists once you had more than about 210 items.
> I never did get round to rewriting it in C for a more realistic speed
> comparison: summing integers my Python version is about 60 times slower
> than the builtin.

Steve Howell
Guest
Posts: n/a

 03-28-2010
On Mar 28, 7:57*am, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
> On Sun, 28 Mar 2010 07:16:10 -0700, Steve Howell wrote:
> > The mildly surprising part of sum() is that is does add vs. add-in-
> > place, which leads to O(N) vs. O(1) for the inner loop calls, for
> > certain data structures, notably lists, even though none of the
> > intermediate results get used by the caller. *For lists, you could make
> > a more efficient variant of sum() that clones the start value and does

>
> I have no doubt that you could make a version of sum for lists which is
> more efficient than the existing one. After all, join more or less does
> the same sort of thing, and it's very efficient. But don't think that add-
> in-place is necessarily cheap. List appends are amortized O(1) each; if
> you are adding M lists of N items each, that gives you O(M*N).
>

O(M*N) is still cheaper than O(M*N*N).

> It's possible to improve the performance a tad if you can make multiple
> appends in roughly constant time, which is what list.extend (probably?)
> does, but only up to a point. Lists are over-allocated, but if you try to
> add more items than there is room for, you need to make the list bigger,
> and that means reallocating memory, which could easily be O(N**2) or
> worse, depending on how good your OS's memory management is. Under Linux,
> at least by default, malloc will never fail, but there's no guarantee how
> long it will take to return. If the OOM killer has to start shutting down
> other applications, and paging more and more memory to disk, eventually
> malloc will return (or the system will core dump), but it could take a
> while...
>

Even though extend() obviously has to do memory allocations along the
way itself, it is still more efficient than the alternative. No need
to speculate, you can measure these methods on your platform:

M = 10
N = 1000

def in_place(
start = [],
sublists = ([[None] * M]) * N
):
accum = start[:]
for sublist in sublists:
accum.extend(sublist)
return accum

def with_intermediates(
start = [],
sublists = ([[None] * M]) * N
):
accum = start
for sublist in sublists:
accum = accum + sublist
return accum

Patrick Maupin
Guest
Posts: n/a

 03-28-2010
On Mar 28, 10:17*am, Duncan Booth <(E-Mail Removed)>
wrote:
> Doing add-in-place isn't the only way to make sum more efficient: if you
> assume that addition is associative (which of course the builtin sum can't)
> then you can form partial sums. e.g. instead of calculating:

....
>
> Doing it this way helps summing lists or strings (though not as much as
> str.join), but it also helps if you need to sum a long list of similarly
> sized floats as you'll get a more accurate answer.

Also, partial sums would be a clear winner over add-in-place if
someone were dumb^H^H^H^Hnaive enough to use sum() on a long list of
tuples