up vote 3 down vote favorite
1

I have 1-dimensional numpy array (array_) and a Python list (list_).

The following code works, but is inefficient because slices involve an unnecessary copy (certainly for Python lists, and I believe also for numpy arrays?):

result = sum(array_[1:])
result = sum(list_[1:])

What's a good way to rewrite that?

share|improve this question
94% accept rate
feedback

4 Answers

up vote 9 down vote accepted

Slicing a numpy array doesn't make a copy, as it does in the case of a list.

As a basic example:

import numpy as np
x = np.arange(100)
y = x[1:5]
y[:] = 1000
print x[:10]

This yields:

[   0 1000 1000 1000 1000    5    6    7    8    9]

Even though we modified the values in y, it's just a view into the same memory as x.

Slicing an ndarray returns a view and doesn't duplicate the memory.

However, it would be much more efficient to use array_[1:].sum() rather than calling python's builtin sum on a numpy array.

As a quick comparison:

In [28]: x = np.arange(10000)

In [29]: %timeit x.sum()
100000 loops, best of 3: 10.2 us per loop

In [30]: %timeit sum(x)
100 loops, best of 3: 4.01 ms per loop

Edit:

In the case of the list, if for some reason you don't want to make a copy, you could always use itertools.islice. Instead of:

result = sum(some_list[1:])

you could do:

result = sum(itertools.islice(some_list, 1, None))

In most cases this is overkill, though. If you're dealing with lists long enough that memory management is a major issue, then you probably shouldn't be using a list to store your values. (Lists are not designed or intended to store items compactly in memory.)

Also, you wouldn't want to do this for a numpy array. Simply doing some_array[1:].sum() will be several orders of magnitude faster and won't use any more memory than islice.

share|improve this answer
There must be something odd in your machine. According to my timings sum(x) is just some 5- 10% slower than x.sum() (on numpy 1.5.1). Thanks – eat May 5 '11 at 7:43
@eat - Are you using relatively large (>1000 elements) arrays? With short (~10 element) arrays, sum is only a few percent slower, but by the time you get up to >1000 elements, it's a matter of microseconds vs milliseconds. I've run it on 3 machines with different hardware and different versions of python & numpy. The times differ, but the scaling results are similar. They're both linear-time algorithms, but iterating through every element of a numpy array in python (which is what sum does) is much slower than iterating through every element of the memory buffer in C (which is what numpy does) – Joe Kington May 5 '11 at 15:08
No, same size as yours. I'll abuse the answer for a while to show my timings. Thanks – eat May 5 '11 at 15:49
how did you call command-line timeit in [29] and [30] from within the shell? Did you start a subshell? – max May 10 '11 at 15:43
@max - It's one of IPython's "magic" functions. ipython.scipy.org/moin It's just more convienent that putting a full timeit.timeit call with setup, etc... All it does is use the code previously run in the interactive shell as the setup kwarg to timeit.timeit. If you aren't already using IPython, have a look at it! It has many nice little features and macros! – Joe Kington May 10 '11 at 18:29
feedback
up vote 2 down vote

