Какой самый быстрый / самый эффективный способ найти младший значащий бит в целом числе в R? - PullRequest
Новая
       59

Какой самый быстрый / самый эффективный способ найти младший значащий бит в целом числе в R?

0 голосов
/ 19 января 2019

У меня вопрос, похожий на Какой самый быстрый способ вернуть позицию младшего значащего бита, заданного в целом числе в Python 3? , найти первый установленный бит в двоичном числе и Позиция младшего значащего бита, который установлен для для R. Мне нужно найти позицию младшего значащего установленного бита в целом числе в R. Решение, предложенное Spätzle это следующее: 

unlist(lapply(x, function(z) min(which(as.integer(intToBits(z)) == 1))-1))

Есть ли более эффективные способы сделать это?

Ответы [ 2 ]

0 голосов
/ 19 января 2019

Если у вас длинные векторы и вы хотите перейти на C ++, вам может помочь следующий код (вместе с Rcpp и функцией ffs из strings.h): 

#include <Rcpp.h>
#include <strings.h>
using namespace Rcpp;

// [[Rcpp::export]]
Rcpp::IntegerVector lsb(const IntegerVector x)
{
  IntegerVector res(x.size());
  std::transform(x.begin(), x.end(), res.begin(), ffs);
  return(res-1);  # To start from 0
}

Сохраните приведенный выше код в виде файла, скажем, lsb.cpp, и скомпилируйте его, используя sourceCpp("lsb.cpp") из пакета Rcpp.

Это немного быстрее - по крайней мере для более длинных входных векторов, где издержки становятся незначительными 

> x <- floor(runif(10000,1,2^31))
> microbenchmark::microbenchmark(f(x), g(x), lsb(x))
Unit: microseconds
   expr       min         lq        mean    median         uq       max neval
   f(x)   121.771   129.6360   168.91273   133.241   151.0110  1294.667   100
   g(x) 36165.757 40508.1740 50371.45183 42608.686 60460.5270 94664.255   100
 lsb(x)    25.767    26.8015    34.58856    33.035    35.2385   156.852   100
0 голосов
/ 19 января 2019

намного быстрее следующее: 

f <- function(x){
  log2(bitwAnd(x,-x))
}

Для сравнения: 

g <- function(x){
  unlist(lapply(x, function(z) min(which(as.integer(intToBits(z)) == 1))-1))
}

Быстрый тест: 

> library(microbenchmark)
> tests <- floor(runif(1000,1,2^31))
> sum(f(tests) == g(tests)) #just to check
[1] 1000
> microbenchmark(f(tests),g(tests))
Unit: microseconds
     expr      min        lq       mean   median        uq       max neval
 f(tests)   38.435   40.5515   45.82673   42.667   45.1355   146.337   100
 g(tests) 1985.940 2083.9680 2530.79036 2131.218 2287.4280 11749.204   100
...