Return to Video

ps4 4 solution

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

This is a solution video for Udacity CS215 problem set 4, problem 4.

Find the mode of a list in time Theta(n).

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