Algorithm to find best 8 minute window in a 1 hour run

Question

An activity runs for a bit more than an hour. I need to get the best 8 minute window, where some parameters are maximum.

For example, a value x is measured every second. If my activity runs for one hour, I get 3600 values for x. I need to find the best continuous 8 minute time interval where the x value was the highest among all the others.

If I capture, say, from 0th minute to 8th minute, there may be another time frame like 0.4 to 8.4 where it was maximum. The granularity is one second. We need to consider every second.

Please help me with the design.

Answer 1

What is preventing you from just trying every possibility? 3600 values is not many. You can run through them in O(n*m) time where n in the number of data points and m in the number of points in the window.

If you want to make an optimization you can do it in O(n) by using a sliding window. Keep a queue of all the values of x within the first 8 minutes, and the total for that 8 minutes. Every time you advance one second you can dequeue the oldest value of x and subtract it from your running total. Then add the new value of x to the queue and add it to the total.

But this optimization hardly seems necessary for the size of problem you have. I'd recommend keeping it simple unless the extra performance is necessary.

Answer 2

there are many windows which will capture the peak value of x -- you need to define what you want a little better. the window the the maximum average value of x? of all the windows which contain the peak, the one with the highest average? lowest signal to noise ratio? the first window which contains the peak?

Answer 3

Something along the lines of this:

int[] xs = { 1, 9, 5, 6, 14, 9, 6, 1, 5, 4, 7, 16, 8, 3, 2 };

int bestEndPos = 0;
int bestSum = 0;

int currentSum = 0;
for (int i = 0; i < xs.length; i++) {

    // Add the current number to the sum.
    currentSum += xs[i];

    // Subtract the number falling out behind us.
    if (i >= 8)
        currentSum -= xs[i - 8];

    // Record our new "best-last-index" if we beat our previous record!
    if (currentSum > bestSum) {
        bestEndPos = i;
        bestSum = currentSum;
    }
}

System.out.println("Best interval: " + (bestEndPos - 8 + 1) + "-" + bestEndPos);
System.out.println("Has interval-sum of: " + bestSum);

Answer 4

In Haskell!

module BestWindow where

import Data.List (tails, maximumBy, genericTake)
import Data.Ord (comparing)
import System.Random (mkStdGen, random)

type Value = Integer
type Seconds = Integer
type Window = [Seconds]

getVal :: Seconds -> Value
getVal = fst . random . mkStdGen . fromIntegral

winVal :: Window -> Value
winVal = sum . map getVal

bestWindow :: Seconds -> Seconds -> (Value, Window)
bestWindow winTime totTime = maximumBy (comparing fst) valWins
  where
    secs = [0 .. totTime]
    wins = map (genericTake winTime) (tails secs)
    vals = map winVal wins
    valWins = zip vals wins

Usage:

bestWindow (8 * 60) (60 * 60) -- gives value of window and list of window seconds

Answer 5

This is maximum subsequence problem and it can be done in O(N). google for examples.

Answer 6

Hi, thanks a lot for all your responses. I need the window the the maximum average value of x?