r - 在 R 中对大数据进行高效字符串匹配(和索引)的技巧？

Question

我想做什么

我有许多唯一的 ID，例如id1, id2, etc. .它们出现在多个组中，每个组都是 1 到 100 个 ID 之间的随机样本，例如

[1] "id872- id103- id746-"                             
[2] "id830- id582-"                                   
[3] "id663- id403- id675- id584- id866- id399- id28- id550-"

我想找到一个 id 所属的所有组，例如为 id1

groups.with.id[1] = grep("id1-", groups)

我的问题

数据很大(80k id，1M 组)，这大约需要 12小时在我的笔记本电脑上。我认为这是我做某事 80k 次(每个 id 一次)的事实的组合，并且每次我访问一个巨大的对象(1M 组)。

有什么办法可以使这更有效吗？

(我经常在 R 中遇到较大对象的问题。例如，重复索引具有 > 10k 行的数据帧会很快变慢。 也感谢有效索引大对象的一般答案! )

示例代码

# make toy dataset
n.ids = 80000 # number of unique ids
n.groups = 100 # number of groupings

# make data
ids = paste("id", 1:n.ids, "-", sep="")
groups = character(n.groups)
for (ii in 1:n.groups) {
  group.size = ceiling(runif(1) * 10)
  groups[ii] = paste(sample(ids, group.size), collapse=" ")
}

# execute and time
t1 = Sys.time()
groups.with.id = sapply(ids, grep, groups)
difftime(Sys.time(), t1)

> Time difference of 29.63272 secs

在这个例子中，500 个组需要大约 30 秒。我想扩展到 100 万个组。有没有一种有效的方法来做到这一点？

Answer 1

这是一个 tidyverse选择。一个可能的缺点是数据中不存在的 ID 不会包含在输出中——尽管这可以在必要时解决。

library(tidyverse)

groups.with.id <- groups %>% 
  enframe() %>%
  separate_rows(value, sep = " ") %>%
  group_by(value) %>%
  summarise(ids = list(name)) %>%
  mutate(ids = set_names(ids, value)) %>%
  pull(ids)

如果您还想知道哪些 ID 不在任何组中，您可以使用:

setdiff(ids, names(groups.with.id))

基准测试表明，这种方法在示例数据集上比使用 grep 快 100 倍以上。与 fixed = TRUE .

microbenchmark::microbenchmark(original = sapply(ids, grep, groups),
                               original_fixed = sapply(ids, grep, groups, fixed = TRUE),
                               separate_summarise_groups = {groups %>% 
                                   enframe() %>%
                                   separate_rows(value, sep = " ") %>%
                                   group_by(value) %>%
                                   summarise(ids = list(name)) %>%
                                   mutate(ids = set_names(ids, value)) %>%
                                   pull(ids)}, times = 10, unit = "relative")

Unit: relative
                      expr      min       lq     mean   median        uq       max neval cld
                  original 685.0922 695.7236 382.0759 641.2018 290.30233 188.40790    10   c
            original_fixed 199.8912 209.1225 115.5693 199.9749  85.89842  59.26886    10  b 
 separate_summarise_groups   1.0000   1.0000   1.0000   1.0000   1.00000   1.00000    10 a