r - R如何能够如此快速地对整数序列求和？

Question

创建一个大的连续整数序列:

x <- 1:1e20

R 如何能够如此快速地计算和？

sum(x)

它不是必须循环遍历向量中的 1e20 个元素并对每个元素求和吗？

Answer 1

评论总结:

R 引入了一种称为 ALTREP 的东西，即 R 对象的 ALternate REPresentation。它的目的是更有效地做一些事情。来自 https://www.r-project.org/dsc/2017/slides/dsc2017.pdf , 一些例子包括:

• 允许向量数据在内存映射文件中或分布式
• 允许算术序列的紧凑表示；
• 允许向对象添加元数据；
• 允许推迟计算/分配；
• 支持环境的替代表示。

第二个和第四个项目符号在这里似乎很合适。

我们可以通过查看我推断的是 altreps 的 R sum 原语的核心，在 https://github.com/wch/r-source/blob/7c0449d81c853f781fb13e9c7118065aedaf2f7f/src/main/altclasses.c#L262 处看到这方面的一些暗示。 :

static SEXP compact_intseq_Sum(SEXP x, Rboolean narm)
{
#ifdef COMPACT_INTSEQ_MUTABLE
    /* If the vector has been expanded it may have been modified. */
    if (COMPACT_SEQ_EXPANDED(x) != R_NilValue) 
    return NULL;
#endif
    double tmp;
    SEXP info = COMPACT_SEQ_INFO(x);
    R_xlen_t size = COMPACT_INTSEQ_INFO_LENGTH(info);
    R_xlen_t n1 = COMPACT_INTSEQ_INFO_FIRST(info);
    int inc = COMPACT_INTSEQ_INFO_INCR(info);
    tmp = (size / 2.0) * (n1 + n1 + inc * (size - 1));
    if(tmp > INT_MAX || tmp < R_INT_MIN)
    /**** check for overflow of exact integer range? */
    return ScalarReal(tmp);
    else
    return ScalarInteger((int) tmp);
}

也就是说，没有间隙的整数序列的缩减是微不足道的。当存在间隙或 NA 时，事情就会变得有点复杂。

在行动中:

vec <- 1:1e10
sum(vec)
# [1] 5e+19
sum(vec[-10])
# Error: cannot allocate vector of size 37.3 Gb
### win11, R-4.2.2

理想情况下我们会看到 sum(vec) == (sum(vec[-10]) + 10)，但我们不能，因为我们不能使用序列求和的优化.