快速确定整数向量的近似最大值

Question

我想利用使用 Rcpp 在整数向量上pmax(x, 0) = (x + abs(x)) / 2的事实来提高性能。

我写了一个幼稚的实现：

IntegerVector do_pmax0_abs_int(IntegerVector x) {
R_xlen_t n = x.length();
IntegerVector out(clone(x));
for (R_xlen_t i = 0; i < n; ++i) {
int oi = out[i];
out[i] += abs(oi);
out[i] /= 2;
}
return out;
}

这确实是高性能的;但是，如果包含任何大于.Machine$integer.max / 2的元素，它会调用未定义的行为x。

有没有办法快速确定向量是否小于.Machine$integer.max / 2？我考虑过位移，但这对负数无效。

Answer 1

如注释中所述，您可以使用int64_t获得中间结果。此外，不要将x复制到out，也不要在任何地方将out初始化为零是有意义的：

#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export]]
IntegerVector do_pmax0_abs_int(IntegerVector x) {
R_xlen_t n = x.length();
IntegerVector out(clone(x));
for (R_xlen_t i = 0; i < n; ++i) {
int oi = out[i];
out[i] += abs(oi);
out[i] /= 2;
}
return out;
}
// [[Rcpp::plugins(cpp11)]]
// [[Rcpp::export]]
IntegerVector do_pmax0_abs_int64(IntegerVector x) {
R_xlen_t n = x.length();
IntegerVector out = no_init(n);
for (R_xlen_t i = 0; i < n; ++i) {
int64_t oi = x[i];
oi += std::abs(oi);
out[i] = static_cast<int>(oi / 2);
}
return out;
}
/***R
ints <- as.integer(sample.int(.Machine$integer.max, 1e6) - 2^30)
bench::mark(do_pmax0_abs_int(ints),
do_pmax0_abs_int64(ints),
pmax(ints, 0))[, 1:5]
ints <- 2L * ints
bench::mark(#do_pmax0_abs_int(ints), 
do_pmax0_abs_int64(ints), 
pmax(ints, 0))[, 1:5]
*/

结果：

> Rcpp::sourceCpp('57310889/code.cpp')
> ints <- as.integer(sample.int(.Machine$integer.max, 1e6) - 2^30)
> bench::mark(do_pmax0_abs_int(ints),
+             do_pmax0_abs_int64(ints),
+             pmax(ints, 0))[, 1:5]
# A tibble: 3 x 5
expression                    min   median `itr/sec` mem_alloc
<bch:expr>               <bch:tm> <bch:tm>     <dbl> <bch:byt>
1 do_pmax0_abs_int(ints)     1.91ms   3.31ms     317.     3.82MB
2 do_pmax0_abs_int64(ints)   1.28ms   2.67ms     432.     3.82MB
3 pmax(ints, 0)              9.85ms  10.68ms      86.9   15.26MB
> ints <- 2L * ints
> bench::mark(#do_pmax0_abs_int(ints), 
+             do_pmax0_abs_int64(ints), 
+             pmax(ints, 0))[, 1:5]
# A tibble: 2 x 5
expression                    min   median `itr/sec` mem_alloc
<bch:expr>               <bch:tm> <bch:tm>     <dbl> <bch:byt>
1 do_pmax0_abs_int64(ints)   1.28ms   2.52ms     439.     3.82MB
2 pmax(ints, 0)              9.88ms  10.83ms      89.5   15.26MB

笔记：

• 如果没有no_init这两种C++方法同样快。
• 我已经从第二个基准中删除了原始方法，因为默认情况下bench::mark比较结果，并且原始方法对该特定输入产生错误的结果。