Optimizing dictionary loop summing values

Question

I have a method that takes a nested dict input_dict

final = 0
for key, value in input_dict[self.state][self.city].iteritems():
    age = self._get_age(key)
    if (age > 0 and age < MAX_VAL):
      final += value  * self.lookup[key][age] * self.multiplier

return final

This runs in around .03 seconds, but given that in an example execution it gets called >10k times, it winds up being bottleneck and is responsible for about 50% of the runtime. Assuming I can't reduce the total number of times the method is called, does anyone have suggestions on how to improve this?

Takes a date `period`: `return (self.current_period - period) / 7` — ARB, Dec 31 '18 at 20:35
`input_dict` has keys which are dates, so each key is the argument to `self._get_age(key)` — ARB, Dec 31 '18 at 20:38

score 1 · Answer 1 · answered Jan 01 '19 at 20:59

Perhaps consider something like the following-

current_period = self.current_period - (self.current_period % 7)
MIN_VALUE = current_period - 7 * MAX_VALUE
return self.multiplier * sum(value * self.lookup[key][self._get_age(key)]
    for key, value in input_dict[self.state][self.city].iteritems()
    if MIN_VALUE < key < current_period
)

Here I pull the multiplication by self.multiplier out of the loop, and replace the comparison 0 < age < MAX_VALUE with an equivalent comparison of precomputed values, obtained by substituting age with your _get_age() method described in the comments and solving for key. This allows us to skip the function call + extra computations for cases where age <= 0 or age >= MAX_VALUE, and incurs no extra cost (save for computing the 2 variables outside the loop) over the original if 0 < age < MAX_VALUE. Additionally, this allows us to make use of the builtin sum() function, which is typically faster than summing via a for loop, but without creating a separate generator as in qxz's answer.

Note that I assume (self.current_period - period) in your _get_age() method is an integer, and so / 7 floors the result in Python-2.x. If this is not the case, remove the - (self.current_period % 7) from the current_period assignment for equivalent functionality.

qxz · Answer 2 · 2018-12-31T20:54:01.543

-1

The built-in sum function is typically faster than writing out a for loop. (See this question.) In your case, you could construct a generator expression of the values to be summed, and then pass that to sum:

items = (
    (key,value,self._get_age(key))
    for key,value in input_dict[self.state][self.city].iteritems()
)
return sum(
    value * self.lookup[key][age] * self.multiplier
    for key,value,age in items
    if 0 < age < MAX_VAL
)

edited Dec 31 '18 at 20:54

answered Dec 31 '18 at 20:50

qxz

3,814
1
14
29

I believe you could use chained comparison, do not know if it will be faster, but is more *pythonic* – Dani Mesejo Dec 31 '18 at 20:52
Well, `sum` is generally fast when using it on built-in data-types, generator expressions are typically slow. I bet a for-loop is faster. – juanpa.arrivillaga Dec 31 '18 at 20:54
Maybe replacing the generator expressions with list comprehension would be faster? – qxz Dec 31 '18 at 21:02
That would not scale well, you have to build *a list*. Although I think it will be faster for even moderately smalish list sizes, e.g. thousands or even ten thousands. However, then you add linear space complexity to something that can take constant space. Might not be an issue... – juanpa.arrivillaga Dec 31 '18 at 21:05

Optimizing dictionary loop summing values

2 Answers2