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)

我的问题

数据很大（8 万个 ID，100 万组），这在我的笔记本电脑上大约需要 12 小时。我认为这是我正在做某事 80k 次（每个 id 一次）以及每次我访问一个巨大的对象（100 万组）的事实的组合。

有什么方法可以提高效率吗？

（我经常遇到 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 和 fixed = TRUE 快 100 倍以上。

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

R 中大数据高效字符串匹配（和索引）的技巧？

Tips for efficient string matching (and indexing) for large data in R?

string

r

string-matching

processing-efficiency

large-data