Dynamic Programming

Our recursive algorithm for computing Fibonacci numbers may look elegant, but that doesn't mean it's efficient. For example, when computing the fourth term in the sequence, it calculates the value for both the second and third terms. Likewise, when calculating the value of the third term in the sequence, it calculates the value for the first and second terms. This isn't ideal, as the second term in the sequence was already being calculated in order to get the fourth term. Dynamic programming will help us to address this problem by ensuring you break down the problem into the appropriate subproblems, and never solve the same subproblem twice.

Exercise 52: Summing Integers

In this exercise, you write a sum_to_n function to sum integers up to n. You store the results in a dictionary, and the function will use the stored results to return the answer in fewer iterations. For example, if you already know the sum of integers up to 5 is 15, you should be able to use this answer when computing the sum of integers up to 6:

1. Create a new dynamic.py Python file.
2. Write a sum_to_n function that starts with result = 0, and an empty dictionary for saving results:

   stored_results = {}

   def sum_to_n(n):

       result = 0

3. Add in a loop that computes the sum, returns the result, and stores the result in our dictionary:

   stored_results = {}

   def sum_to_n(n):

       result = 0

       for i in reversed(range(n)):

           result += i + 1

       stored_results[n] = result

       return result

4. Finally, extend the function further by checking in each loop whether you already have a result for this number; if so, use the stored result and exit the loop:

   stored_results = {}

   def sum_to_n(n):

       result = 0

       for i in reversed(range(n)):

           if i + 1 in stored_results:

               print('Stopping sum at %s because we have previously computed it' % str(i + 1))

               result += stored_results[i + 1]

               break

           else:

               result += i + 1

       stored_results[n] = result

       return result

5. Test the function in a Python shell to find the sum of integers up to 5:

   sum_to_n(5)

   You should get the following output:

   15

   Now, test the function once again to find the sum of integers up to 6.

   sum_to_n(6)

   You should get the following output:

Figure 3.26: Stopping early with saved results

In this exercise, you were able to reduce the number of steps in our code using dynamic programming to find the sum of integers up to n. The results were stored in a dictionary, and the function uses the stored result to output the answer in fewer iterations.

Timing Your Code

One measure of code efficiency is the actual time taken for your computer to execute it. In the examples given so far in this chapter, the code will execute too quickly to gauge any difference in the various algorithms. There are a few methods with which we can time programs in Python; you will focus on using the time module from the standard library.

Exercise 53: Timing Your Code

In this exercise, you will calculate the time taken to execute the function in the previous exercise:

1. Open the dynamic.py file created in the previous exercise.

   Add the following import at the top of the file:

   import time

2. Modify the function to calculate the time at the start, and print out the time elapsed at the end:

   stored_results = {}

   def sum_to_n(n):

       start_time = time.perf_counter()

       result = 0

       for i in reversed(range(n)):

           if i + 1 in stored_results:

               print('Stopping sum at %s because we have previously computed it' % str(i + 1))

               result += stored_results[i + 1]

               break

           else:

               result += i + 1

       stored_results[n] = result

       print(time.perf_counter() - start_time, "seconds")

3. Open a Python shell, import your new function, and try running an example with a large number:

   sum_to_n(1000000)

   You should get the following output:

   

   Figure 3.27: Timing our code

4. Rerun the same code in the shell:

   sum_to_n(1000000)

   You should get the following output:

Figure 3.28: Speeding up the execution with dynamic programming

Note

In the preceding example, the function returned the value faster by simply looking up the stored value in the dictionary.

Activity 12: The Fibonacci Function with Dynamic Programming

Your colleague has tried to use the code written in Activity 11, The Fibonacci Function with Recursion, and they notice that it is too slow when computing large Fibonacci numbers. They ask you to write a new function that can compute large Fibonacci numbers quickly.

In this activity, you will use dynamic programming to avoid the inefficient recursive loops that you implemented in Activity 11, The Fibonacci Function with Recursion.

The steps to do this are as follows:

1. Open the fibonacci.py file created in Activity 10, The Fibonacci Function with Iteration.
2. Define a fibonacci_dynamic function, which takes a single positional argument representing the number in the sequence that you want to return. Try starting with the fibonacci_recursive function from the previous activity and storing the results in a dictionary as the recursions are performed.
3. Try running a few examples in a Python shell:

   from fibonacci import fibonacci_recursive

   fibonacci_dynamic(3)

   You should get the following output:

   2

4. Note that if you try to use our recursive or iterative functions to compute the 100th Fibonacci number, they will be too slow and will never finish executing (unless you're willing to wait a few years).

   Note

   The solution for this activity is available on page 532.