0
$\begingroup$

Given a list of non-overlapping ranges and values, i.e. [(0, 5, 0.5), (10, 15, 1.1), ...], and a list of potentially overlapping ranges (bins), i.e. [(0, 10), (5, 15), (0, 5), ...], find the average, min, max, standard deviation of the bins.

For example, the answer for averages would be [0.25, 0.55, 0.5, ...]. Assume there is a implicit range (5, 10, 0) in the first list.

The max range is from 1 to 109. The number of bins ranges from 1 $\le$ n $\ge$ 1010.

What is a memory and computationally efficient way of solving this problem?

Edit: The first list of non-overlapping ranges would create a list: [0.5, 0.5, 0.5, 0.5, 0.5, 0, 0, 0, 0, 0, 1.1, 1.1, 1.1, 1.1, 1.1, ...]. A pair in the second list would specify the indices of the range to find a statistic. The average for the first pair, (0, 10), would be (0.5 * 5 + 0 * 5) / 10 = 0.25.

This is an actual problem in bioinformatics, and an algorithm already exists here, but I was wondering if there was a potentially better one.

$\endgroup$
10
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. If this problem is from a third party, please see the help for proper referencing. (The comparison operators look off.) $\endgroup$
    – greybeard
    Mar 8 at 17:37
  • $\begingroup$ I suppose this is from some competition, so asking people for help completely misses the point. The way to improve your ability to solve such problems is to solve them or try to solve them. $\endgroup$
    – gnasher729
    Mar 8 at 21:24
  • $\begingroup$ What is the std of a bin? $\endgroup$
    – gnasher729
    Mar 8 at 21:25
  • 1
    $\begingroup$ Which numbers exactly are represented for example by (0, 10, 0.5) ? I think if you had tried to solve this problem just a little bit, your question would have stated things much more precisely. $\endgroup$
    – gnasher729
    Mar 8 at 21:26
  • 1
    $\begingroup$ There is no $n$ smaller than or equal to one and greater than or equal to $10^9$. $\endgroup$
    – greybeard
    Mar 9 at 23:08
1
$\begingroup$

I don't know what algorithm they use so I don't know whether this will be better, but there is an efficient algorithm for your problem, by using a tree. Form the list of all endpoints of all ranges and bins, and sort it. This partitions the real line into non-overlapping intervals, where each bin is a union of intervals that don't overlap.

Put those endpoints into a binary search tree. Each internal node in the binary tree represents a union of those intervals. You can store, in each tree, the min, max, sum, and sum of squares of all values in that interval, filling these in bottom-up. Note that given these statistics for the two children of a node, it is easy to compute these statistics for the node itself in $O(1)$ time.

This yields an $O(n \log n)$ time algorithm, where $n$ counts the number of ranges + number of bins. It takes $O(n \log n)$ time to sort the endpoints, then $O(n)$ time to build the binary search tree, then $O(n)$ time to fill in each node bottom-up.

You might also enjoy reading about interval trees and segment trees, if you do a lot of computation on ranges/intervals.

$\endgroup$

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.