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

测试矩阵中的行是否排序的有效方法是什么? [更新:见Aaron的Rcpp答案 – 直截了当的&非常快.]

我正在移植一些使用issorted(,'rows') from Matlab的代码.因为看起来is.unsorted并没有超出向量,我正在写或寻找其他东西.天真的方法是检查矩阵(或数据框)的排序版本是否与原始版本相同,但这显然是低效的.

注意:对于排序,la sortrows() in Matlab,我的代码基本上使用SortedDF< -DF [do.call(order,DF),](它包含在一个更大的函数中,它将矩阵转换为数据帧,将参数传递给订单等等. ).如果有更快的实现(数据表浮现在脑海中),我不会感到惊讶. 更新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,对于testSorted(x)将返回FALSE,对于testSorted(y)将返回TRUE.

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

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

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

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

在这种情况下,所有方法都需要大约0.85秒才能完成.无论如何,在5.5秒内完成并不可怕(实际上,对于对对象进行排序所需的时间似乎是正确的),但是知道排序矩阵快11倍表明没有排序的测试可能是均匀的快点.在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行,尽管矢量化并不是一个坏主意.

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

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

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

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

更新:我决定使用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的黑客攻击速度与所有矩阵相同;它对于排序矩阵来说肯定更快;对于未分类的,它取决于未分类的性质.

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)
}
相关文章
相关标签/搜索