测试矩阵或数据帧的行是否按R排序

Question

什么是测试矩阵中的行是否排序的有效方法？[更新:请参阅Aaron的Rcpp答案 - 直截了当且非常快.]

我正在移植一些使用issorted(,'rows')Matlab的代码.因为它似乎is.unsorted不会超越矢量,我正在写或寻找其他东西.天真的方法是检查矩阵(或数据框)的排序版本是否与原始版本相同,但这显然效率低下.

注意:对于排序,sortrows()在Matlab中的一个la ,我的代码基本上使用SortedDF <- DF[do.call(order, DF),](它包含在一个更大的函数中,它将矩阵转换为数据帧,传递参数order等).如果有更快的实现(数据表浮现在脑海中),我不会感到惊讶.

---

更新1:澄清:我没有测试排列行内或列内.(这种排序通常会产生代数不同的矩阵.)

作为创建未排序矩阵的示例:

set.seed(0)
x <- as.data.frame(matrix(sample(3, 60, replace = TRUE), ncol = 6, byrow = TRUE))

它的排序版本是:

y <- x[do.call(order, x),]

一个适当的测试,比如说testSorted,将返回FALSE的testSorted(x)和TRUE为testSorted(y).

更新2: 以下答案都很好 - 它们很简洁并且可以进行测试.关于效率,看起来这些都是对数据进行排序.

我已经尝试使用相当大的矩阵,例如1M x 10,(只是更改x上面的创建),并且所有矩阵都具有相同的时间和内存成本.特别之处在于,对于未分类的对象(1Mx10大约5.5秒)消耗的时间比分类对象(大约0.5秒y)消耗的时间更长.这表明他们在测试前进行了分类.

我通过创建z矩阵进行测试:

z <- y
z[,2] <- y[,1]
z[,1] <- y[,2]

在这种情况下,所有方法都需要大约0.85秒才能完成.不管怎样,在5.5秒整理并不可怕(事实上,这似乎是正确的约排序的对象所需的时间),但我们知道,一个有序矩阵是11X快表明,一个测试,不排序可能会更快点.在1M行矩阵的情况下,前三行x是:

  V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
1  3  1  2  2  3  1  3  3  2   2
2  1  1  1  3  2  3  2  3  3   2
3  3  3  1  2  1  1  2  1  2   3

没有必要超越第2行,尽管矢量化并不是一个坏主意.

(我还添加了byrow创建的参数x,因此行值不依赖于.的大小x.)

更新3: 可以使用sort -cLinux中的命令找到此测​​试的另一个比较.如果文件已写入(使用write.table()),包含1M行,则time sort -c myfile.txt未排序数据需要0.003秒,排序数据需要0.101秒.我不打算写出文件,但这是一个有用的比较.

更新4: Aaron的Rcpp方法击败了这里提供的所有其他方法,并且我已经尝试过(包括sort -c上面的比较:内存预计会在盘上击败).至于相对于其他方法的比例,很难说:分母太小而无法给出准确的测量结果,而且我没有进行过广泛的探索microbenchmark.对于某些矩阵(例如一个用矩阵),加速可能非常大(4-5个数量级)rnorm,但这是误导性的 - 检查可以在仅几行之后终止.我已经加速了大约25-60的示例矩阵和未分类的大约1.1X,因为如果数据被排序,竞争方法已经非常快.

由于这是正确的事情(即没有排序,只是测试),并且非常快,它是公认的答案.

Answer 1

如果y被排序,则do.call(order,y)返回1:nrow(y).

 testSorted = function(y){all(do.call(order,y)==1:nrow(y))}

请注意,这不会比较矩阵,但一旦发现不匹配就不会消失.

Answer 2

好吧,你为什么不用:

all(do.call(order, y)==seq(nrow(y)))

这避免了创建有序矩阵,并确保它检查您的订购风格.

Answer 3

更新：我决定我可以使用 Rcpp 练习......

library(Rcpp)
library(inline)
isRowSorted <- cxxfunction(signature(A="numeric"), body='
  Rcpp::NumericMatrix Am(A);
  for(int i = 1; i < Am.nrow(); i++) {
    for(int j = 0; j < Am.ncol(); j++) {
      if( Am(i-1,j) < Am(i,j) ) { break; }
      if( Am(i-1,j) > Am(i,j) ) { return(wrap(false)); }
    }
  }
  return(wrap(true));
', plugin="Rcpp")

rownames(y) <- NULL # because as.matrix is faster without rownames
isRowSorted(as.matrix(y))

新：这个 R-only hack 对所有矩阵的速度都相同；排序矩阵肯定更快；对于未排序的，它取决于未排序的性质。

iss3 <- function(x) {
  x2 <- sign(do.call(cbind, lapply(x, diff)))
  x3 <- t(x2)*(2^((ncol(x)-1):0))
  all(colSums(x3)>=0)
}

原文：对于某些未排序的矩阵，这更快。多快取决于未排序元素的位置；这会逐列查看矩阵，因此左侧的未排序会比右侧的未排序更快被注意到，而顶部/底部几乎没有那么重要。

iss2 <- function(y) {
  b <- c(0,nrow(y))
  for(i in 1:ncol(y)) {
    z <- rle(y[,i])
    b2 <- cumsum(z$lengths)
    sp <- split(z$values, cut(b2, breaks=b))
    for(spi in sp) {
      if(is.unsorted(spi)) return(FALSE)
    }
    b <- c(0, b2)
  }
  return(TRUE)
}