06-28 Increasing Efficiency Solution
0:00 - 0:06Here's what I did. I introduced two global variables--the previous hand and previous results.
0:06 - 0:11I am making a cache, like a memoization cache, but it's only for one hand,
0:11 - 0:13because we're only dealing with one hand at a time.
0:13 - 0:18Then I say, we then find_prefixes if the hand that you were given is equal
0:18 - 0:21to the previous hand, then return the previous results.
0:21 - 0:25I'm only going to update the previous hand and the previous results
0:25 - 0:28in the case where the prefix is the empty string.
0:28 - 0:32And that's how I know I'm at the top level call when the prefix is the empty string.
0:32 - 0:35For all the recursive calls, the prefix will be something else.
0:35 - 0:39I'm only storing away the results when I'm at the top level call
0:39 - 0:42and I'm updating previous hand and previous results.
0:42 - 0:47With that, efficiency improvement to find prefixes, now when I do timedcalls
0:47 - 0:52of row plays for this fairly complex row, it's only about a thousandth of a second.
0:52 - 0:58If I had a complete board that was similarly complex and say fifteen rows or so in the board,
0:58 -then it'd still be around one or two hundredths of a second and that's pretty good performance.
- 06-28 Increasing Efficiency Solution
Other units in this course below:
To gain access to interactive quizzes, homework, programming assignments and a helpful community, join the class at http://www.udacity.com
- CS212 - Design of Computer Programs
|Amara Bot added a translation|