2
$\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.

Improve this question
$\endgroup$
3
  • $\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, 2017 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, 2017 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, 2017 at 21:16

1 Answer 1

Reset to default
5
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Shouldn't you just set $P[j] := A[i]$? $\endgroup$
    – Mark Betters
    Jun 30, 2017 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, 2017 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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