performance - 在R中创建循环矩阵的有效方法

Question

我想根据R中的向量创建循环矩阵。循环矩阵是具有以下形式的矩阵。

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

第二行与第一行相同，但最后一个元素在开头，依此类推。

现在我有了向量，例如(1、2、3、4)，我想找到一种有效的(快速)方法来创建此矩阵。实际上，数字不是整数，可以是任何数字。

这就是我现在正在做的。

x <- 1:4
n <- length(x)
mat <- matrix(NA, n, n)
for (i in 1:n) {
    mat[i, ] <- c(x[-(1:(n+1-i))], x[1:(n+1-i)])
}

我想知道是否有更快的方法来做到这一点？我需要一遍又一遍地生成这种矩阵。一步的小改进将带来很大的不同。谢谢你。

Answer 1

以下是建议解决方案的一些基准。

ndoogan带头!

基准

x <- 1:100
microbenchmark(
  OP.Circulant(x),
  Josh.Circulant(x),
  Dwin.Circulant(x) ,
  Matt.Circulant(x),
  Matt.Circulant2(x),
  Ndoogan.Circulant(x),

  times=100
)
# Unit: microseconds
#                   expr       min         lq    median          uq        max
# 1    Dwin.Circulant(x)  1232.775  1288.1590  1358.999   1504.4490   2900.430
# 2    Josh.Circulant(x)  1081.080  1086.3470  1097.863   1125.8745   2526.237
# 3    Matt.Circulant(x) 61924.920 64579.3735 65948.152 129359.7895 137371.570
# 4   Matt.Circulant2(x) 12746.096 13499.0580 13832.939  14346.8570  16308.040
# 5 Ndoogan.Circulant(x)   469.502   487.2285   528.591    585.8275   1522.363
# 6      OP.Circulant(x)  1291.352  1363.8395  1421.509   1513.4950   2714.707

用于基准测试的代码

OP.Circulant <- function(x) {
    n <- length(x)
    mat <- matrix(NA, n, n)

    for (i in 1:n) {
        mat[i, ] <- c(x[-(1:(n + 1 - i))], x[1:(n + 1 - i)])
    }
    return(mat)

}


rotn <- function(x, n) rep(x, 2)[n:(n + length(x) - 1)]

Dwin.Circulant <- function(x) {
    n <- length(x)
    return(t(sapply(x[c(1L, n:2)], rotn, x = x)))
}

Josh.Circulant <- function(x, nrow = length(x)) {
    m <- length(x)
    return(matrix(x[(1:m - rep(1:nrow, each = m))%%m + 1L],
                  ncol = m, byrow = TRUE))
}


Matt.Circulant <- function(x) {
    n <- length(x)
    mat <- matrix(, n, n)
    for (i in seq(-n + 1, n - 1)) {
        mat[row(mat) == col(mat) - i] = x[i%%n + 1]
    }
    return(mat)
}

Matt.Circulant2 <- function(x) {
    n <- length(x)
    return(rbind(x[], do.call(rbind, lapply(seq(n - 1),
                            function(i) c(tail(x, i), head(x, -i))))))
}

Ndoogan.Circulant <-function(x) {
    n <- length(x)
    suppressWarnings(
      matrix(x[matrix(1:n,n+1,n+1,byrow=T)[c(1,n:2),1:n]],n,n))
}


# check for identical results (all TRUE)
check <- OP.Circulant(x)
identical(check, OP.Circulant(x))
identical(check, Dwin.Circulant(x))
identical(check, Josh.Circulant(x))
identical(check, Matt.Circulant(x))
identical(check, Matt.Circulant2(x))
identical(check, Ndoogan.Circulant(x))