Return to Video

ps4 4 solution

  • 0:01 - 0:04
    In problem 4, we’ve given a list of n numbers
  • 0:04 - 0:06
    and our task is to find the mode, within time
  • 0:06 - 0:09
    Theta (n). And there’s a lot of different ways to
  • 0:09 - 0:11
    do this and – so, what I’ve done is, I’ve gone
  • 0:11 - 0:14
    through and basically written five different ways
  • 0:14 - 0:17
    of doing it. All variations of the theme really. In
  • 0:17 - 0:18
    the first case, what we’re going to do is, we’re
  • 0:18 - 0:21
    going to use a dictionary and when we iterate
  • 0:21 - 0:24
    through the dictionary, keeping track of the
  • 0:24 - 0:28
    element that has been seen the most often. So,
  • 0:28 - 0:32
    here we’re just doing initialization, if we haven’t
  • 0:32 - 0:34
    seen this value before we’ll create a key value
  • 0:34 - 0:39
    pair and set its value to 1. If we have seen this
  • 0:39 - 0:42
    key – this value before, we’ll just increment the
  • 0:42 - 0:45
    value associated with it. As we’re going along,
  • 0:45 - 0:48
    we can keep track of what the value – what
  • 0:48 - 0:50
    value we’ve seen the most. So, if the value that
  • 0:50 - 0:53
    we’ve just updated is higher than the previous
  • 0:53 - 0:55
    maximum value, we will set the current
  • 0:55 - 0:58
    maximum value to be this current key value
  • 0:58 - 1:01
    pair. As a result, by the time we finish this loop,
  • 1:01 - 1:04
    which is 1 pass through the list, we will know
  • 1:04 - 1:07
    the mode or we’ll know one of the values in the
  • 1:07 - 1:09
    mode, if there’s more than one value that has
  • 1:09 - 1:13
    the same number of appearances and we’ll just
  • 1:13 - 1:15
    return that. There’s a lot of different ways you
  • 1:15 - 1:18
    can do this and a slight variation of that, that
  • 1:18 - 1:21
    let’s us shorten our code a little bit is when you
  • 1:21 - 1:24
    can use the default dictionary that Python has.
  • 1:24 - 1:26
    And what we’re doing here is, we’re saying
  • 1:26 - 1:29
    basically that the first time you see a key, you’re
  • 1:29 - 1:33
    going to give it an initial value using this int
  • 1:33 - 1:36
    function, and it’s going to give it a value of zero.
  • 1:36 - 1:38
    So what that allows us to do, it lets us get rid of
  • 1:38 - 1:42
    this little bit of code here, that check to see
  • 1:42 - 1:44
    whether or not the value existed already, which
  • 1:44 - 1:47
    is a single look-up in a hash table basically. So,
  • 1:47 - 1:50
    what we do now is we just increment the value
  • 1:50 - 1:54
    by 1 regardless, and so the first time it sees it,
  • 1:54 - 1:57
    it’ll use the default dictionary value of zero, add
  • 1:57 - 1:59
    1 to it and give us the value of 1, so it’s
  • 1:59 - 2:01
    basically the same as what we’ve done before.
  • 2:01 - 2:02
    And the rest of the code is the same, just
  • 2:02 - 2:04
    keeping track of the maximum value and
  • 2:04 - 2:08
    returning it. Another thing you could do is you
  • 2:08 - 2:11
    can use the – the built-in max feature of Python
  • 2:11 - 2:13
    and again when we’re just doing incremental
  • 2:13 - 2:15
    changes, we’re going to use the default
  • 2:15 - 2:17
    dictionary again, we’re going to increment the
  • 2:17 - 2:20
    value, but instead of keeping track as we go
  • 2:20 - 2:22
    through, what we’re going to do instead is do
  • 2:22 - 2:23
    see this max at the end, with a little lambda
  • 2:23 - 2:28
    function that basically returned the number of
  • 2:28 - 2:32
    appearances that a given value had in the list
  • 2:32 - 2:36
    and then returning the maximum key. And to
  • 2:36 - 2:38
    show you that you can make it even more
  • 2:38 - 2:40
    compact, you can actually use the set feature of
  • 2:40 - 2:45
    Python. Pick our initial value, our initial list, turn
  • 2:45 - 2:47
    it into a set which removes all duplicates and
  • 2:47 - 2:50
    then use the same max function. And then if
  • 2:50 - 2:53
    you want to be even more compact, you can
  • 2:53 - 2:56
    even do it as a one liner, if you wish, and here
  • 2:56 - 2:58
    what we’re doing is everything in one line, using
  • 2:58 - 3:01
    the max function, we’re creating a set from our
  • 3:01 - 3:04
    initial list, so that gives us all the unique values
  • 3:04 - 3:07
    that we want. And then we’re using the lambda
  • 3:07 - 3:10
    function to say, give us a count of the number
  • 3:10 - 3:15
    of times this value appeared in our initial list,
  • 3:15 - 3:18
    and then return that value. Now, we talked
  • 3:18 - 3:21
    before – in class, we’ve talked before about
  • 3:21 - 3:24
    performance. And this is great, this is one-liner
  • 3:24 - 3:28
    code and that’s fairly understandable, but it’s
  • 3:28 - 3:31
    actually not nearly as fast as some of the other
  • 3:31 - 3:36
    things that we’ve done. There is a lot of repeat
  • 3:36 - 3:38
    passes through the list that occurs because of
  • 3:38 - 3:41
    the way that we’re doing this. And actually –
  • 3:41 - 3:44
    probably the fastest one that I’ve seen so far is
  • 3:44 - 3:46
    this one. Now there are some people on the
  • 3:46 - 3:49
    forums that may have faster ones and we’ve
  • 3:49 - 3:52
    been using the comparison functions done by
  • 3:52 - 3:55
    Anthony Pace to run test on it and this is – it’s
  • 3:55 - 3:57
    fun to play with. So anyhow, any of these things
  • 3:57 - 4:00
    work – there’s lots of different ways to find the
  • 4:00 - 4:03
    mode and a simple and straightforward pass
  • 4:03 - 4:07
    through a dictionary is a nice way to do it.
  • 4:07 - 4:10
    And it clearly finishes in time for Theta(n).
Tytuł:
ps4 4 solution
Opis:

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS215 - Intro to Algorithms
Duration:
04:10
Udacity Robot edited angielski subtitles for 04ps-01 Finding the Mode
podsinprint_user1 edited angielski subtitles for 04ps-01 Finding the Mode
podsinprint_user1 edited angielski subtitles for 04ps-01 Finding the Mode
podsinprint_user1 added a translation

English subtitles

Revisions Compare revisions