c++ - R と Rcpp で最大 n 個の一意の値とその頻度を見つける

Question

数値ベクトル v (既に省略された NA) があり、n 番目に大きい値とそれぞれの頻度を取得したいと考えています。

http://gallery.rcpp.org/articles/top-elements-from-vectors-using-priority-queue/ は非常に高速であることがわかりまし た。

// [[Rcpp::export]]
std::vector<int> top_i_pq(NumericVector v, unsigned int n)
{

typedef pair<double, int> Elt;
priority_queue< Elt, vector<Elt>, greater<Elt> > pq;
vector<int> result;

for (int i = 0; i != v.size(); ++i) {
    if (pq.size() < n)
      pq.push(Elt(v[i], i));
    else {
      Elt elt = Elt(v[i], i);
      if (pq.top() < elt) {
        pq.pop();
        pq.push(elt);
      }
    }
  }

  result.reserve(pq.size());
  while (!pq.empty()) {
    result.push_back(pq.top().second + 1);
    pq.pop();
  }

  return result ;

}

ただし、絆は尊重されません。実際、インデックスは必要ありません。値を返すことも問題ありません。

私が取得したいのは、値と頻度を含むリストです。次のように言います。

numv <- c(4.2, 4.2, 4.5, 0.1, 4.4, 2.0, 0.9, 4.4, 3.3, 2.4, 0.1)

top_i_pq(numv, 3)
$lengths
[1] 2 2 1

$values
[1] 4.2 4.4 4.5

n は通常、v の長さに比べて小さいため (簡単に >1e6 になる可能性があります)、一意のベクトル、テーブル、または (完全な) 並べ替えを取得することはお勧めできません。

これまでの解決策は次のとおりです。

 library(microbenchmark)
 library(data.table)
 library(DescTools)

 set.seed(1789)
 x <- sample(round(rnorm(1000), 3), 1e5, replace = TRUE)
 n <- 5

 microbenchmark(
   BaseR = tail(table(x), n),
   data.table = data.table(x)[, .N, keyby = x][(.N - n + 1):.N],
   DescTools = Large(x, n, unique=TRUE),
   Coatless = ...
 )

Unit: milliseconds
       expr       min         lq       mean     median        uq       max neval
      BaseR 188.09662 190.830975 193.189422 192.306297 194.02815 253.72304   100
 data.table  11.23986  11.553478  12.294456  11.768114  12.25475  15.68544   100
  DescTools   4.01374   4.174854   5.796414   4.410935   6.70704  64.79134   100

うーん、DescTools はまだ最速ですが、Rcpp によって大幅に改善されると確信しています (純粋な R であるため)。