r - 有效地查找值第一次出现在列表中

Question

我试图解决一个问题，其中有一个很长的列表，每个索引都有不同数量的数字。目标是说明每个数字出现的最早索引是什么。因此，如果 15 出现在列表中的索引 45 和 78 处，那么我应该返回 15 首先位于 48 处。在原始问题中，这是一个长度为 10,000 的列表，因此快速执行此操作很有帮助。

最初我尝试使用现有的列表结构并做了这样的事情，在 10,000 行时非常慢。

set.seed(1)
x <- replicate(100, sample(100, sample(10, 1)))
cbind(value = 1:100,
      index = sapply(1:100, function(i) which.max(sapply(x, function(x) i %in% x))))

最终我尝试将数据转换为 data.table，这样效果更好，但我一直想知道是否有更好的方法来解决问题。就像默认列表结构本质上效率低下一样，还是有更好的方法可以使用它？

set.seed(1)
x <- replicate(100, sample(100, sample(10, 1)))
dt <- data.table(index = rep(1:100, sapply(x, length)), value = unlist(x))
dt[,.(index = first(index)),value][order(value)]

如果有帮助，这里是原始问题的完整数据集。

library(RcppAlgos)
library(memoise)
library(data.table)

jgo <- function(n) {
  if (isPrimeRcpp(n) | n == 1) return (n)
  div <- divisorsRcpp(n)
  div <- div[-c(1, length(div))]
  div <- Map(function(a, b) c(a, b), div, rev(div))
  div2 <- lapply(div, function(x) lapply(jgo(x[1]), c, x[2]))
  unique(lapply(c(div, unlist(div2, recursive = FALSE)), sort))
}

jgo <- memoise(jgo)  

x <- lapply(1:12500, function(x) x - sapply(jgo(x), sum) + sapply(jgo(x), length))

Answer 1

您可以简单地将列表堆叠到数据框中并删除重复的值。这将为您提供列表中所有值的第一个索引。

set.seed(1)
x <- replicate(100, sample(100, sample(10, 1)))

names(x) <- seq_along(x)
first_indices <- (d <- stack(x))[!duplicated(d$values), ]

head(first_indices)
  values ind
1     38   1
2     57   1
3     90   1
5     94   2
6     65   2
7      7   3

您现在可以使用 %in% 查找您想要的任何值的索引——

subset(first_indices, values %in% c(37,48))

   values ind
11     37   3
40     48   8

基准 -

set.seed(1)
x <- replicate(1000, sample(1000, sample(10, 1)))

microbenchmark::microbenchmark(
  Shree = first_indices(x),
  JamesB = cbind(value = 1:1000,
      index = sapply(1:1000, function(i) which.max(sapply(x, function(x) i %in% x))))
)

Unit: milliseconds
  expr       min         lq        mean    median        uq       max neval
 Shree    2.3488    2.74855    4.171323    3.0577    4.7752   17.0743   100
JamesB 1750.4806 1904.79150 2519.912936 1994.9814 3282.5957 5966.1011   100