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

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