在R中最快的去除所有重复值的方法

Question

我想要从向量中删除所有出现超过一次的项，包括字符、数字和整数向量。目前，我使用 duplicated() 函数进行前向和后向去重。

在R中，是否有更高效（更快）的方法来执行此操作？下面的解决方案很简单易懂，但执行两次重复搜索似乎效率低下。也许使用计数的方法并添加额外的数据结构会更好？

示例：

d <- c(1,2,3,4,1,5,6,4,2,1)
d[!(duplicated(d) | duplicated(d, fromLast=TRUE))]
#[1] 3 5 6

相关的SO帖子在这里和这里。

- Megatron

---

这个也可以工作，但我不确定它是否更加计算上高效：d[!(d %in% d[duplicated(d)])]。 - lmo

“duplicated”是一个内部函数，支持长向量，我认为调用两次并不像你想象的那么低效。它比使用建议的集合操作解决方案更快。 - rawr

如果时间是问题，使用 duplicated.default 可以节省约50%的时间。 - Señor O

@Bulat 两个答案有共同点并不意味着这些问题是重复的。 - Señor O

@alexis_laz仅在d为严格正整数时起作用，否则为{ ud = unique(d); ud[tabulate(match(d, ud)) == 1L] }。 - Martin Morgan

Answer 1

一些时间：

set.seed(1001)
d <- sample(1:100000, 100000, replace=T)
d <- c(d, sample(d, 20000, replace=T))  # ensure many duplicates
mb <- microbenchmark::microbenchmark(
  d[!(duplicated(d) | duplicated(d, fromLast=TRUE))],
  setdiff(d, d[duplicated(d)]),
  {tmp <- rle(sort(d)); tmp$values[tmp$lengths == 1]},
  as.integer(names(table(d)[table(d)==1])),
  d[!(duplicated.default(d) | duplicated.default(d, fromLast=TRUE))],
  d[!(d %in% d[duplicated(d)])],
  { ud = unique(d); ud[tabulate(match(d, ud)) == 1L] },
  d[!(.Internal(duplicated(d, F, F, NA)) | .Internal(duplicated(d, F, T, NA)))]
)
summary(mb)[, c(1, 4)]  # in milliseconds
#                                                                                expr      mean
#1                               d[!(duplicated(d) | duplicated(d, fromLast = TRUE))]  18.34692
#2                                                       setdiff(d, d[duplicated(d)])  24.84984
#3                       {     tmp <- rle(sort(d))     tmp$values[tmp$lengths == 1] }   9.53831
#4                                         as.integer(names(table(d)[table(d) == 1])) 255.76300
#5               d[!(duplicated.default(d) | duplicated.default(d, fromLast = TRUE))]  18.35360
#6                                                      d[!(d %in% d[duplicated(d)])]  24.01009
#7                        {     ud = unique(d)     ud[tabulate(match(d, ud)) == 1L] }  32.10166
#8 d[!(.Internal(duplicated(d, F, F, NA)) | .Internal(duplicated(d,      F, T, NA)))]  18.33475

鉴于评论，请让我们看看它们是否都正确？

 results <- list(d[!(duplicated(d) | duplicated(d, fromLast=TRUE))],
         setdiff(d, d[duplicated(d)]),
         {tmp <- rle(sort(d)); tmp$values[tmp$lengths == 1]},
         as.integer(names(table(d)[table(d)==1])),
         d[!(duplicated.default(d) | duplicated.default(d, fromLast=TRUE))],
         d[!(d %in% d[duplicated(d)])],
         { ud = unique(d); ud[tabulate(match(d, ud)) == 1L] },
         d[!(.Internal(duplicated(d, F, F, NA)) | .Internal(duplicated(d, F, T, NA)))])
 all(sapply(ls, all.equal, c(3, 5, 6)))
 # TRUE

- Raad

---

不妨全力以赴 d[!(.Internal(duplicated(d, FALSE, FALSE, NA)) | .Internal(duplicated(d, FALSE, TRUE, NA)))] - rawr

最好先检查正确性（与测试用例的一致性），然后是鲁棒性（包括字符、整数、数字向量，从更新的问题中获得；names(tables(...)) 的解决方案会失败），最后再考虑性能。 - Martin Morgan

哎呀呀，第二名！ - Señor O

在更大的向量上进行基准测试会不会更加干净呢？另外，do.call(all.equal, results)仅比较“results”的前两个元素；其他元素将作为其他参数传递。 - alexis_laz

看起来我的解决方案最终是第一个。 - Bulat

这实际上是误导性的，至少使用10^6作为样本，由于这是一个单向量，我甚至会选择10^8。结果差异太大了！ - Bulat

Answer 2

您可以使用 rle 函数来实现此操作：

tmp <- rle(sort(d))
res <- tmp$values[tmp$lengths == 1]

找到向量中相同值的数量是个好主意。

这里有很多替代方法：在向量中计算具有x值的元素数量 编辑 看完基准测试后，@NBATrends让我有些怀疑。理论上说，通过单次遍历计算项目数必须比原始的duplicated逻辑快约2倍。

我尝试使用data.table来实现这一点：

library(data.table)
dt <- data.table(d)
res <-  dt[, count:= .N, by = d][count == 1]$d

以下是三种解决方案在不同样本大小下的基准测试结果（仅列出了快速独特方法）：。可以看到，随着样本量的增长，data.table 开始表现出优异的性能（2倍）。以下是代码以进行复制：

set.seed(1001)
N <- c(3, 4, 5, 6 ,7)
n <- 10^N
res <- lapply(n, function(x) {
d <- sample(1:x/10, 5 * x, replace=T)
d <- c(d, sample(d, x, replace=T))  # ensure many duplicates
dt <- data.table(d)
mb <- microbenchmark::microbenchmark(
  "duplicated(original)" = d[!(duplicated(d) | duplicated(d, fromLast=TRUE))],
  "tabulate" = { ud = unique(d); ud[tabulate(match(d, ud)) == 1L] },
  "data.table" = dt[, count:= .N, by = d][count == 1]$d,
  times = 1,unit = "ms")
sm <- summary(mb)[, c(1, 4, 8)]
sm$size = x
return(sm)

})

res <- do.call("rbind", res)

require(ggplot2)
##The values Year, Value, School_ID are
##inherited by the geoms
ggplot(res, aes(x = res$size, y = res$mean, colour=res$exp)) + 
geom_line() + scale_x_log10() + scale_y_log10() +
geom_point() 

- Bulat

---

就此而言，标准的 data.table 语法/做法是 dt[, if(.N == 1) .SD, by = d]。 - eddi

从语法角度来看，它很有趣，但在速度方面并不高效。 - Bulat

@Bulat，哪个更快很大程度上取决于重复项的分布。 - eddi

@eddi，我想不出为什么会这样。 - Bulat

Answer 3

你可以使用一个集合操作：

d <- c(1,2,3,4,1,5,6,4,2,1)
duplicates = d[duplicated(d)]
setdiff(d, duplicates)
[1] 3 5 6

（不确定这是否比上面的代码更有效，但从概念上看似乎更清晰）

- djq