CODEWITHSUNDEEP
pythonoptimization
WeaklyTyped
WeaklyTyped

Reputation: 1341

Optimising a simple mathematical calculation over list

I have a script where I am computing:

def sumsquared(arr):
    sum = 0
    idx = 0
    len = arr.__len__()
    while idx < (len - 1):
            sum = sum + (arr[idx] * arr[idx]) + (arr[idx+1] * arr[idx+1])
            idx = idx + 2

    return sum

The above function is called in a loop which populates two lists and calls this function twice: First time with a list of len ~ 1024 items and second time with len ~ 44100 items. The loop itself can run anywhere from 100 to 100000 times depending upon the input.

For a small sized input, cProfile based profiling informs me: 

ncalls  tottime  percall  cumtime  percall  filename:lineno(function)
---------------------------------------------------------------------
 2560   12.065   0.005    12.065    0.005    beat.py:8(sumsquared)

which is about 95% of the total running time for the script. Is there some way I can get some speed up on the function?

Upvotes: 0

Views: 153

Answers (4)

BrenBarn
BrenBarn

Reputation: 251398

Your function is very strange. All it does is compute the sum of the squares of the elements, except that it throws away the last element if there are an odd number of elements. You add them two at a time for some reason, but that doesn't affect the end result.

To make it faster, you could use numpy instead of writing your own function.

>>> x = np.array([1, 2, 3, 4, 5])
>>> sumsquared(x)
30
>>> (x[:2*(len(x)//2)]**2).sum()
30

In general, if you have lists of thousands of numbers, using numpy arrays instead is likely to bring a major performance gain.

Upvotes: 5

Raymond Hettinger
Raymond Hettinger

Reputation: 226346

This looks like a job for the itertools module:

def sumsquared(arr):
    s = sum(itertools.imap(operator.mul, arr, arr))
    return s - arr[-1] ** 2 if len(arr) & 1 else s

The use of sum, operator, and itertools will eliminate almost all of the pure python overhead.

Also, sum has been optimized to run at nearly C speed when the inputs are ints, floats, or some mix of the two. It is able to accumulate running totals without creating pure python objects for every intermediate subtotal.

Credit: Robert King for the idea of subtracting the final square when necessary.

One other note, if you're interested in obtaining high accuracy (i.e. minimizing loss of precision), consider using math.fsum instead of sum.

Upvotes: 3

John La Rooy
John La Rooy

Reputation: 304215

This is the fastest I can find

from itertools import imap
from operator import mul
def sumsquared(arr):
    return sum(imap(mul, arr, arr))

Upvotes: 2

Rusty Rob
Rusty Rob

Reputation: 17173

sum([i**2 for i in arr]) - (arr[-1]**2 if len(arr) % 2 else 0)

Upvotes: 1

Related Questions