快速获取列表中匹配项的索引

Question

给定一个包含长度不同的向量的列表a和一个包含a中某些元素的向量b，我想要得到一个与b长度相等的向量，其中包含了b中每个元素在a中匹配的索引（这是一个糟糕的解释，我知道...）

下面的代码可以实现这个目标：

a <- list(1:3, 4:5, 6:9)
b <- c(2, 3, 5, 8)

sapply(b, function(x, list) which(unlist(lapply(list, function(y, z) z %in% y, z=x))), list=a)
[1] 1 1 2 3

用for循环替换sapply当然可以实现相同的功能。

问题在于，此代码将与长度超过1000的列表和向量一起使用。 在真实数据集上，该函数需要大约15秒钟（对于for循环和sapply都是如此）。

有人有想法如何加速此过程，除了并行处理的方法？ 我没有看到矢量化的方法（我也不会编写C，虽然那可能是最快的方法）。

编辑：

只想强调Aaron的优雅解决方案，使用match()可以获得1667倍的速度提升（从15到0.009）

我稍微扩展了一下，以允许多个匹配（返回值是一个列表）。

a <- list(1:3, 3:5, 3:7)
b <- c(3, 5)
g <- rep(seq_along(a), sapply(a, length))
sapply(b, function(x) g[which(unlist(a) %in% x)])
[[1]]
[1] 1 2 3

[[2]]
[1] 2 3

运行时间为 0.169，这可能略慢，但另一方面更加灵活。

- ThomasP85

---

如果在a的多个元素中出现了b的一个元素，你希望算法做什么？您的实际问题中是否可能出现这种情况？ - Joshua Ulrich

我应该明确指出......这不是一种可能性。 - ThomasP85

Answer 1

以下是使用 match 的一种可能性：

a <- list(1:3, 4:5, 6:9)
b <- c(2, 3, 5, 8)
g <- rep(seq_along(a), sapply(a, length))
g[match(b, unlist(a))]
#> [1] 1 1 2 3

findInterval是另一个选项：

findInterval(match(b, unlist(a)), cumsum(c(0, sapply(a, length))) + 1)
#> [1] 1 1 2 3

返回一个列表，试试这个：

a <- list(1:3, 4:5, 5:9)
b <- c(2, 3, 5, 8, 5)
g <- rep(seq_along(a), sapply(a, length))
aa <- unlist(a)
au <- unique(aa)
af <- factor(aa, levels = au)
gg <- split(g, af)
gg[match(b, au)]

- Aaron left Stack Overflow

---

从15秒到0.009秒-这是一个令人印象深刻的改进。我发现我实际上想返回一个列表而不是向量，以便它可以处理多个匹配项。我用sapply(b, function(x) g[which(unlist(a) %in% x)])替换了您第一个建议中的最后一行来实现这一点。然后运行时间为0.169秒，比您的慢得多，但仍然是一个重大的改进。 - ThomasP85

供日后参考：在R 4.2中，使用第一种选项（match()与seq_along()）与第二种选项（match()与findInterval()）的速度完全相同。这两个版本都已经在R 3.0及以后的版本中可用。 - MS Berends

Answer 2

正如您帖子中的评论所建议的那样，如果/当相同元素出现在a的多个向量中，这取决于您想要做什么。 假设您想要最低索引，则可以执行以下操作：

apply(sapply(a, function(vec) {b %in% vec}), 1, which.max)

- ALiX