Search algorithm for the best 8-minute window for 1 hour

Question

Activity takes a little over an hour. I need to get a better 8 minute window where some parameters are maximal.

For example, the value of 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 x was the highest among all the others.

If I capture, say, from the 0th minute to the 8th minute, there may be a different time interval, for example, from 0.4 to 8.4, when it was maximum. Granularity is one second. We must consider every second.

Please help me with the design.

Answer 1

What prevents you from just trying all the features? 3600 values ​​are few. You can run them at O ​​(n * m) time, where n is the number of data points and m is the number of points in the window.

If you want to do the optimization, you can do it in O (n) using a sliding window. Keep a queue of all x values ​​for the first 8 minutes, and the total for 8 minutes. Each time you advance for one second, you can remove the highest value of x and subtract it from the total. Then add the new x value to the queue and add it to the total.

But this optimization hardly seems necessary for the size of your problem. I would recommend keeping it simple unless extra performance is required.

Answer 2

Something like that:

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 3

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 

Using:

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

Answer 4

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

Answer 5

This is the maximum subsequence problem, and this can be done in O (N). Google for examples.