R 为何能够这么快地对整数序列求和？

Question

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

x <- 1:1e20

R 为何能够sum如此快地计算？

sum(x)

是否必须循环向量中的 1e20 个元素并对每个元素求和？

Answer 1

总结一下评论：

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

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

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

sum通过查看我推断的 altreps 的R 原语的核心内容，我们可以看到这一点的暗示，网址为https://github.com/wch/r-source/blob/7c0449d81c853f781fb13e9c7 ​​118065aedaf2f7f/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)，但我们不能，因为我们不能使用序列求和的优化。