0

Before showing my problem, I fully understand that functions can change mutable parameters passed through it. In my case, a terminated dictionary's values can still be accessed.

I'm doing the Pascal triangle problem and I have a recursive function like this:

def get_element( i :int, k: int, cache: dict[str, int] = {}) -> int:
global count
if (i == 3 and k == 2):
    count+=1
'''get the element at i'th row and k'th column

cache -- a dict used to store precomputed values. If it isn't provided, an empty dict will be created to boost performance'''
if i == 1 or k == 1 or k == i:
    cache[i, k] = 1
    return 1
if (i, k) in cache:
    return cache[i, k]
temp = get_element(i - 1, k - 1, cache) + get_element(i - 1, k, cache)
cache[i, k] = temp
return temp

def _get_triangle(num_lines: int, triangle = []) -> list:
'''Return a list of <num_lines> lists of elements on each line'''
triangle = []
precomputed = {} # To store precomputed values
for line in range (1, num_lines + 1):
    elems_in_line = []
    for elem in range (1, line + 1):
        elems_in_line.append(get_element(line, elem))
    triangle.append(elems_in_line)
return triangle

(The first function has a variable count used to count the number of time get_element(3, 2) is called (for debug purpose). )

As far as I know, without precomputed's being passed to get_element(), each time the _get_triangle() function want to compute another element, every computed values will be calculated again. However, I find that passing precomputed doesn't help boost perfomance at all. In fact sometimes it slows the program down:

import time
start = time.time()
_get_triangle(5000)
print('Execution time: {} ms'.format(time.time() - start))
print('Number of call: {}'.format(count))

Output:

Execution time: 20.584648847579956 s
Number of call: 3

With precomputed's being passed through elems_in_line.append(get_element(line, elem, cache = precomputed)):

Execution time: 21.495153665542603 ms
Number of call: 3

Slightly worse performance because of additional dictionary assignment and the same number of time that get_element(3, 2) is called (the first one on get_element(3, 2), 2nd time on get_element(4, 2) and the 3rd on get_element(4, 3)). My question is, how can that happen? Is the cache variable somehows stays alive after the function that generated it was killed (VSCode debug mode said "no")? Or there are other answers for the fact that precalculated values are still accessable after the dictionary that stored it was killed?

TrickyWhiteCat
  • 1
  • 1
  • `cache` and `triangle` may be function parameters, but the default values persist between calls because the functions themselves hold references to them. – chepner Apr 05 '22 at 14:41
  • One way to think about it: functions are objects. Default arguments are attributes of these objects. Even when the execution of one function call terminates, the function object is still there (so that you can call it gain). Since the function object is still there, its attributes are still there too. – Stef Apr 05 '22 at 15:12

0 Answers0