Return to Video

ps4 4 solution

  • Niezsynchronizowane
    In problem 4, we’ve given a list of n numbers and
  • Niezsynchronizowane
    our task is to find the mode, within time therein. And
  • Niezsynchronizowane
    there’s a lot of different ways to do this and – so,
  • Niezsynchronizowane
    what I’ve done is, I’ve gone through and basically
  • Niezsynchronizowane
    written five different ways of doing it. All variations
  • Niezsynchronizowane
    on the theme really. In the first case, what we’re
  • Niezsynchronizowane
    going to do is, we’re going to use a dictionary and
  • Niezsynchronizowane
    when we iterate through the dictionary, keeping
  • Niezsynchronizowane
    track of the element that has been seen the most
  • Niezsynchronizowane
    often. So, here we’re just doing initialization, if we
  • Niezsynchronizowane
    haven’t seen this value before we’ll create a key
  • Niezsynchronizowane
    value pair and set its value to 1. If we have seen this
  • Niezsynchronizowane
    key – this value before, we’ll just increment the value
  • Niezsynchronizowane
    associated with it. As we’re going along, we can
  • Niezsynchronizowane
    keep track of what the – what value we’ve seen the
  • Niezsynchronizowane
    most. So, if the value that we’ve just updated is
  • Niezsynchronizowane
    higher than the previous maximum value, we will set
  • Niezsynchronizowane
    the current maximum value to be this current key
  • Niezsynchronizowane
    value pair. As a result, by the time we finish this
  • Niezsynchronizowane
    loop, which is 1 pass through the list, we will know
  • Niezsynchronizowane
    the mode or we’ll know one of the values in the
  • Niezsynchronizowane
    mode, if there’s more than one value that has the
  • Niezsynchronizowane
    same number of appearances and we’ll just return
  • Niezsynchronizowane
    that. There’s a lot of different ways you can do this
  • Niezsynchronizowane
    and a slight variation of that, that let’s us shorten our
  • Niezsynchronizowane
    code a little bit is when you can use the default
  • Niezsynchronizowane
    dictionary that pipeline has. And what we’re doing
  • Niezsynchronizowane
    here is, we’re saying basically that the first time you
  • Niezsynchronizowane
    see a key, you’re going to give it an initial value
  • Niezsynchronizowane
    using this int function, and it’s going to give it a value
  • Niezsynchronizowane
    of zero. So that allows us to do, unless just get rid of
  • Niezsynchronizowane
    this little bit of code here, that check to see whether
  • Niezsynchronizowane
    or not the value existed already, which is a single
  • Niezsynchronizowane
    look-up in a hash table basically. So, what we do
  • Niezsynchronizowane
    now is we just increment the value by 1 regardless,
  • Niezsynchronizowane
    and so the first time it sees it, it’ll use the default
  • Niezsynchronizowane
    dictionary value of zero, add 1 to it and give us the
  • Niezsynchronizowane
    value of 1, so it’s basically the same as what we’ve
  • Niezsynchronizowane
    done before. And the rest of the code is the same as
  • Niezsynchronizowane
    keeping track with the maximum value and returning
  • Niezsynchronizowane
    it. Another thing you could do is you can use the –
  • Niezsynchronizowane
    the built-in max feature of pipeline and again when
  • Niezsynchronizowane
    we’re just doing incremental changes, we’re going to
  • Niezsynchronizowane
    use the default dictionary again with an increment of
  • Niezsynchronizowane
    value, but instead of keeping track as we go through
  • Niezsynchronizowane
    what we’re going to do instead is just use max at the
  • Niezsynchronizowane
    end, with a little Lambda function that basically
  • Niezsynchronizowane
    returns the number of appearances that a given
  • Niezsynchronizowane
    value had in the list and then returning the maximum
  • Niezsynchronizowane
    key. And to show you that you can make it even
  • Niezsynchronizowane
    more compact, you can actually use the set feature
  • Niezsynchronizowane
    of pipeline. We take our initial value, our initial list,
  • Niezsynchronizowane
    trade into a set which removes all duplicates and
  • Niezsynchronizowane
    then use the same max function. And then if you
  • Niezsynchronizowane
    want to be even more compact, you can even do it
  • Niezsynchronizowane
    as a one liner, if you wish, and here what we’re
  • Niezsynchronizowane
    doing is everything in one line, using the max
  • Niezsynchronizowane
    function, we’re creating a set from our initial list, so
  • Niezsynchronizowane
    that gives us all the unique values that we want. And
  • Niezsynchronizowane
    then we’re using the Lambda function to say, give us
  • Niezsynchronizowane
    account of the number of times this value appeared
  • Niezsynchronizowane
    in our initial list, and then return that value. Now, we
  • Niezsynchronizowane
    talked before – in class, we’ve talked before about
  • Niezsynchronizowane
    performance. And this is great, this is one line
  • Niezsynchronizowane
    occurred and that’s fairly understandable, but it’s
  • Niezsynchronizowane
    actually not nearly as fast as some of the other
  • Niezsynchronizowane
    things that we’ve done. There is a lot of repeat
  • Niezsynchronizowane
    passes through the list that occurs because of the
  • Niezsynchronizowane
    way that we’re doing this. And actually – probably
  • Niezsynchronizowane
    the fastest one that I’ve seen so far is this one. Now
  • Niezsynchronizowane
    there’s some people on the forums that may have
  • Niezsynchronizowane
    faster ones and we’ve been using the comparison
  • Niezsynchronizowane
    functions done by Anthony Pace to run test on it and
  • Niezsynchronizowane
    this is, it’s fun to play with. So anyhow, any of these
  • Niezsynchronizowane
    things worth – there’s lots of different ways to find
  • Niezsynchronizowane
    the mode and a simple and straightforward pass
  • Niezsynchronizowane
    through a dictionary is a nice way to do it. And it
  • Niezsynchronizowane
    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