Median

The Challenge

The challenge is to find the median of a stream of 100,000,000 uint32s in binary as fast as possible. Median here means the 50,000,000th element in the sorted list.

The Solution

The naive solution would be to read in every value, store it, sort, and take the middle value. The issue with this is the fact that every value has to be stored and the entire array has to be sorted. Sorting 100 million values is absurd so the first optimization I made was to process the input into separate bins based on the highest 11 bits of the uint32. This way the bin containing the median could be quickly identified by noting when the prefix sum of the bin sizes crossed over 50 million. For example if there were 4 bins and 10 numbers and the bins had sizes: 2, 4, 1, 3. The 5th element is the third element in the second bin because the prefix sum when adding in the 2nd bin crosses 5 from 2 to 6. Then, only roughly 1/2048th of the values would have to be sorted. I found a nice sorting library online called tieredsort and used it for all the solution iterations.

The next important step was to get rid of the useless work of storing the whole 100 million values when really only values in the median containing bin were relevant. Therefore the core loop was broken into 2 loops that both read the entire input front to back. The first one just kept counters for the number of elements in each bin without storing any values. This was then used to identify the median containing bin and the median's exact location in that bin. The second one read the input again, but this time storing the actual values that fell into that bin.

Making the second loop fast was quite simple. The 2048 bins made it <1% likely that any of the 8 uint32s processed each iteration were in the one desired bin. Therefore a simple fastpath was added for an early exit.

Optimizing the first loop was harder. The 8 sequential writes each iteration that updated the bin sizes killed the speed and getting around that seemed pretty tough.

I made a number of attempts to restructure the algorithm to get past this block. Instead of having an array of bin sizes, a simple count of values below certain thresholds would be kept. A simple example of this is counting the number of values below 25%, 50%, and 75% marks of UINT32_MAX. This process can identify the median within the quartile and could all be done completely vectorized. The only issue, though, is the second loop has to deal with a huge bin size.

To keep the bin size small, I used the fact that the median is likely near the 50% mark and only explored a 50% +/- k% range where k is pretty small, but that was still too slow. My last attempt down this path was to have multiple loops narrowing the bin size down together, each exploring in finer granularity the identified median containing range of the previous loop. This cut down on the total number of accumulators, but required another walk through the data and still couldn’t beat the original 2 loop approach with the sequential bin size updating bottleneck.

At this point the solution had around a score of 9.6k at 27th which was not in the top 20 as was my goal. The key realization that got me past this barrier and nearly halved my runtime was that the algorithm could be probabilistic just like in Parse Integers. The bin that the median was in could be estimated from just a small sample of the values instead of every value like in the time consuming first loop. This required, though, a larger bin size because the algorithm had to maintain a high probability of the chosen bin actually having the global median. Therefore, I ended up choosing around 128 bins and only actually processing every nth value.

This insight vastly simplified the first loop but also required a modification to the second loop because now the total bin counts weren’t known. The prefix sum was only based on the sampled data and could no longer identify where the 50 millionth element was in the bin. To fix this, a simple accumulator that counted all values below the bin was inserted into the second loop and the index of the median in the bin was just 50 million minus this accumulator.

Results and Thoughts

This final solution got a score of 5093 and reached 18th on the leaderboard. I believe that for most challenges there are perhaps a few different algorithms that can get a solution into the top 20, but I think the probabilistic first run to estimate the median is critical to breaking through to the top solutions. It is just so time consuming to otherwise process every uint32 into a bin.

The final algorithm isn’t very complex at all, it really just came down to coming up with the right idea. I enjoyed testing the different algorithms (especially because the relative simplicity made the process pretty quick). And lastly, thanks again to the sorting algorithm I used: tieredsort.