Найти самые большие n уникальных значений и их частоты в R и Rcpp

Я хотел бы бросить свою шляпу в кольцо с другим решением на основе Rcpp, которое примерно в 7 раз быстрее, чем DescTools подход и ~ 13x быстрее, чем data.table подход, используя длину 1e5 x а также n = 5 Пример данных выше. Реализация немного длинная, поэтому я приведу пример:

fn.dt <- function(v, n) {
data.table(v = v)[
,.N, keyby = v
][(.N - n + 1):.N]
}

microbenchmark(
"DescTools" = Large(x, n, unique=TRUE),
"top_n" = top_n(x, 5),
"data.table" = fn.dt(x, n),
times = 500L
)
# Unit: microseconds
#        expr      min       lq      mean   median       uq       max neval
#   DescTools 3330.527 3790.035 4832.7819 4070.573 5323.155 54921.615   500
#       top_n  566.207  587.590  633.3096  593.577  640.832  3568.299   500
#  data.table 6920.636 7380.786 8072.2733 7764.601 8585.472 14443.401   500

Обновить

Если ваш компилятор поддерживает C ++ 11, вы можете воспользоваться std::priority_queue::emplace для (удивительно) заметного прироста производительности (по сравнению с версией C ++ 98 ниже). Я не буду публиковать эту версию, поскольку она в основном идентична, за исключением нескольких звонков std::move а также emplace, но вот ссылка на него.

Тестирование по сравнению с предыдущими тремя функциями и использование data.table 1.9.7 (что немного быстрее, чем 1.9.6) дает

print(res2, order = "median", signif = 3)
# Unit: relative
#              expr  min    lq      mean median    uq   max neval  cld
#            top_n2  1.0  1.00  1.000000   1.00  1.00  1.00  1000    a
#             top_n  1.6  1.58  1.666523   1.58  1.75  2.75  1000    b
#         DescTools 10.4 10.10  8.512887   9.68  7.19 12.30  1000    c
#  data.table-1.9.7 16.9 16.80 14.164139  15.50 10.50 43.70  1000    d

где top_n2 это версия C ++ 11.

top_n Функция реализована следующим образом:

#include <Rcpp.h>
#include <utility>
#include <queue>

class histogram {
private:
struct paired {
typedef std::pair<double, unsigned int> pair_t;

pair_t pair;
unsigned int is_set;

paired()
: pair(pair_t()),
is_set(0)
{}

paired(double x)
: pair(std::make_pair(x, 1)),
is_set(1)
{}

bool operator==(const paired& other) const {
return pair.first == other.pair.first;
}

bool operator==(double other) const {
return is_set && (pair.first == other);
}

bool operator>(double other) const {
return is_set && (pair.first > other);
}

bool operator<(double other) const {
return is_set && (pair.first < other);
}

paired& operator++() {
++pair.second;
return *this;
}

paired operator++(int) {
paired tmp(*this);
++(*this);
return tmp;
}
};

struct greater {
bool operator()(const paired& lhs, const paired& rhs) const {
if (!lhs.is_set) return false;
if (!rhs.is_set) return true;
return lhs.pair.first > rhs.pair.first;
}
};

typedef std::priority_queue<
paired,
std::vector<paired>,
greater
> queue_t;

unsigned int sz;
queue_t queue;

void insert(double x) {
if (queue.empty()) {
queue.push(paired(x));
return;
}

if (queue.top() > x && queue.size() >= sz) return;

queue_t qtmp;
bool matched = false;

while (queue.size()) {
paired elem = queue.top();
if (elem == x) {
qtmp.push(++elem);
matched = true;
} else {
qtmp.push(elem);
}
queue.pop();
}

if (!matched) {
if (qtmp.size() >= sz) qtmp.pop();
qtmp.push(paired(x));
}

std::swap(queue, qtmp);
}

public:
histogram(unsigned int sz_)
: sz(sz_),
queue(queue_t())
{}

template <typename InputIt>
void insert(InputIt first, InputIt last) {
for ( ; first != last; ++first) {
insert(*first);
}
}

Rcpp::List get() const {
Rcpp::NumericVector values(sz);
Rcpp::IntegerVector freq(sz);
R_xlen_t i = 0;

queue_t tmp(queue);
while (tmp.size()) {
values[i] = tmp.top().pair.first;
freq[i] = tmp.top().pair.second;
++i;
tmp.pop();
}

return Rcpp::List::create(
Rcpp::Named("value") = values,
Rcpp::Named("frequency") = freq);
}
};// [[Rcpp::export]]
Rcpp::List top_n(Rcpp::NumericVector x, int n = 5) {
histogram h(n);
h.insert(x.begin(), x.end());
return h.get();
}

Там много всего происходит в histogram класс выше, но просто коснемся некоторых из ключевых моментов:

• paired Тип по сути является классом-оберткой вокруг std::pair<double, unsigned int>, который связывает значение с количеством, предоставляя некоторые удобные функции, такие как operator++() / operator++(int) для прямого пре- / постинкрементного подсчета и модифицированных операторов сравнения.
• histogram класс обертывает своего рода «управляемую» очередь приоритетов, в том смысле, что размер std::priority_queue ограничен определенным значением sz,
• Вместо использования по умолчанию std::less заказ std::priority_queueЯ использую компаратор больше, чем можно проверить значения кандидатов std::priority_queue::top() чтобы быстро определить, должны ли они (а) быть отброшены, (б) заменить текущее минимальное значение в очереди или (в) обновить счетчик одного из существующих значений в очереди. Это возможно только потому, что размер очереди ограничен <знак равно sz,