Алгоритм нахождения лучшего 8-минутного окна за 1 час бега

Question

Действие длится чуть больше часа. Мне нужно получить лучшее 8-минутное окно, где некоторые параметры максимальны.

Например, значение x измеряется каждую секунду. Если моя деятельность длится один час, я получаю 3600 значений для x. Мне нужно найти лучший непрерывный 8-минутный интервал времени, где значение x было самым высоким среди всех остальных.

Если я сниму, скажем, с 0-й по 8-ю минуту, может быть другой временной интервал, например, от 0,4 до 8,4, где он был максимальным. Зернистость составляет одну секунду. Нам нужно учитывать каждую секунду.

Пожалуйста, помогите мне с дизайном.

Answer 1

Что мешает вам просто попробовать каждую возможность? 3600 значений это не много. Вы можете выполнить их в O (n * m) раз, где n в количестве точек данных и m в количестве точек в окне.

Если вы хотите провести оптимизацию, вы можете сделать это в O (n), используя скользящее окно. Сохраняйте в очереди все значения x в течение первых 8 минут, а общее количество - за эти 8 минут. Каждый раз, когда вы продвигаетесь на одну секунду, вы можете исключить самое старое значение x и вычесть его из промежуточного итога. Затем добавьте новое значение x в очередь и добавьте его к итогу.

Но эта оптимизация вряд ли необходима для решения проблемы. Я бы рекомендовал не усложнять, если не требуется дополнительная производительность.

Answer 2

Что-то вроде этого:

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

В Хаскеле!

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

Использование:

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

Answer 4

Это проблема максимальной подпоследовательности, и это можно сделать за O (N). Google для примеров.

Answer 5

Есть много окон, которые фиксируют пиковое значение х - вам нужно определить, что вы хотите немного лучше. в окне максимальное среднее значение х? из всех окон, которые содержат пик, с самым высоким средним? самое низкое отношение сигнал / шум? первое окно, которое содержит пик?