为什么在 R 中 `outer` 比 `for` 循环慢？

Question

u <- rnorm(10000)
v <- rnorm(10000)

# `outer`
system.time(mat1 <- outer(u, v , `<`))
#    user  system elapsed 
#    1.80    1.34    3.32 

# `for` loop
system.time({
  mat2 <- matrix(NA, nrow = length(u), ncol = length(v))
  for(i in seq_along(v)) {
    mat2[, i] <- u < v[i]
  }
})
#    user  system elapsed 
#    0.97    0.02    1.01 

identical(mat1, mat2)
# [1] TRUE

- Julien

---

我得到了（几乎）完全相同的 system.time，分别为 (0.45/0.17/0.62 和 0.45/0.18/0.63)。 - Sotos

我也尝试过几次（使用不同大小的矩阵），outer 总是稍微快一点。如果你运行 mat3 <- `<`(rep(u, times = ceiling(length(v)/length(u))), rep(v, rep.int(length(u), length(v)))) 会得到什么速度差异？这本质上就是 outer 在做的事情。 - SamR

可能是因为内存分配的问题。outer一次完成整个操作，因此需要分配大量内存，而for循环执行许多简单的操作。如果你在u <- rnorm(100) ; v <- rnorm(100)上测试它，你会发现outer更快。通常，这就是循环和向量化函数之间的权衡-如果操作简单但需要大量内存-循环更好，但如果操作复杂，则每次迭代都是昂贵的，而编译的代码则更可取。 - David Arenburg

两全其美：vapply(seq_along(v), \(i) u < v[i], logical(length(u))) - s_baldur

@sindri_baldur 是的，矩阵越大，vapply() 的表现就越好，对于很小的矩阵，outer() 的表现实际上更好。 - D.J

Answer 1

分配和销毁内存需要时间

如果您使用bench::press()并设置四个选项，您可以感受到具有最多内存分配的方法需要最长时间，正如David Arenburg在评论中所建议的那样。

这四个选项是：

1. outer()。
2. for循环。
3. vapply()（来自sindri_baldur的评论）。
4. `<`(rep(x), rep(y))（正是outer()在幕后执行的操作）。

我喜欢bench，因为它显示了内存使用情况。此图中的每个面板都显示了这四种方法在n*n矩阵和垃圾收集级别下的速度。

当数据行数为100时，vapply比其他方法慢，而在gc（垃圾回收）方面没有区别。

然而，一旦数据大于100行，我们可以看到vapply()的垃圾回收要少得多，速度也要快得多。

同样，在最后一个分面（1e4行和列），我们可以看到for循环的垃圾回收较少，倾向于比outer()更快。

vapply()使用的RAM最少

你可能会怀疑vapply()的垃圾回收较少是因为它留下了更多未被回收的垃圾。然而，如果我们查看总的RAM使用情况，我们可以看到它实际上只使用了outer()的三分之一的RAM：

注意：我不知道如何使用0字节创建一个1x1矩阵，但是如果您真的要比较两个标量，则可能根本不需要使用矩阵。

垃圾回收级别的含义是什么？

请参见R Internals一章中的The write barrier and the garbage collector：

引用：

有三个收集级别。级别0仅收集最年轻的一代，级别1收集最年轻的两代，级别2收集所有代。 20个level-0收集之后，下一个收集将在level 1进行，在5个level-1收集之后进入level 2。此外，如果级别n的收集未能提供20％的空闲空间（对于节点和向量堆的每个空间），则下一个收集将处于级别n + 1。（R级函数gc()执行level-2收集。）

理解这一点的方法是，如果函数正在创建更多的临时对象，然后销毁它们，它将做更多的分配并且有更多的垃圾回收。

运行模拟并生成第一个图的代码

sizes <- c(1, 1e2, 1e3, 1e4)

results <- bench::press(
    size = sizes,
    {
        set.seed(1)
        u <- rnorm(size)
        v <- rnorm(size)

        bench::mark(
            min_iterations = 10,
            check = FALSE,
            outer = {
                mat <- outer(u, v, `<`)
            },
            loop = {
                mat <- matrix(NA, nrow = length(u), ncol = length(v))
                for (i in seq_along(v)) {
                    mat[, i] <- u < v[i]
                }
                mat
            },
            vapply = {
                mat <- vapply(seq_along(v), \(i) u < v[i], logical(length(u)))
            },
            seq = {
                mat <- as.matrix(
                    `<`(
                        rep(u, times = ceiling(length(v) / length(u))),
                        rep(v, rep.int(length(u), length(v)))
                    ),
                    nrow = length(u)
                )
            }
        )
    }
)

ggplot2::autoplot(results) +
    ggplot2::facet_wrap(ggplot2::vars(size),scales="free_x")

第二个图的代码

library(ggplot2)
p  <- results  |>
    dplyr::mutate(
        expr = attr(expression, "description"),
        size = as.factor(size))  |>
    ggplot() +
        geom_col(aes(
            x = reorder(expr, mem_alloc),
            y = mem_alloc,
            fill = size
        ), color= "black") +
        facet_wrap(vars(size), scales="free_y") +
    labs(
        title = "Total RAM usage", 
        y = "Bytes", 
        x = "Expression"
    )

免责声明：这些结果是在一台机器上得出的（一台普通而又相对较旧的笔记本电脑）。我没有像你那样在outer()和for循环之间得到同样程度的差异，因此你的结果可能会有所不同。

- SamR