# Summing all keys in the leaves of a tree

My program takes 35 sec to run example 2. How can I make my program faster?

def sum_keys(K, inputs, count=1):
A, B, M, L1, L2, L3, D, R = list(map(int, inputs))
x = ((A*K)+B)%M
y = ((A*K+2*B)%M)

if K < L1 or count == D:
my_list.append(K)
elif L1 <= K < L2:
sum_keys(x, inputs, count + 1)
elif L2 <= K < L3:
sum_keys(y, inputs, count + 1)
elif L3 <= K:
sum_keys(x, inputs, count + 1)
sum_keys(y, inputs, count + 1)

return sum(my_list)

inputs = inputstring.split()
A, B, M, L1, L2, L3, D, R = list(map(int, inputs))
x = ((A*R)+B)%M
y = ((A*R+2*B)%M)

if L1 <= R < L2:
return sum_keys(x, inputs)
elif L2 <= R < L3:
return sum_keys(y, inputs)
elif L3 <= R:
sum_keys(x, inputs)
return sum_keys(y, inputs)

my_list = []
if __name__ == '__main__':

• Why did you edit out the description of what this code does? – Simon Forsberg Apr 23 '16 at 14:33

I dislike your duplicate, near C&P, functions. The differences between the functions are:

• One splits the string.
• One doesn't append to the list.
• One uses R the other K to calculate x and y.

This means you can reduce the amount of code. If you make a function that changes R to K and splits the string, and you make a change to the other function to not add to the list on the first call.

You also want all A, B, etc and your my_list to be in this second functions scope. This means a closure is perfect!

You should also generate all the keys before calling sum. I done a profile of you code a significant amount of time was spent in sum.

You can also reduce your ifs. If you change K < L1 to just test against that, you can then test only against the upper limit on all the other ifs.

This should result in something like:

def read_input(input_string):
A, B, M, L1, L2, L3, D, R = map(int, input_string.split())
keys = []
def inner(K, count):
x = (A * K + B) % M
y = (A * K + 2 * B) % M
if count == D:
keys.append(K)
elif K < L1:
if count != 0:
keys.append(K)
elif K < L2:
inner(x, count + 1)
elif K < L3:
inner(y, count + 1)
else:
inner(x, count + 1)
inner(y, count + 1)
inner(R, 0)
return sum(keys)

import cProfile
cProfile.run('read_input("717 244 2069 280 300 450 20 699")')
print(read_input("717 244 2069 280 300 450 20 699"))
cProfile.run('read_input("31 17 43   5 15 23   5   30")')
print(read_input("31 17 43   5 15 23   5   30"))

    return sum(my_list)


You don't need to calculate the sum every time. Do it just when count is 1:

if count == 1:
return sum(my_list)


You have a recursive function, but your function doesn't care what itself returns. All it cares about is the side-effect: mylist.append(K). Just changing that (without any other changes) made the second example take less than a second. It would be best to return my_list and let whatever is calling the function decide if it wants the sum.

In two places you say:

A, B, M, L1, L2, L3, D, R = list(map(int, inputs))


You don't need to convert to a list just to iterate. That is what A, B, M, ... = ... does. Just use A, B, M, ... = map(int, inputs). That prevents the unnecessary storage of the numbers in memory.

Your naming is not ideal. How does someone looking at your program know what A, B, M, etc. are? They are just letters. To tell you the truth, I have no idea what this program is doing. If you had more descriptive names, it would be easier for future readers (possibly including you) to read the code. PEP 8, the Python style guide, recommends snake_case for normal variables.
It is better not to use global variables. I would suggest passing my_list as an argument to sum_keys() instead of relying on the existence of a global variable.
• @Joe: It gives no errors for me. It's true that a map object is not subscriptable, but we aren't trying that. Are you doing a test with map(...)[...]? – zondo Apr 20 '16 at 0:19