R中最快的列排序方法

Question

R中最快的列排序方法

17

我有一个数据框 full ，我想从中获取最后一列和一列 v 。然后，我想以最快的方式按 v 对两个列进行排序。 full 是从CSV中读取的，但可以用于测试（包括一些NA以实现真实性）：

n <- 200000
full <- data.frame(A = runif(n, 1, 10000), B = floor(runif(n, 0, 1.9)))
full[sample(n, 10000), 'A'] <- NA
v <- 1

我这里有一个变量v，但实际上它可能会改变，而full有很多列。

我已经尝试使用order和sort.list对数据框、数据表和矩阵进行排序（从这个帖子中获取了一些想法）。以下是所有这些的代码：

# DATA FRAME

ord_df <- function() {
  a <- full[c(v, length(full))]
  a[with(a, order(a[1])), ]
}

sl_df <- function() {
  a <- full[c(v, length(full))]
  a[sort.list(a[[1]]), ] 
}


# DATA TABLE

require(data.table)

ord_dt <- function() {
  a <- as.data.table(full[c(v, length(full))])
  colnames(a)[1] <- 'values'
  a[order(values)]
}

sl_dt <- function() {
 a <- as.data.table(full[c(v, length(full))])
 colnames(a)[1] <- 'values'
 a[sort.list(values)]
}


# MATRIX

ord_mat <- function() {
  a <- as.matrix(full[c(v, length(full))])
  a[order(a[, 1]), ] 
}

sl_mat <- function() {
  a <- as.matrix(full[c(v, length(full))])
  a[sort.list(a[, 1]), ] 
}

时间结果：

         ord_df  sl_df    ord_dt   sl_dt   ord_mat sl_mat
Min.     0.230   0.1500   0.1300   0.120   0.140   0.1400
Median   0.250   0.1600   0.1400   0.140   0.140   0.1400
Mean     0.244   0.1610   0.1430   0.136   0.142   0.1450
Max.     0.250   0.1700   0.1600   0.140   0.160   0.1600

或者使用 microbenchmark（结果以毫秒为单位）：

             min      lq       median   uq       max
1  ord_df() 243.0647 248.2768 254.0544 265.2589 352.3984
2  ord_dt() 133.8159 140.0111 143.8202 148.4957 181.2647
3 ord_mat() 140.5198 146.8131 149.9876 154.6649 191.6897
4   sl_df() 152.6985 161.5591 166.5147 171.2891 194.7155
5   sl_dt() 132.1414 139.7655 144.1281 149.6844 188.8592
6  sl_mat() 139.2420 146.8578 151.6760 156.6174 186.5416

似乎对数据表进行排序是最好的选择。在使用数据框时，order和sort.list之间并没有太大的区别，除非使用sort.list可以更快地处理。

在数据表版本中，我还尝试将v设置为键（由于根据文档进行排序），但我无法使它工作，因为v的内容不是整数。

由于我需要针对不同的v值多次执行此操作，所以最好能进一步加速此过程。有没有人知道如何进一步加速此过程？另外，尝试使用Rcpp实现是否值得一试？谢谢。

如果对任何人有用，这是我用于计时的代码：

sortMethods <- list(ord_df, sl_df, ord_dt, sl_dt, ord_mat, sl_mat)

require(plyr)
timings <- raply(10, sapply(sortMethods, function(x) system.time(x())[[3]]))
colnames(timings) <- c('ord_df', 'sl_df', 'ord_dt', 'sl_dt', 'ord_mat', 'sl_mat')
apply(timings, 2, summary) 

require(microbenchmark)
mb <- microbenchmark(ord_df(), sl_df(), ord_dt(), sl_dt(), ord_mat(), sl_mat())
plot(mb)

- Fist

“full”在排序之前原本是一个数据框（我无法更改），因此将其转换为矩阵或数据表是排序方法的一部分，因此需要包含在时间测量中。 - Fist

4

请升级至CRAN上现已发布的data.table v1.8.2版本。有一条评论指出您无法在非整数列上设置关键字 - 在1.8.2版本中已经修复了这个问题，详见NEWS。在v上设置关键字应该会更快。此外，您似乎将转换成data.table的时间包含在排序时间内，这样公平吗？然而，您可能会发现，在1.8.2版本中，转换时间比1.8.0版本要快得多。顺便说一下，很好的问题。 - Matt Dowle

4

你可能需要超过200,000行。每当我看到无关紧要的时间差被报道时，我通常会翻白眼。你是在说基于0.13秒与0.23秒的比较，data.table获胜了吗？我认为这个差异微不足道。请参阅vignette（“datatable-timings”），以获取我认为是良好基准测试的内容。8.8秒缩短为0.013秒（快了678倍），22.6秒缩短为1.1秒（快了19倍）。这些都是显著的时间差异，适用于你（几乎）有足够时间在等待时泡一杯茶的任务。 - Matt Dowle

1

对于 ord_df，不需要使用 with。你的速度差异是因为对数据框进行排序 order(a[1]) 而不是向量 order(a[[1]])；order(a[[1]]) 就像 sort.list(a[[1]])。如果要排序的列实际上是整数值，则 sort.list(..., method="radix") 很快（比 data.table 更快？）。 - Martin Morgan

@Martin data.table 使用 sort.list(...,method="radix")。如 ?setkey 中所述。 - Matt Dowle

显示剩余11条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fist · Accepted Answer

我不知道是将这种类型的内容作为编辑还是答案更好，但它似乎更像一个答案，所以我在此处发表。更新的测试函数：

n <- 1e7
full <- data.frame(A = runif(n, 1, 10000), B = floor(runif(n, 0, 1.9)))
full[sample(n, 100000), 'A'] <- NA

fdf <- full
fma <- as.matrix(full)
fdt <- as.data.table(full)
setnames(fdt, colnames(fdt)[1], 'values')

# DATA FRAME
ord_df <- function() { fdf[order(fdf[1]), ] }
sl_df <- function() { fdf[sort.list(fdf[[1]]), ] }

# DATA TABLE
require(data.table)
ord_dt <- function() { fdt[order(values)] }

key_dt <- function() {
  setkey(fdt, values) 
  fdt
}

# MATRIX
ord_mat <- function() { fma[order(fma[, 1]), ] }
sl_mat <- function() { fma[sort.list(fma[, 1]), ] }

以下是使用不同的电脑、R 2.13.1和data.table 1.8.2得到的结果：

         ord_df  sl_df   ord_dt  key_dt  ord_mat sl_mat
Min.     37.56   20.86   2.946   2.249   20.22   20.21
1st Qu.  37.73   21.15   2.962   2.255   20.54   20.59
Median   38.43   21.74   3.002   2.280   21.05   20.82
Mean     38.76   21.75   3.074   2.395   21.09   20.95
3rd Qu.  39.85   22.18   3.151   2.445   21.48   21.42
Max.     40.36   23.08   3.330   2.797   22.41   21.84

因此，data.table 是明显的赢家。使用键比排序更快，并且语法更好，我会这样认为。感谢大家的帮助。