2

これは、高レベルの一般的な質問です。いくつかの類似したものがあり、異なる、より簡潔な例があります。おそらく答えられないでしょう。connは行列です。

     for (i in 2:dim(conn)[1]) {
        for (j in 2:dim(conn)[1]) {
          if ((conn[i, 1] == conn[1, j]) & conn[i, 1] != 0) {
              conn[i, j] <- 1
              conn[j, i] <- 1
              }
              else {
                conn[i, j] <- 0
                conn[j, i] <- 0
                }
           }
      }

これはcluscomp、clusterConsパッケージから直接提供されます。

私の質問は単純です：ループをスピードアップすること、またはそれをベクトル化することは可能ですか？R初心者としては見えないので欲求不満になりたくないです。「はい」または「いいえ」と答えることができ、潜在的な労力の量を示唆する答えを受け入れます。

4

3 に答える 3

2

非行列ソリューション-connが非負で対称であると仮定すると、かなり速くなるはずです...

connmake = function(conn){
  ordering = order(conn[,1])
  breakpoints = which(diff(conn[ordering,1]) != 0)
  if (conn[ordering[1], 1] != 0){
    breakpoints = c(1, breakpoints + 1, nrow(conn) + 1)
  } else {
    breakpoints = c(breakpoints + 1, nrow(conn) +1)
  }
  output = matrix(0, nrow(conn), nrow(conn))

  for (i in 1:(length(breakpoints) - 1)){
    output[ ordering[breakpoints[i]:(breakpoints[i+1] -1)],
        ordering[breakpoints[i]:(breakpoints[i+1] -1)]] =  1
  }
  output[,1] = conn[,1]
  output[1,] = conn[,1]
  output
}

以前のベンチマークを使用したいくつかのテストコード。（元のコードはorig()、f2()以前の提案として実装されています。）

size = 2000
conn  = matrix(0, size, size)
conn[1,] = sample( 1:20, size, replace = T)
conn[,1] = conn[1,]

system.time(orig(conn) -> out1)
#user  system elapsed 
#20.54    0.00   20.54 
system.time(f2(conn) -> out2)
#user  system elapsed
#0.39    0.02    0.41 
system.time(connmake(conn) -> out3)
#user  system elapsed 
#0.02    0.00    0.01 
identical(out1, out2)
#[1] TRUE
identical(out1, out3)
#[1] TRUE

f2は実際には0を含むconnで失敗しますが、私の問題ではないことに注意してください。負の値のconnは、たとえば、関連する値を安全なオフセットで増やすだけで処理できます。非対称のconnはもっと考える必要がありますが、実行可能である必要があります...

一般的な教訓は、並べ替えはペアワイズ比較に比べて高速であるということです。ペアワイズ比較はO（N ^ 2）ですが、Rで最も遅いソートアルゴリズムはO（N ^ 4/3）です。データが並べ替えられると、比較は簡単になります。

于 2012-05-24T10:02:13.850 に答える
2

outerこれは、二重ループの代わりに使用して、私がそれをどのように書いたかです。まだ必要以上の計算を行っていますが、確かに高速であることに注意してください。私はconn正方行列であると仮定しました。

元のコード:

f1 <- function(conn) {
   for (i in 2:dim(conn)[1]) {
      for (j in 2:dim(conn)[1]) {
         if ((conn[i, 1] == conn[1, j]) & conn[i, 1] != 0) {
            conn[i, j] <- 1
            conn[j, i] <- 1
         } else {
            conn[i, j] <- 0
            conn[j, i] <- 0
         }
      }
   }
   return(conn)
}

私のおすすめ：

f2 <- function(conn) {
   matches <- 1*outer(conn[-1,1], conn[1,-1], `==`)
   matches[conn[-1,1] == 0, ] <- 0
   ind <- upper.tri(matches)
   matches[ind] <- t(matches)[ind]
   conn[-1,-1] <- matches
   return(conn)
}

いくつかのサンプルデータ:

set.seed(12345678)
conn <- matrix(sample(1:2, 5*5, replace=TRUE), 5, 5)
conn
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    2    2    1    2    1
# [2,]    1    1    2    2    1
# [3,]    2    2    1    2    1
# [4,]    2    2    2    2    1
# [5,]    1    1    2    2    1

結果：

f1(conn)
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    2    2    1    2    1
# [2,]    1    0    1    1    0
# [3,]    2    1    0    0    1
# [4,]    2    1    0    1    0
# [5,]    1    0    1    0    1

identical(f1(conn), f2(conn))
# [1] TRUE

時間を比較した大きな例:

set.seed(12345678)
conn <- matrix(sample(1:2, 1000*1000, replace=TRUE), 1000, 1000)

system.time(a1 <- f1(conn))
# user  system elapsed 
# 59.840   0.000  57.094 

system.time(a2 <- f2(conn))
# user  system elapsed 
# 0.844   0.000   0.950 

identical(a1, a2)
# [1] TRUE

あなたが得ることができる最速の方法ではないかもしれませんが (コンパイラーや Rcpp などを使用して、ここにいる他の人がはるかに高速であることは間違いありません)、短くて十分に高速であることを願っています。

conn編集：対称行列であることが（このコードがどこから引き出されたのかという文脈から）指摘されているので、私の解決策は少し短くすることができます：

f2 <- function(conn) {
   matches <- outer(conn[-1,1], conn[1,-1],
                    function(i,j)ifelse(i==0, FALSE, i==j)) 
   conn[-1,-1] <- as.numeric(matches)
   return(conn)
}
于 2012-05-24T00:54:07.043 に答える
1

いくつかのことが思い浮かびます。

まず、対角線の下または上のエントリだけをループすることで、時間を約半分に短縮できます。行列が正方形の場合、どちらでも機能します。dim(conn)[1] > dim(conn)[2]次に、次のようなものを使用して左下の三角形をループしたい場合

for (j in 2:dim(conn)[2]) {
  for (i in j:dim(conn)[1]) {
    ...
  }
}

第二に、使用しようとするかもしれませんがapply、通常は大幅な時間の短縮をもたらすため、それはうまくいきません。ただし、この場合、各 [i,j] セルは column head[1,j]と row head の両方を参照し[i,1]ます。つまり、セル、行、または列を *pply に送信することはできません。コードを明確にするために、おそらくforループを保持します。*pply ベースのトリックはどれも非常に巧妙で、1 年後にはそれがどのように機能したかを忘れてしまいます。

最後に、これは、R から呼び出された C を使用してはるかに高速になる典型的な例のようです。これは大変な作業のように思えるかもしれませんが、(この特定の例では)あなたは C を知りません。私にとって意味のある R から C を呼び出す最初の簡単な例はhereでしたが、Rcpp を活用していないため、ここで終わりません。あるいは、Rcpp コードを動作させる簡単な例から始める場合は、ここでやりたいことを行うように変更することができます。他の人のコードを変更したいだけなら、この StackOverflow スレッドから始めてください。

于 2012-05-23T22:13:26.220 に答える