Return to Video

Testing Shuffles - Design of Computer Programs

  • 0:00 - 0:03
    [Norvig] Now I'm going to show you this program, test_shuffler,
  • 0:03 - 0:05
    that produces the output you just saw
  • 0:05 - 0:12
    to see if a shuffle program is correct, if it comes up with a balanced set of results.
  • 0:12 - 0:14
    So what am I going to do?
  • 0:14 - 0:18
    First I'm going to keep track of the counts of every result that comes back from the shuffler.
  • 0:18 - 0:21
    I'm going to start counts off as a default dictionary.
  • 0:21 - 0:25
    That means that its default value is the default value of integer, which is 0.
  • 0:25 - 0:27
    So the counts all start at 0.
  • 0:27 - 0:30
    And then I go from range(n), so n times,
  • 0:30 - 0:33
    and by default we're going to go 10000 shuffles.
  • 0:33 - 0:38
    We're going to make a list out of the deck that we get passed in.
  • 0:38 - 0:41
    The deck is just a string of characters. That's the simplest thing to show.
  • 0:41 - 0:45
    Then we're going to shuffle the input and then count the result.
  • 0:45 - 0:48
    And result here is a list of items.
  • 0:48 - 0:51
    We're going to join the list of items together back into a single string
  • 0:51 - 0:54
    to make them smaller and easy to deal with,
  • 0:54 - 0:56
    and then we just increment that count.
  • 0:56 - 1:00
    So abcd comes in, we make a list, we make the list abcd,
  • 1:00 - 1:07
    we shuffle that, maybe we get bcad, and then we increment the count for that result.
  • 1:07 - 1:11
    Now, we calculate the expected count, what we expect to get,
  • 1:11 - 1:16
    and that's 1 over the factorial of the number of items in the deck
  • 1:16 - 1:24
    because all n factorial where n is the length of the deck items are equally probable.
  • 1:24 - 1:27
    And so the expected count should be n times that.
  • 1:27 - 1:32
    And then we say that the result is okay if the counts for each item--
  • 1:32 - 1:36
    The ratio of the counts to the expected value should be about 1.
  • 1:36 - 1:42
    And we're going to say if it's within 0.9 and 1.1 of what we expect, then that's okay.
  • 1:42 - 1:47
    If any item doesn't have that, then it's not okay.
  • 1:47 - 1:49
    What we passed in as shuffler is a function,
  • 1:49 - 1:53
    and functions have a name attribute, so we're pulling out the name of the shuffler
  • 1:53 - 1:57
    and then we're just printing out the name of the shuffler, the deck we're shuffling,
  • 1:57 - 1:59
    and whether it's okay or not,
  • 1:59 - 2:05
    and then we print out the individual probabilities for each of the possible results.
  • 2:05 - 2:07
    And then I made another function, test_shufflers,
  • 2:07 - 2:10
    which takes a list of shufflers and a list of possible decks
  • 2:10 - 2:13
    and it applies the test to the cross product of them.
  • 2:13 - 2:17
    For every shuffler we test every deck and we print the result.
  • 2:17 - 2:20
    We saw that the function shuffle1 was not a good function,
  • 2:20 - 2:25
    so I'm trying to fix it up, and I have 2 attempts here called shuffle2 and shuffle3.
  • 2:25 - 2:27
    We can see what's going on here.
  • 2:27 - 2:31
    In shuffle2 it's almost the same as shuffle1,
  • 2:31 - 2:36
    except when I pick out 2 random indices to swap,
  • 2:36 - 2:39
    I'm only saying that swapped of i is true,
  • 2:39 - 2:41
    and I'm not saying that swapped of j is true.
  • 2:41 - 2:42
    Otherwise it's the same.
  • 2:42 - 2:46
    In shuffle3 I go through the deck.
  • 2:46 - 2:50
    Rather than have a while loop, I just go through the deck for each of the indices
  • 2:50 - 2:54
    and swap that index with something in the random range of N.
  • 2:54 - 2:58
    So in other words, we swap each of the elements in the deck
  • 2:58 -
    with any one of the other elements.
タイトル:
Testing Shuffles - Design of Computer Programs
概説:

dummy description

more » « less
Video Language:
English
Team:
Udacity
プロジェクト:
CS212 - Design of Computer Programs
Duration:
03:01

English subtitles

改訂 Compare revisions