@Joe Kington (this is temporary answer to just show my timings, I'll remove it soon):

In []: x= arange(1e4)
In []: %timeit sum(x)
100000 loops, best of 3: 18.8 us per loop
In []: %timeit x.sum()
100000 loops, best of 3: 17.5 us per loop
In []: x= arange(1e5)
In []: %timeit sum(x)
10000 loops, best of 3: 165 us per loop
In []: %timeit x.sum()
10000 loops, best of 3: 158 us per loop
In []: x= arange(1e2)
In []: %timeit sum(x)
100000 loops, best of 3: 4.44 us per loop
In []: %timeit x.sum()
100000 loops, best of 3: 3.2 us per loop

As far as my numpy(1.5.1) source tells, sum(.) is just a wrapper for x.sum(.). Thus with larger inputs execution time is same (asymptotically) for sum(.) and x.sum(.).

Edit: This answer was intended to be just a temporary one, but actually it (and its comments) may indeed be useful to someone. So I'll just leave it as it is just now, until someone really request me to delete it.

share|improve this answer
1  
@eat: I think the OP's code and Joe's timings use the built-in sum() rather than numpy.sum(). This is only one of the pitfalls of using from numpy import *. – Sven Marnach May 5 '11 at 16:31
@eat - Yes, I was purposefully comparing python's sum to numpy's sum. I assumed the OP was referring to python's sum, as well. (He very well may not have been...) I have to agree with @Sven, here... This is exactly why from whatever import * is bad, and why it's especially bad in the case of a namespace as large as numpy's! :) – Joe Kington May 5 '11 at 16:42
Aha, OK that makes (kind of) sense. However I personally feel quite comfortable to work with IPython profile scipy, even tough it shadows pythons sum(.). (And since Joe was using IPython as well, I just misinterpreted the timings). BTW, should I still remove this answer or leave it (with comments as further clarification of OP's question)? Thanks – eat May 5 '11 at 17:30
Eh, I think it clarifies a point that other people might be confused on. I'd leave it if it were me... Your call, though, of course. – Joe Kington May 5 '11 at 17:39
2  
@eat: from numpy import * shadows all(), min(), max(), sum(), any(), abs() and round(). The biggest show-stoppers for me (even for interactive use) are any() and all() -- the numpy versions won't work with generator expressions. (I'd also suggest not to delete this answer.) – Sven Marnach May 5 '11 at 19:05
show 2 more comments
feedback
up vote 0 down vote

I don't find x[1:].sum() significantly slower than x.sum(). For lists sum(x) - x[0] is faster than sum(x[1:])(about 40% faster OMM).

share|improve this answer
feedback
up vote 4 down vote

My first instinct was the same as Joe Kington's when it comes to lists, but I checked, and on my machine at least, islice is consistently slower!

>>> timeit.timeit("sum(l[50:950])", "l = range(1000)", number=10000)
1.0398731231689453
>>> timeit.timeit("sum(islice(l, 50, 950))", "from itertools import islice; l = range(1000)", number=10000)
1.2317550182342529
>>> timeit.timeit("sum(l[50:950000])", "l = range(1000000)", number=10)
7.9020509719848633
>>> timeit.timeit("sum(islice(l, 50, 950000))", "from itertools import islice; l = range(1000000)", number=10)
8.4522969722747803

I tried a custom_sum and found that it was faster, but not by much:

>>> setup = """
... def custom_sum(list, start, stop):
...     s = 0
...     for i in xrange(start, stop):
...         s += list[i]
...     return s
... 
... l = range(1000)
... """
>>> timeit.timeit("custom_sum(l, 50, 950)", setup, number=1000)
0.66767406463623047

Furthermore, at larger numbers, it was slower by far!

>>> setup = setup.replace("range(1000)", "range(1000000)")
>>> timeit.timeit("custom_sum(l, 50, 950000)", setup, number=10)
14.185815095901489

I couldn't think of anything else to test. (Thoughts, anyone?)

share|improve this answer
Well, I wasn't claiming it was faster (there's no reason it would be). (I am surprised at how much slower it is, though...) I was claiming that it would use less memory, as it wouldn't make a copy of the list. It does do that. – Joe Kington May 5 '11 at 1:52
@Joe, sorry, I assumed you were talking about speed. – senderle May 5 '11 at 1:59
Well, re-reading my post, it certainly seems that way! I meant memory usage, but that wasn't at all clear from what I wrote. I'm an intrigued at how much difference there is... Oddly enough, with large enough lists, it appears that islice becomes faster again... You need ~1e7 elements, though. I'd imagine that at that point allocating new memory becomes a bottleneck. At any rate your post is certainly an interesting comparison! – Joe Kington May 5 '11 at 2:12
feedback

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.