Reduce function calls

Question

I profiled my python program and found that the following function was taking too long to run. Perhaps, I can use a different algorithm and make it run faster. However, I have read that I can also possibly increase the speed by reducing function calls, especially when it gets called repeatedly within a loop. I am a python newbie and would like to learn how to do this and see how much faster it can get. Currently, the function is:

def potentialActualBuyers(setOfPeople,theCar,price):
 count=0
 for person in setOfPeople:
 if person.getUtility(theCar) >= price and person.periodCarPurchased==None:
 count += 1
 return count

where setOfPeople is a list of person objects. I tried the following:

 def potentialActualBuyers(setOfPeople,theCar,price):
 count=0
 Utility=person.getUtility
 for person in setOfPeople:
 if Utility(theCar) >= price and person.periodCarPurchased==None:
 count += 1
 return count

This, however, gives me an error saying local variable 'person' referenced before assignment Any suggestions, how I can reduce function calls or any other changes that can make the code faster.

Again, I am a python newbie and even though I may possibly be able to use a better algorithm, it is still worthwhile learning the answer to the above question.

Thanks very much.

***** EDIT *****

Adding the getUtility method:

 def getUtility(self,theCar):
 if theCar in self.utility.keys():
 return self.utility[theCar]
 else:
 self.utility[theCar]=self.A*(math.pow(theCar.mpg,self.alpha))*(math.pow(theCar.hp,self.beta))*(math.pow(theCar.pc,self.gamma))

return self.utility[theCar]

***** EDIT: asking for new ideas *****

Any ideas how to speed this up further. I used the method suggested by Alex to cut the time in half. Can I speed this further? Thanks.

• sosborn: The error refers to the fact that you reference person before you assign it in the enumerator. It should go after "for person in setOfPeople:" Also, when you say it takes to long to run, how do you quantify this? How long is it actually taking and how big is the set that you are running through? Premature optimization is the root of all evil.
• Marcelo Cantos: Precomputing the method reference is unlikely to buy you any speed-up. A look inside getUtility might yield some insight. Can you add the code to your question?
• PaulMcG: I too suspect that the actual logic of getUtility will outweigh the overhead of the function call. Before doing anything unnatural, see what options you have in getUtility.
• Jochen Ritzel: if theCar in self.utility.keys(): should be if theCar in self.utility:. Anyways, don't you have a database behind this? It can do the filtering much, much faster.
• Curious2learn: @THC4k: No I don't have a database. Are you saying I should update the status of period car purchased in a database and obtain the values which satisfy a particular criteria from there. Will writing to a database and getting information from there, not slow things down? Thanks

Answer 1

I doubt you can get much speedup in this case by hoisting the lookup of person.getUtility (by class, not by instances, as other instances have pointed out). Maybe...:

return sum(1 for p in setOfPeople
 if p.periodCarPurchased is None
 and p.getUtility(theCar) >= price)

but I suspect most of the time is actually spent in the execution of getUtility (and possibly in the lookup of p.periodCarPurchased if that's some fancy property as opposed to a plain old attribute -- I moved the latter before the and just in case it is a plain attribute and can save a number of the getUtility calls). What does your profiling say wrt the fraction of time spent in this function (net of its calls to others) vs the method (and possibly property) in question?

• jbochi: I think you mean and and not end
• Ponkadoodle: In python (atleast <3.0), 1+True = 2, False+1 = 1. So just use sum((p.periodCarPurchased is None and p.getUtility(theCar) >= price) for p in setOfPeople)
• Alex Martelli: @wallacoloo, that's also true in Python 3.*, but the result is not necessarily faster since you may be summing up a lot of 0s -- be sure to measure timing accurately before you pick one or the other.
• Curious2learn: @Alex, thanks for the suggestions. You are absolutely right...it makes sense to put the p.periodCarPurchased condition first. This change cut the time in half. Now the total time (variable tottime in the output of cprofile) in getUtility method is 1.76. Whereas tottime for the potentialActualBuyers function I have above is 12.361. That is, the potentialActualBuyers is still taking a lot of time. Though I have not yet tried the sum(...) approach that you have suggested.
• Alex Martelli: @curious, glad the switch helped so much -- the sum suggestions, both mine and the one in the comments, won't help as much, alas. Maybe there are implicit "fetch from db" operations going on and you could speed things up by fetching in bulk...?

Answer 2

Try instead (that's assuming all persons are of the same type Person):

Utility = Person.getUtility
for person in setOfPeople:
 if Utility (person, theCar) >= ...

Also, instead of == None using is None should be marginally faster. Try if swapping and terms helps.

• Curious2learn: Changing == None to is None reduced the tottime from about 13 seconds to 9 seconds. Pretty good, I think. Thanks!

Answer 3

Methods are just functions bound to an object:

 Utility = Person.getUtility
 for person in setOfPeople:
 if Utility(person, theCar) ...

This doesn't eliminate a function call though, it eliminates an attribute lookup.

• Curious2learn: This does not reduce the timing much. However, can you explain the difference between my method and this method. What does it exactly mean, when you say that it does not prevent function call but prevents attribute lookup. Thanks!

Answer 4

This one line made my eyes bleed:

 self.utility[theCar]=self.A*(math.pow(theCar.mpg,self.alpha))*(math.pow(theCar.hp,self.beta))*(math.pow(theCar.pc,self.gamma))

Let's make it legible and PEP8able and then see if it can be faster. First some spaces:

self.utility[theCar] = self.A * (math.pow(theCar.mpg, self.alpha)) * (math.pow(theCar.hp, self.beta)) * (math.pow(theCar.pc, self.gamma))

Now we can see there are very redundant parentheses; remove them:

self.utility[theCar] = self.A * math.pow(theCar.mpg, self.alpha) * math.pow(theCar.hp, self.beta) * math.pow(theCar.pc, self.gamma)

Hmmm: 3 lookups of math.pow and 3 function calls. You have three choices for powers: x ** y, the built-in pow(x, y[, z]), and math.pow(x, y). Unless you have good reason for using one of the others, it's best (IMHO) to choose x ** y; you save both the attribute lookup and the function call.

self.utility[theCar] = self.A * theCar.mpg ** self.alpha * theCar.hp ** self.beta * theCar.pc ** self.gamma

annnnnnd while we're here, let's get rid of the horizontal scroll-bar:

self.utility[theCar] = (self.A
 * theCar.mpg ** self.alpha
 * theCar.hp ** self.beta
 * theCar.pc ** self.gamma)

A possibility that would require quite a rewrite of your existing code and may not help anyway (in Python) would be to avoid most of the power calculations by taking logs everywhere and working with log_utility = log_A + log_mpg * alpha ...

• Curious2learn: How did you get the line breaks. Did you press the enter key? Thanks for your suggestions.
• John Machin: Enter key: Yes. Thanks: Have you noticed the up-pointing triangle at the top left of each answer? Ciick on this to up-vote an answer. Kind questioners up-vote all answers that they think useful, and accept (a big tick button) the answer they think most useful.
• Curious2learn: Thanks. I did not know you could use enter for linebreak in python in the middle of an expression. I up-vote answers all the time. Before doing yours, I was waiting for your reply about the enter key question.