English subtitles

← ps4 4 solution

Get Embed Code
3 Languages

Showing Revision 4 created 05/25/2016 by Udacity Robot.

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