1
$\begingroup$

So let's say you have a histogram distribution represented as an array where each element is equal to the number of numbers from the underlying data set that are equal to that element's index.

For example, if your underlying data had 5 0's, 18 1's, 11 2's, 0 3's, etc., then the array representing this distribution would look like... histogramBinSizes = [5, 18, 11, 0, ...]

Now, let's say you want to get the percentile distribution, which would be represented as an array where each element is equal to the number of numbers from the underlying data that fall in that percentile. What's the most efficient algorithm to get the percentile distribution array? (Maybe call this array percentileBinSizes)

To make the question easier, assume the numbers in the underlying data range from 0 to 100. That would make it so that histogramBinSizes and percentileBinSizes both have lengths of 101. Is there an even more efficient algorithm when this constraint is added?

I tagged this question with data structures as well as algorithms because I'm open to solutions that use a different data structure besides arrays. However, the input and output should still be arrays.

$\endgroup$
  • $\begingroup$ I hope I understood your question, you have sorted frequencies of elements, with the global count info (how many elements are there) you can do percentiles in single pass, you cannot do it faster (need to at least read the data) and am not sure how to do it differently. $\endgroup$ – Evil Jun 28 '17 at 20:17
  • $\begingroup$ Oh, my bad. The build is one pass, but the query is linear, so probably you want the interval tree. $\endgroup$ – Evil Jun 28 '17 at 20:28
  • $\begingroup$ What difficulties are you having with solving this? Looks like a straightforward linear pass over the input array to keep track of the percentile of each value, and then update the output array. That takes $O(n)$ time, where $n$ is the length of the input array. It seems unlikely you can do better than that, since you have to read the entire input. What am I missing? $\endgroup$ – D.W. Jun 28 '17 at 21:16
3
$\begingroup$

First, compute the cumulative distribution. Suppose the input array is $A[0..n-1]$. You can compute the cumulative distribution as follows:

  • Set $C[-1] := 0$.
  • For $i:=0,1,2,\dots,n-1$, do: set $C[i] := C[i-1] + A[i]$.

After this, $C[i]$ contains a count of the number of values in the underlying data set that are $\le i$.

Now you can compute percentiles directly from the cumulative distribution. In particular, item $i$ is in the $\lfloor 100 C[i] / C[n-1] \rfloor$ percentile. So, the output array can be computed as

  • Set $P[j] := 0$ for $j=:0,1,2,\dots,100$.
  • For $i:=0,1,\dots,n-1$, do:
    • Set $j := \lfloor 100 C[i] / C[n-1] \rfloor$, and set $P[j] := P[j] + A[i]$.

Now $P[j]$ contains the number of values from the underlying data set that fall into the $j$th percentile. That was what you wanted to compute.

The running time is $O(n)$, where $n$ is the length of the input array. It seems unlikely you can build anything that's any faster than that, as the problem seems to require reading the entire input.

$\endgroup$
  • $\begingroup$ Shouldn't you just set $P[j] := A[i]$? $\endgroup$ – Mark Betters Jun 30 '17 at 20:58
  • 1
    $\begingroup$ @MarkBetters, No, I don't think so. There might be multiple values of $i$ that are all at the same percentile. $\endgroup$ – D.W. Jun 30 '17 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.