2

What's the quickest way (without going into parallel processing) to find a sum of results of function calls in Python?

Imagine xlist is a list of values, the purpose is to transform each of them with f(x) and sum up. For now (keeping in mind "flat is always better") I have:

sum([f(x) for x in xlist])

This works fine, but my xlist is pretty large (~20000 float values) and this sum is called a few million times during the execution of my program, consuming most of the time resources. Is there a way to implement it in a more efficient fashion?

I don't mind adding C++ inclusions or whatever other methods you could think of, but would not want to change the structure of the whole program for the sake of it...

sashkello
  • 17,306
  • 24
  • 81
  • 109
  • 1
    If you have 20000 numbers and you are trying to operate on and sum them millions of times, why are you using Python and avoiding parallel processing? – jtbandes May 02 '13 at 07:17
  • Use generator instead of iterator as you said the xlist is pretty large. i.e sum((f(x) for x in xlist)) – Bhavish Agarwal May 02 '13 at 07:18
  • @jtbandes Because I wrote this program in 2 days and if it is successful, I can write a nice parallel C++ evaluation afterwards, but it will take a month at least. I just don't want to spend 2 hours waiting for it to run, if it is possible to cut it to say 1 hour... – sashkello May 02 '13 at 07:19
  • @sashkello If you are using this within a function, you can cache `sum` and `f` eg. `def g(sum=sum, f=f): return sum(imap(f, xlist))` which should save some global lookups – jamylak May 02 '13 at 07:47
  • @jtbandes Python is really fast at operating on numbers using `numpy` – jamylak May 02 '13 at 07:57

2 Answers2

6

Getting rid of the square brackets should do the trick.

sum(f(x) for x in xlist)

This will sum a generator expression, and removes the need to create a list that is stored in memory first. Rather it will sum the elements as it iterates through the generator.

In Python 3, using map (itertools.imap in Python 2) will be a bit faster.

import itertools
sum(itertools.imap(f, xlist))

A further optimization you could make (as the sum is going to be called a fair few times) would be to remove the overhead of using the . operator.

from itertools import imap
sum(imap(f, xlist))
Volatility
  • 31,232
  • 10
  • 80
  • 89
  • 1
    In addition to that, `map` is [claimed](http://stackoverflow.com/a/1247490/770830) to be marginally faster (or, maybe, `itertools.imap` for python2) – bereal May 02 '13 at 07:20
  • For me itertools.imap is ~20% quicker than generator (which is another 10% quicker than list sum). Great advice, thanks a lot - will be using it extensively in future. – sashkello May 02 '13 at 07:35
  • 1
    @Volatility The `sum` is called a few million times, so the global lookup to the `itertools` module first is not doing any good. `from itertools import imap` should be a bit faster. – jamylak May 02 '13 at 07:44
  • Thanks everyone! I'm accepting this answer because it's easy and does improve things considerably. – sashkello May 02 '13 at 08:00
2

I would recommend an aproach similar to Volatility's.

But also using a Memoization decorator. (only really useful if you expect multiple identical values)

def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret 
    return memodict().__getitem__

@memodict
def f(x):
    pass # your code

sum(f(x) for x in xlist)

source: Memodict

Community
  • 1
  • 1
Inbar Rose
  • 41,843
  • 24
  • 85
  • 131
  • The function is actually called within another function and has more than one argument. Would this be applicable in such case? – sashkello May 02 '13 at 07:28
  • 1
    You could always use another memoize decorator that handles multiple arguments, but in these cases I would reduce or re-factor your code to be as fast as possible, single argument functions that are called millions of times to calculate data is much faster than handling multiple function calls and such... if this is all contained inside a class or another function it would be faster. as locality is faster than globality in Python. – Inbar Rose May 02 '13 at 07:30
  • Thank you! I'll definitely be looking into decorators as it seems like a very interesting concept... You are also right, and I see now that there are a lot of ways to improve program by simply reshaffling the code and this is the first thing to do really. – sashkello May 02 '13 at 08:02