## ← Improving Optimal Solution - Design of Computer Programs

• 3 Követős
• 36 Sors

### Beágyazókód kérése x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=DUGTsRzbjdg" data-team="udacity"></div> ``` 1 Language

• Angol [en] eredeti

Showing Revision 3 created 05/24/2016 by Udacity Robot.

1. And here's my solution.
2. It's pretty much just copying out the version from Pwin and making sure it fits
3. with this new definition of the parameters.
4. So if me plus pending is greater than goal, then the probability is 1.
5. Otherwise, if you wins, the probability is 0.
6. Otherwise, we compute the probability of winning by rolling.
7. And if there are no pending, then we better roll,
8. because if we try to hold, we'll get stuck in an infinite loop.
9. So the return value is just the probability of rolling if there's no pending, if pending is 0.
10. If there is a pending, then we want to take the maximum result
11. of either rolling or dealing with holding.
12. How did we do?
13. We've defined our new Pwin2 function.
14. We can call that on the same initial state, and that will do all the computations
15. and cache them.
16. And it turns out it takes just about ¼ of a second,
17. so it's 3 times faster than the previous version that took ¾ of a second.
18. And if you see the probability that it computes, it's exactly the same.
19. And just to be sure, you should probably go through and pick out a bunch of other states
20. and test those.
21. I actually did it for all states and showed that all of them compute exactly the same function.
22. Then we can look at the size of the cache and see that that's about half as much--
23. a little bit less than half as much--and that's where we're getting our speed-up.
24. We're only computing half as much, so it goes a lot faster.
25. And there's always a choice.
26. When you get a speed-up like this, you can put it in the bank or you can spend it.
27. So we can put it in the bank and say, "Now we can do in ¼ of a second
28. "what previously took ¾ of a second."
29. Or we can spend it. Here I'm spending it by increasing the goal to 60 rather than 40.
30. So much more computation to do.
31. Then I reload all my code so that the caches are flushed and do a timed call again,
32. and this time it's about ¾ of a second,
33. and I can do in the same amount of time--which I could only handle a goal up to 40;
34. now I can handle a goal up to 60.
35. And note that the probability is a little bit lower than it was before.
36. If the goal is farther away, then the advantage of going first is a little bit less.