2

質問:ベクトルを指定して、一連の累積合計の最小値を知りたいです。各累積合計は、ベクトルの増加する開始インデックスと固定終了インデックス (1:5、2:5、...) に対して計算されます。 、5:5)。for()具体的には、これがループを使用せずに計算できるかどうか、およびこのアルゴリズム/計算に潜在的な用語があるかどうか疑問に思っています。私はRで働いています。

コンテキスト: 対象のベクトルには、圧力変化の時系列が含まれています。一定範囲の開始点での圧力の最大 (または最小) 正味の変化を知りたいのですが、終点は固定されています。

詳細 + 例:

#Example R code    
diffP <- c(0, -1,  0,  1,  0,  0,  1,  0,  0,  0,  0,  0, -1,  0,  0,  0,  0,  0,  0,  0, -1,  0,  0)
minNet1 <- min(cumsum(diffP))
minNet1 #over the whole vector, the "biggest net drop" (largest magnitude with negative sign) is -1.
#However, if I started a cumulative sum in the second half of diffP, I would get a net pressure change of -2.
hold <- list()
nDiff <- length(diffP)
for(j in 1:nDiff){
   hold[[j]] <- cumsum(diffP[j:nDiff])
}
answer <- min(unlist(hold)) #this gives the answer that I ultimately want

上記の例が私の質問を明確にするのに役立ったことを願っています。answer正解が含まれていますがfor()、R でループを使用せずにこれを実行したいのですが、この計算を行うためのより良い方法はありますか、それとも名前を付けることができますか?

4

1 に答える 1

3

これはhttp://en.wikipedia.org/wiki/Maximum_subarray_problemとして知られており、典型的な面接の質問です!

ほとんどの人 (私を含む) は O(n^2) アルゴリズムを使用して解決しますが、実際には O(n) の複雑さを持つはるかに優れたアルゴリズムがあります。上記のリンクからの Kadane のアルゴリズムの R 実装を次に示します。

max_subarray <- function(A) {
   max_ending_here <- 0
   max_so_far <- 0
   for (x in A) {
      max_ending_here <- max(0, max_ending_here + x)
      max_so_far <- max(max_so_far, max_ending_here)
   }
   max_so_far
}

あなたの場合、最小のサブ配列の合計を探しているので、次のように呼び出す必要があります。

-max_subarray(-diffP)
[1] -2

(または、上記の関数を書き換えて、maxどこでも置き換えることもできminます。)

はい、実装はまだforループを使用していますが、アルゴリズムの複雑さは O(n) (操作の数が と同じ順序であることを意味しますlength(diff)) であるため、かなり高速である必要があります。また、いくつかの変数を保存および更新するだけなので、メモリを消費しません。

于 2013-08-28T19:22:41.647 に答える