如何加快检查巨大 ffdf 的重复

Question

我有一个ffdf的列表，如果加载到RAM而不是使用ff包，它会占用大约76GB的RAM。以下是他们各自的dim()

> ffdfs |> sapply(dim)
         [,1]     [,2]     [,3]      [,4]      [,5]      [,6]      [,7]
[1,] 11478746 12854627 10398332 404567958 490530023 540375993 913792256
[2,]        3        3        3         3         3         3         3
         [,8]     [,9]     [,10]     [,11]    [,12]     [,13]     [,14]
[1,] 15296863 11588739 547337574 306972654 11544523 255644408 556900805
[2,]        3        3         3         3        3         3         3
        [,15]     [,16]    [,17]
[1,] 13409223 900436690 15184264
[2,]        3         3        3

我想检查每个 ffdf 中的重复次数，所以我做了以下操作：

check_duplication <- sample_cols |> sapply(function(df) {
    df[c("chr","pos")] |> duplicated() |> sum()
})

它可以工作，但速度非常慢。

我在 HPC 上，我有大约 110GB RAM 和 18CPU。

我可以调整任何其他选项或设置来加快进程吗？谢谢。

Answer 1

并行化是加速这一过程的自然方式。它可以通过 data.table:

在 C 级完成

library("data.table")

data.table 1.14.2 using 4 threads (see ?getDTthreads).  Latest news: r-datatable.com

set.seed(1L)
x <- as.data.frame(replicate(2L, sample.int(100L, size = 1e+06L, replace = TRUE), simplify = FALSE))
y <- as.data.table(x)
microbenchmark::microbenchmark(duplicated(x), duplicated(y), times = 1000L)

Unit: milliseconds
          expr       min         lq       mean     median         uq       max neval
 duplicated(x) 449.27693 596.242890 622.160423 625.610267 644.682319 734.39741  1000
 duplicated(y)   5.75722   6.347518   7.413925   6.874593   7.407695  58.12131  1000

此处的基准显示 duplicated 应用于 data.table 而不是等效数据框时要快得多。当然，速度有多快取决于您提供给 data.table 的 CPU 数量（参见 ?setDTthreads）。

如果你走 data.table 路线，那么你将像这样处理你的 17 个数据帧：

nduped <- function(ffd) {
  x <- as.data.frame(ffd[c("chr", "pos")])
  setDT(x)
  n <- sum(duplicated(x))
  rm(x)
  gc(FALSE)
  n
}
vapply(list_of_ffd, nduped, 0L)

在这里，我们使用 setDT 而不是 as.data.table 来执行从数据帧到 data.table 的就地强制转换，我们使用 rm 和 gc 在将另一个数据帧读入内存之前释放 x 占用的内存。

如果出于某种原因 data.table 不是一个选项，那么您可以坚持对数据帧使用 duplicated 方法，即 duplicated.data.frame。它没有在 C 级别并行化，因此您需要在 R 级别并行化，例如使用 mclapply 将 17 个数据帧分配给批次并并行处理这些批次：

nduped <- function(ffd) {
  x <- as.data.frame(ffd[c("chr", "pos")])
  n <- sum(duplicated(x))
  rm(x)
  gc(FALSE)
  n
}
unlist(parallel::mclapply(list_of_ffd, nduped, ...))

此选项比您预期的更慢并且消耗更多的内存。幸运的是，还有优化的空间。这个答案的其余部分强调了一些主要问题和解决这些问题的方法。如果您已经选择 data.table.

，请随时停止阅读

由于你有18个CPU，你可以尝试同时处理所有17个数据帧，但是你可能会遇到内存不足的问题，因为一次将所有17个数据帧读入内存.增加批处理大小（即，将 17 个作业分布在少于 17 个 CPU 上）应该会有所帮助。
由于您的 17 个数据帧的长度（行数）差异很大，因此将它们随机分配给大致相同大小的批次可能不是一个好的策略。您可以通过将较短的数据帧一起批处理而不将较长的数据帧一起批处理来减少总体运行时间。 mclapply 有一个 affinity.list 参数给你这个控制权。理想情况下，每个批次需要相同的处理时间。

每个作业使用的内存量实际上至少是存储数据帧 x 所需内存量的两倍，因为 duplicated.data.frame 复制其参数：

x <- data.frame(chr = rep(1:2, times = 5L), pos = rep(1:2, each = 5L))
tracemem(x)

[1] "<0x14babad48>"

invisible(duplicated(x))

tracemem[0x14babad48 -> 0x14babc088]: as.list.data.frame as.list vapply duplicated.data.frame duplicated

复制发生在方法主体中的 vapply 调用内部：

duplicated.data.frame

function (x, incomparables = FALSE, fromLast = FALSE, ...) 
{
    if (!isFALSE(incomparables)) 
        .NotYetUsed("incomparables != FALSE")
    if (length(x) != 1L) {
        if (any(i <- vapply(x, is.factor, NA))) 
            x[i] <- lapply(x[i], as.numeric)
        duplicated(do.call(Map, `names<-`(c(list, x), NULL)), 
            fromLast = fromLast)
    }
    else duplicated(x[[1L]], fromLast = fromLast, ...)
}
<bytecode: 0x15b44f0f0>
<environment: namespace:base>

vapply 调用是完全可以避免的：您应该已经知道 chr 和 pos 是否是因子。我建议定义 duplicated.data.frame 的替代品，该替代品仅根据您的用例执行必要的操作。例如，如果您知道 chr 和 pos 不是因子，那么您可以分配

duped <- function(x) {
  duplicated.default(do.call(Map, `names<-`(c(list, x), NULL)))
}

并计算 sum(duped(x)) 而不是 sum(duplicated(x))。事实上，将 list 替换为 c:

可以做得更好

fastduped <- function(x) {
  duplicated.default(do.call(Map, `names<-`(c(c, x), NULL)))
}

在此处使用 c 会导致数据帧 x 的行作为原子向量而不是列表进行存储和比较。也就是说，fastduped(x)在做

duplicated.default(<length-'m' list of length-'n' atomic vectors>)

而 duped(x) 正在做

duplicated.default(<length-'m' list of length-'n' lists of length-1 atomic vectors>)

其中 m = nrow(x) 和 n = length(x)。后者速度较慢，消耗内存较多，?duplicated中有警告说：

Using this for lists is potentially slow, especially if the elements are not atomic vectors (see ‘vector’) or differ only in their attributes. In the worst case it is O(n^2).

计算 sum(fastduped(x)) 而不是 sum(duplicated(x)) 应该会增加您可以同时处理的数据帧的数量，而不会运行内存不足。 FWIW，这是一个比较 duplicated、duped、fastduped 的运行次的基准（不说内存使用情况）：

set.seed(1L)
x <- as.data.frame(replicate(2L, sample.int(100L, size = 1e+06L, replace = TRUE), simplify = FALSE))
microbenchmark::microbenchmark(duplicated(x), duped(x), fastduped(x), times = 1000L)

Unit: milliseconds
          expr      min       lq     mean   median       uq      max neval
duplicated(x) 521.7263 598.9353 688.7286 628.8813 769.6100 1324.458  1000
      duped(x) 521.3863 598.7390 682.1298 627.1445 764.7331 1373.712  1000
  fastduped(x) 431.0359 528.6613 594.1534 553.7739 609.6241 1123.542  1000

如何加快检查巨大 ffdf 的重复

how to speed up checking duplication for huge ffdf

hpc

r

ff

ffbase