Ever since we talked about memoization, I have been wondering about how to optimize tour_of_four_stools method in Assignment 1, tour.py file. My original approach was to use a method which would generate the lowest k value for the function, k being a number that gives the lowest number of moves for the equation : [2*k - 1 + 2*tour_of_four_stools(n - k)]. When I was doing preliminary testing that would calculate the optimal number of moves, I was able to reach up to a million cheeses and it would still calculate the answer in a second. However, when I actually implemented it in the assignment, it would not calculate the moves after 1000 cheeses. I was initially thinking of a bottom up approach, but it was actually less efficient than my recursive approach. Of course, I wasn't using the function which actually sped things up for my recursive tour_of_four_stools method, which is the generate_lowest_k function.
Now, generate_lowest_k generated a list of k values for the equation mentioned previously such that the number at index (k-1) of the list lowest_k would be the optimal k for the lowest number for that equation. The pattern being 1,1,2,2,2,3,3,3,3... and so on. Now, I thought of two approaches of possibly speeding up tour_of_four_stools function. The first is to generate all the answers from 1 to n and just use lowest_k to pick the ideal two numbers from two separate lists, one for 2*k - 1, and the other from 2*tour_of_four_stools(n - k). 2*k - 1 list will be of length k to make things more efficient and the other will be of length (n - k). I am going to think of some more ways of optimizing this algorithm as I am not completely convinced that this will be faster than my previous approach.
No comments:
Post a Comment