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

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;
}

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

有没有办法快速判断向量是否小于.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 默认情况下比较结果，并且原始方法为该特定输入产生了错误的结果。

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

Quickly determine the approximate maximum of an integer vector

rcpp