Return to Video

06-28 Increasing Efficiency Solution

  • 0:00 - 0:06
    Here's what I did. I introduced two global variables--the previous hand and previous results.
  • 0:06 - 0:11
    I am making a cache, like a memoization cache, but it's only for one hand,
  • 0:11 - 0:13
    because we're only dealing with one hand at a time.
  • 0:13 - 0:18
    Then I say, we then find_prefixes if the hand that you were given is equal
  • 0:18 - 0:21
    to the previous hand, then return the previous results.
  • 0:21 - 0:25
    I'm only going to update the previous hand and the previous results
  • 0:25 - 0:28
    in the case where the prefix is the empty string.
  • 0:28 - 0:32
    And that's how I know I'm at the top level call when the prefix is the empty string.
  • 0:32 - 0:35
    For all the recursive calls, the prefix will be something else.
  • 0:35 - 0:39
    I'm only storing away the results when I'm at the top level call
  • 0:39 - 0:42
    and I'm updating previous hand and previous results.
  • 0:42 - 0:47
    With that, efficiency improvement to find prefixes, now when I do timedcalls
  • 0:47 - 0:52
    of row plays for this fairly complex row, it's only about a thousandth of a second.
  • 0:52 - 0:58
    If 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.
Title:
06-28 Increasing Efficiency Solution
Description:

Other units in this course below:
Unit 1:http://www.youtube.com/playlist?list=PL818D7B4539EED6D3
Unit 2:http://www.youtube.com/playlist?list=PLB470B7816A914D87
Unit 3:http://www.youtube.com/playlist?list=PL2C981397711BDD5C
Unit 4:http://www.youtube.com/playlist?list=PL66FC120367E358C0
Unit 5:http://www.youtube.com/playlist?list=PL17BE79F86C9283AA
Unit 6:http://www.youtube.com/playlist?list=PL7B0DE2C0104F814D
Unit 7:http://www.youtube.com/playlist?list=PL6AE83B25FC53CEEF

Q&A: http://www.youtube.com/playlist?list=PLB8CD9F4159903D84

To gain access to interactive quizzes, homework, programming assignments and a helpful community, join the class at http://www.udacity.com

more » « less
Team:
Udacity
Project:
CS212 - Design of Computer Programs
Duration:
01:03
Amara Bot added a translation

English subtitles

Revisions