1 00:00:01,031 --> 00:00:03,743 In problem 4, we’ve given a list of n numbers and 2 00:00:03,743 --> 00:00:07,933 our task is to find the mode, within time therein. And 3 00:00:07,933 --> 00:00:10,440 there’s a lot of different ways to do this and – so, 4 00:00:10,440 --> 00:00:12,730 what I’ve done is, I’ve gone through and basically 5 00:00:12,730 --> 00:00:15,740 written five different ways of doing it. All variations 6 00:00:15,740 --> 00:00:17,827 on the theme really. In the first case, what we’re 7 00:00:17,827 --> 00:00:20,360 going to do is, we’re going to use a dictionary and 8 00:00:20,360 --> 00:00:22,849 when we iterate through the dictionary, keeping 9 00:00:22,849 --> 00:00:27,145 track of the element that has been seen the most 10 00:00:27,145 --> 00:00:30,378 often. So, here we’re just doing initialization, if we 11 00:00:30,378 --> 00:00:34,288 haven’t seen this value before we’ll create a key 12 00:00:34,288 --> 00:00:38,709 value pair and set its value to 1. If we have seen this 13 00:00:38,709 --> 00:00:41,675 key – this value before, we’ll just increment the value 14 00:00:41,675 --> 00:00:45,478 associated with it. As we’re going along, we can 15 00:00:45,478 --> 00:00:48,496 keep track of what the – what value we’ve seen the 16 00:00:48,496 --> 00:00:51,283 most. So, if the value that we’ve just updated is 17 00:00:51,283 --> 00:00:54,821 higher than the previous maximum value, we will set 18 00:00:54,821 --> 00:00:57,837 the current maximum value to be this current key 19 00:00:57,837 --> 00:01:00,469 value pair. As a result, by the time we finish this 20 00:01:00,469 --> 00:01:04,033 loop, which is 1 pass through the list, we will know 21 00:01:04,033 --> 00:01:07,149 the mode or we’ll know one of the values in the 22 00:01:07,149 --> 00:01:09,391 mode, if there’s more than one value that has the 23 00:01:09,391 --> 00:01:13,627 same number of appearances and we’ll just return 24 00:01:13,627 --> 00:01:16,300 that. There’s a lot of different ways you can do this 25 00:01:16,300 --> 00:01:19,900 and a slight variation of that, that let’s us shorten our 26 00:01:19,900 --> 00:01:21,913 code a little bit is when you can use the default 27 00:01:21,913 --> 00:01:24,710 dictionary that pipeline has. And what we’re doing 28 00:01:24,710 --> 00:01:28,282 here is, we’re saying basically that the first time you 29 00:01:28,282 --> 00:01:31,343 see a key, you’re going to give it an initial value 30 00:01:31,343 --> 00:01:34,808 using this int function, and it’s going to give it a value 31 00:01:34,808 --> 00:01:38,646 of zero. So that allows us to do, unless just get rid of 32 00:01:38,646 --> 00:01:41,880 this little bit of code here, that check to see whether 33 00:01:41,880 --> 00:01:44,476 or not the value existed already, which is a single 34 00:01:44,476 --> 00:01:47,399 look-up in a hash table basically. So, what we do 35 00:01:47,399 --> 00:01:52,144 now is we just increment the value by 1 regardless, 36 00:01:52,144 --> 00:01:55,206 and so the first time it sees it, it’ll use the default 37 00:01:55,206 --> 00:01:57,916 dictionary value of zero, add 1 to it and give us the 38 00:01:57,916 --> 00:02:00,417 value of 1, so it’s basically the same as what we’ve 39 00:02:00,417 --> 00:02:04,762 done before. And the rest of the code is the same as 40 00:02:04,762 --> 00:02:06,625 keeping track with the maximum value and returning 41 00:02:06,625 --> 00:02:08,036 it. Another thing you could do is you can use the – 42 00:02:08,036 --> 00:02:10,423 the built-in max feature of pipeline and again when 43 00:02:10,423 --> 00:02:16,876 we’re just doing incremental changes, we’re going to 44 00:02:16,876 --> 00:02:18,289 use the default dictionary again with an increment of 45 00:02:18,289 --> 00:02:20,279 value, but instead of keeping track as we go through 46 00:02:20,279 --> 00:02:20,531 what we’re going to do instead is just use max at the 47 00:02:20,531 --> 00:02:22,440 end, with a little Lambda function that basically 48 00:02:22,440 --> 00:02:30,316 returns the number of appearances that a given 49 00:02:30,316 --> 00:02:33,934 value had in the list and then returning the maximum 50 00:02:33,934 --> 00:02:36,671 key. And to show you that you can make it even 51 00:02:36,671 --> 00:02:40,167 more compact, you can actually use the set feature 52 00:02:40,167 --> 00:02:43,948 of pipeline. We take our initial value, our initial list, 53 00:02:43,948 --> 00:02:47,274 trade into a set which removes all duplicates and 54 00:02:47,274 --> 00:02:50,209 then use the same max function. And then if you 55 00:02:50,209 --> 00:02:53,407 want to be even more compact, you can even do it 56 00:02:53,407 --> 00:02:56,293 as a one liner, if you wish, and here what we’re 57 00:02:56,293 --> 00:02:58,677 doing is everything in one line, using the max 58 00:02:58,677 --> 00:03:02,673 function, we’re creating a set from our initial list, so 59 00:03:02,673 --> 00:03:05,409 that gives us all the unique values that we want. And 60 00:03:05,409 --> 00:03:08,563 then we’re using the Lambda function to say, give us 61 00:03:08,563 --> 00:03:13,432 account of the number of times this value appeared 62 00:03:13,432 --> 00:03:17,225 in our initial list, and then return that value. Now, we 63 00:03:17,225 --> 00:03:20,989 talked before – in class, we’ve talked before about 64 00:03:20,989 --> 00:03:23,724 performance. And this is great, this is one line 65 00:03:23,724 --> 00:03:27,856 occurred and that’s fairly understandable, but it’s 66 00:03:27,856 --> 00:03:31,003 actually not nearly as fast as some of the other 67 00:03:31,003 --> 00:03:34,113 things that we’ve done. There is a lot of repeat 68 00:03:34,113 --> 00:03:39,005 passes through the list that occurs because of the 69 00:03:39,005 --> 00:03:42,225 way that we’re doing this. And actually – probably 70 00:03:42,225 --> 00:03:45,095 the fastest one that I’ve seen so far is this one. Now 71 00:03:45,095 --> 00:03:47,094 there’s some people on the forums that may have 72 00:03:47,094 --> 00:03:50,849 faster ones and we’ve been using the comparison 73 00:03:50,849 --> 00:03:54,500 functions done by Anthony Pace to run test on it and 74 00:03:54,500 --> 00:03:57,036 this is, it’s fun to play with. So anyhow, any of these 75 00:03:57,036 --> 00:03:59,266 things worth – there’s lots of different ways to find 76 00:03:59,266 --> 00:04:02,649 the mode and a simple and straightforward pass 77 00:04:02,649 --> 00:04:06,592 through a dictionary is a nice way to do it. And it 78 00:04:06,592 --> 00:04:10,000 clearly finishes in time for data end.