61–70 of 189 posts
The "Split the array into subarrays of length 5, now sorting all of the arrays is O(n) instead of O(n log n)" feels like cheating to me
I found this part of the code quite funny: # If there are Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1] [1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
In practice you might also want to use a O(n^2) algorithm like insertion sort under some threshold.
I wonder what's the reason of picking groups of 5 elements instead of 2 or 8.
2. One and three are probably too small
Earlier quoted context omitted.
Do you mean topK rather than median, for K small? You certainly cannot build a heap with trillions of items in it.
No, I mean median. Here is an article describing a very similar problem since I can’t link to the leetcode version: https://www.geeksforgeeks.org/median-of-stream-of-running-in...
> The Space required to store the elements in Heap is O(n).
I don't think this algorithm is suitable for trillions of items.
The "Split the array into subarrays of length 5, now sorting all of the arrays is O(n) instead of O(n log n)" feels like cheating to me
return l[len(l) / 2] I'm not a Python expert, but doesn't the `/` operator return a float in Python? Why would you use a float as an array index instead of doing integer division (with `//`)? I know this probably won't matter until you have extremely large arrays, but this is still quite a code smell. Perhaps this could be forgiven if you're a Python novice and hadn't realized that the two different operators exist,…
Earlier quoted context omitted.
This finds the mode (most common element), not the median. Wouldn't you also need to keep track of all element counts with your approach? You can't keep the count of only the second-most-common element because you don't know what that is yet.
Yes, you are right. I mixed up mode and median. And yes, one would need to keep track of at least a key for each element (not a huge element, if they are somehow huge). But that would be about space complexity.
Earlier quoted context omitted.
That is cool if you can tolerate approximations. But the uncomfortable questions soon arise: Can I tolerate an approximate calculation? What assumptions about my data do I to determine an error bound? How to verify the validity of my assumptions on an ongoing basis? Personally I would gravitate towards the quickselect algorithm described in the OP until I was forced to consider a streaming median approximation method…
Well, I believe you could use the streaming algorithms to pick the likely median, so help choose the pivot for the real quickselect. quickselect can be done inplace too which is O(1) memory if you can afford to rearrange the data.
I found this part of the code quite funny: # If there are Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1] [1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. In this case 5 is likely under that point, though I doubt 2^256 will. In practice you might also want to use a O(n^2) algorithm like insertion sort under some threshold.
Sure, but the author didn't argue that the simpler algorithm would be faster for 5 items, which would indeed make sense.
Instead, the author argued that it's OK to use the simpler algorithm for less than 5 items because 5 is a constant and therefore the simpler algorithm runs in constant time, hence my point that you could use the same argument to say that 2^140 (or 2^256) could just as well be used as the cut-off point and similarly argue that the simpler algorithm runs in constant time for all arrays than can be represented on a real-world computer, therefore obviating the need for the more complex algorithm (which obviously makes no sense).