Name, Trace, and Efficiency (Week of Nov. 25th)

We learned about name and tracing on Monday. In python, every name contains a value, and every value refers to the address of the object. Also when python is searching for name, it goes in the order of local, nonlocal, global, and then built-in names. Professor also showed us an example of local, nonlocal, and global variable. Prior to this example, I never really understood what global does and I have never encounter nonlocal before. I found the python visualizer really helpful when going through the example, because it list what the variable is assigned to in different frame (eg. In global frame, spam is assigned to “global spam”, while in scope_test frame, spam is assigned to “nonlocal spam”).

After finishing the python memory model, Professor Heap started the topic of tracing method. I found tracing not too complicated for most of the function, as most of the functions are pretty straightforward. Determining the output of a function would not be very hard as long as you understood what the function is supposed to return. However, when tracing recursion function, Professor suggested that we should not trace too far. We should first trace the simplest non-recursive case. Then we should trace the next most complicate case, and plug in the results obtained from the simplest case, and repeat the previous steps.

On Wednesday, Professor Heap started off looking at the Fibonacci recursive function. Professor Heap pointed out that the function made a lot of redundant calls when computing the nth number in the Fibonacci sequence, especially when n is very large. However, if we could record each number in the sequence into a table, then the efficiency would be improved. Of course a lot of programmer had already realized this solution, and they called it memorization. Memorization records value into a table (dictionary usually), and when it is called, it would look up the corresponding value in the table. The original function is only run when the input is not in the table. After computing the output, it would be recorded into the table to prevent redundant calls. In this way, the efficiency can be improved by a lot; thus looking for large Fibonacci number would take as long anymore!