1 시간 동안 최고 8 분의 창을 찾을 수있는 알고리즘

Question

활동이 한 시간 이상 실행됩니다. 일부 매개 변수가 최대 인 최대 8 분의 창을 가져야합니다.

예를 들어, 값 x는 매 초마다 측정됩니다. 1 시간 동안 내 활동이 실행되면 x에 3600 개의 값이 표시됩니다. 나는 x 값이 다른 모든 것들 중에서 가장 높은 연속적인 8 분 시간 간격을 찾아야한다.

예를 들어 0 분에서 8 분까지 캡처하면 최대 값 인 0.4 ~ 8.4와 같은 다른 시간대가있을 수 있습니다. 세분성은 1 초입니다. 매 초를 고려해야합니다.

도와주세요.

Answer 1

모든 가능성을 시도하는 것을 방해하는 것은 무엇입니까? 3600 값은 많지 않습니다. O (n * m) 시간에 그들을 실행할 수 있습니다. 여기서 n은 데이터 점의 수이고 m은 창의 점 수입니다.

최적화를 원하면 슬라이딩 윈도우를 사용하여 O (n)에서 수행 할 수 있습니다. 처음 8 분 안에 x의 모든 값의 대기열을 유지하고 그 8 분 동안의 합계를 유지하십시오. 1 초 전진 할 때마다 x의 가장 오래된 값을 대기열에서 제외하고 누적 합계에서 빼기를 수행 할 수 있습니다. 그런 다음 x의 새 값을 대기열에 추가하고 합계에 추가합니다.

하지만이 최적화는 문제의 크기에 거의 필요하지 않습니다. 여분의 성능이 필요하지 않으면 간단하게 유지하는 것이 좋습니다.

Answer 2

x의 최대 값을 캡처하는 창이 많이 있습니다. 원하는 것을 조금 정의하면됩니다. 창 x의 최대 평균값? 피크를 포함하는 모든 창 중, 가장 높은 평균을 가진 창? 최저 신호 대 잡음 비율? 피크를 포함하는 첫 번째 창? 이의 라인을 따라

Answer 3

뭔가 : 하스켈에서

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

!

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 5

이 최대 서브 시퀀스 문제이며이 O (N)에서 수행 할 수 있습니다. 예를 들어 구글.