Return to Video

Bad Shuffle - Design of Computer Programs

  • 0:00 - 0:05
    [Norvig] Now, by all means, you should use the library functions like random.shuffle.
  • 0:05 - 0:07
    That's what they're there for.
  • 0:07 - 0:09
    But I'm going to allow a little bit of a diversion here
  • 0:09 - 0:13
    because the shuffle algorithm is one that's important to me personally.
  • 0:13 - 0:19
    It was the first nontrivial algorithm that I came up with on my own when I was in high school
  • 0:19 - 0:24
    and one of the first cases where I saw that my teacher was just completely wrong.
  • 0:24 - 0:29
    Here's the algorithm that my teacher was trying to describe to me.
  • 0:29 - 0:34
    Of course, I went to high school in the Dark Ages before there was any Python,
  • 0:34 - 0:36
    so it wasn't written in exactly this language,
  • 0:36 - 0:39
    but I've translated it into Python to make sense to you.
  • 0:39 - 0:41
    Here's what the algorithm does.
  • 0:41 - 0:46
    It says we're going to keep track with an array of which items have been swapped so far,
  • 0:46 - 0:50
    and then until they've all been swapped at least once,
  • 0:50 - 0:55
    we're going to generate 2 random indices into that array and then swap them
  • 0:55 - 0:58
    and record the fact that they were both swapped
  • 0:58 - 1:02
    and keep going until all the items have been swapped at least once.
  • 1:02 - 1:04
    So it looks like this.
  • 1:04 - 1:08
    Again, we have this deck of cards
  • 1:08 - 1:13
    and then we have a parallel array of the same length
  • 1:13 - 1:15
    which tells us whether we've been swapped or not,
  • 1:15 - 1:20
    and that starts out as being all false, while this one starts out being cards.
  • 1:20 - 1:23
    And then we go through and we pick out random numbers.
  • 1:23 - 1:31
    So say we pick out I and J as being here and here,
  • 1:31 - 1:33
    and say we have a 9 of diamonds there.
  • 1:33 - 1:35
    Then we're going to just swap the 2.
  • 1:35 - 1:37
    And so we cross those out.
  • 1:37 - 1:43
    We now have the 7 of spades there and the 9 of diamonds there,
  • 1:43 - 1:45
    and we mark the 2 spots as being swapped.
  • 1:45 - 1:49
    So now this one is true and this one is true.
  • 1:49 - 1:53
    Those 2 spots have been swapped, and then we keep on going
  • 1:53 - 1:58
    until all the elements of swapped are all equal to true. Then we know we're done.
  • 1:58 - 2:02
    So that's what my teacher was trying to sell to me that day in high school.
  • 2:02 - 2:06
    I was sitting in the back, and I just woke up and I said,
  • 2:06 - 2:08
    "That can't be right."
  • 2:08 - 2:12
    I just had this visceral reaction that said, "I can see what the algorithm does,
  • 2:12 - 2:16
    "and I know it swaps everything, but it just seems too inefficient."
  • 2:16 - 2:21
    "It has this loop that keeps on going, and it's not a for loop, it's a while loop."
  • 2:21 - 2:26
    And it just seemed to me that it was possible that this loop could go forever.
  • 2:26 - 2:28
    Depending on the choice of random numbers,
  • 2:28 - 2:30
    this might never terminate, and that just seemed wrong.
  • 2:30 - 2:32
    It seemed like there was a much better way.
  • 2:32 - 2:37
    And in my head I came up with the shuffle algorithm that we showed before.
  • 2:37 - 2:40
    Knuth calls it Algorithm P for permutation.
  • 2:40 - 2:42
    It just seemed like that was the simple and correct way,
  • 2:42 - 2:46
    and this was just too complicated, and that really bothered me.
  • 2:46 - 2:49
    I thought that an algorithm should be guaranteed to terminate.
タイトル:
Bad Shuffle - Design of Computer Programs
概説:

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

English subtitles

改訂 Compare revisions