获取其他向量中矢量元素的重复实例的索引(都非常大)

Question

我有两个向量,一个(A)约1亿个非独特元素(整数),另一个(B)有100万个相同,独特的元素.我试图获得一个列表,其中包含A中每个B元素的重复实例的索引.

A <- c(2, 1, 1, 1, 2, 1, 1, 3, 3, 2)
B <- 1:3

# would result in this:
[[1]]
[1] 2 3 4 6 7

[[2]]
[1]  1  5 10

[[3]]
[1] 8 9

我天真地,天真地试过这个:

b_indices <- lapply(B, function(b) which(A == b))

这是非常低效的,显然不会在几年内完成.

我尝试的第二件事是创建一个空向量列表,用B的所有元素索引,然后循环通过A,将索引附加到A中每个元素的相应向量.虽然技术上O(n),我'我不确定重复追加元素的时间.这种方法显然需要2-3天,但仍然太慢......

有什么可以更快地工作吗？

Answer 1

这很快:

A1 <- order(A, method = "radix")

split(A1, A[A1])
#$`1`
#[1] 2 3 4 6 7
#
#$`2`
#[1]  1  5 10
#
#$`3`
#[1] 8 9

B <- seq_len(1e6)
set.seed(42)
A <- sample(B, 1e8, TRUE)

system.time({
  A1 <- order(A, method = "radix")

  res <- split(A1, A[A1])
})
# user      system     elapsed 
#8.650       1.056       9.704

Answer 2

data.table 可以说是处理R中大数据的最有效方法,它甚至可以让你避免不得不一起使用那个100万个长度的向量!

require(data.table)
a <- data.table(x=rep(c("a","b","c"),each=3))
a[ , list( yidx = list(.I) ) , by = x ]

   a  yidx
1: a 1,2,3
2: b 4,5,6
3: c 7,8,9

使用您的示例数据:

a <- data.table(x=c(2, 1, 1, 1, 2, 1, 1, 3, 3, 2))
a[ , list( yidx = list(.I) ) , by = x ]

   a      yidx
1: 2   1, 5,10
2: 1 2,3,4,6,7
3: 3       8,9

将其添加到您的基准测试中.我敢说它应该比使用内置函数快得多,如果你大规模测试它.数据越大data.table,我的经验中的相对表现就越好.

在我的基准测试中,它只占order我Debian笔记本电脑的46%左右,只有order我的Windows笔记本电脑只有5%,只有 8GB RAM和2.x GHz CPU.

B <- seq_len(1e6)
set.seed(42)
A <- data.table(x = sample(B, 1e8, TRUE))
system.time({
+   res <- A[ , list( yidx = list(.I) ) , by = x ]
+ })
   user  system elapsed 
   4.25    0.22    4.50