
Cím:
Improving Optimal Solution  Design of Computer Programs

Leírás:

And here's my solution.

It's pretty much just copying out the version from Pwin and making sure it fits

with this new definition of the parameters.

So if me plus pending is greater than goal, then the probability is 1.

Otherwise, if you wins, the probability is 0.

Otherwise, we compute the probability of winning by rolling.

And if there are no pending, then we better roll,

because if we try to hold, we'll get stuck in an infinite loop.

So the return value is just the probability of rolling if there's no pending, if pending is 0.

If there is a pending, then we want to take the maximum result

of either rolling or dealing with holding.

How did we do?

We've defined our new Pwin2 function.

We can call that on the same initial state, and that will do all the computations

and cache them.

And it turns out it takes just about ¼ of a second,

so it's 3 times faster than the previous version that took ¾ of a second.

And if you see the probability that it computes, it's exactly the same.

And just to be sure, you should probably go through and pick out a bunch of other states

and test those.

I actually did it for all states and showed that all of them compute exactly the same function.

Then we can look at the size of the cache and see that that's about half as much

a little bit less than half as muchand that's where we're getting our speedup.

We're only computing half as much, so it goes a lot faster.

And there's always a choice.

When you get a speedup like this, you can put it in the bank or you can spend it.

So we can put it in the bank and say, "Now we can do in ¼ of a second

"what previously took ¾ of a second."

Or we can spend it. Here I'm spending it by increasing the goal to 60 rather than 40.

So much more computation to do.

Then I reload all my code so that the caches are flushed and do a timed call again,

and this time it's about ¾ of a second,

and I can do in the same amount of timewhich I could only handle a goal up to 40;

now I can handle a goal up to 60.

And note that the probability is a little bit lower than it was before.

If the goal is farther away, then the advantage of going first is a little bit less.