Создайте большую непрерывную последовательность целых чисел:
x <- 1:1e20
Как R может вычислить sum
так быстро?
sum(x)
Разве он не должен перебирать 1e20 элементов в векторе и суммировать каждый элемент?
Подытоживая комментарии:
R представил нечто, называемое ALTREP или ALternate REPresentation для объектов R. Его цель состоит в том, чтобы сделать некоторые вещи более эффективными. Из https://www.r-project.org/dsc/2017/slides/dsc2017.pdf некоторые примеры включают:
Второй и четвертый пули кажутся здесь уместными.
Мы можем увидеть намек на это в действии, посмотрев на то, что, как я предполагаю, лежит в основе примитива 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)
, но не можем, так как не можем использовать оптимизацию суммирования последовательностей.
По касательной: я собирался попытаться суммировать seq(1, 1e10, by = 2)
, но R завершает работу с субъективной ошибкой «аргумент «по» слишком мал». :-)
Некоторое дополнительное чтение: Предварительный просмотр: ALTREP обещает значительно улучшить производительность R и ссылки в нем, например. ALTREP: альтернативные представления для R-объектов