Armadillo C++：根据另外两个向量对向量进行排序

Question

我的问题与排序练习有关，我可以在 R 中轻松（但可能会很慢）进行排序，并且想在 C++ 中进行以加快我的代码速度。

考虑三个大小相同的向量 a、b 和 c。在 R 中，以下命令将首先根据 b 对向量进行排序，然后，如果出现平局，将进一步根据 c 进行排序。

a<-a[order(b,c),1]

示例：

a<-c(1,2,3,4,5)
b<-c(1,2,1,2,1)
c<-c(5,4,3,2,1)

> a[order(b,c)]
[1] 5 3 1 4 2

有没有一种有效的方法可以使用 Armadillo 向量在 C++ 中进行此操作？

Answer 1

我们可以编写以下 C++ 解决方案，我在文件中有它 SO_answer.cpp:

#include <RcppArmadillo.h>
// [[Rcpp::depends(RcppArmadillo)]]

using namespace arma;

// [[Rcpp::export]]
vec arma_sort(vec x, vec y, vec z) {
    // Order the elements of x by sorting y and z;
    // we order by y unless there's a tie, then order by z.
    // First create a vector of indices
    uvec idx = regspace<uvec>(0, x.size() - 1);
    // Then sort that vector by the values of y and z
    std::sort(idx.begin(), idx.end(), [&](int i, int j){
        if ( y[i] == y[j] ) {
            return z[i] < z[j];
        }
        return y[i] < y[j];
    });
    // And return x in that order
    return x(idx);
}

我们所做的是利用 std::sort() 允许您根据自定义比较器进行排序这一事实。我们使用比较器，仅当 y 的元素相等时才比较 z 的元素；否则它比较 y.¹ 的值然后我们可以编译文件并测试 R:

中的函数

library(Rcpp)
sourceCpp("SO_answer.cpp")

set.seed(1234)
x <- sample(1:10)
y <- sample(1:10)
z <- sample(1:10)

y[sample(1:10, 1)] <- 1 # create a tie

all.equal(x[order(y, z)], c(arma_sort(x, y, z))) # check against R
# [1] TRUE # Good

当然，我们还必须考虑这是否真的会给您带来任何性能提升，这就是您这样做的全部原因。让我们进行基准测试：

library(microbenchmark)
microbenchmark(r = x[order(y, z)],
               arma = arma_sort(x, y, z),
               times = 1e4)

Unit: microseconds
 expr    min    lq      mean median    uq      max neval cld
    r 36.040 37.23 39.386160  37.64 38.32 3316.286 10000   b
 arma  5.055  6.07  7.155676   7.00  7.53  107.230 10000  a

在我的机器上，小向量的速度似乎提高了大约 5-6 倍，但当你按比例放大时，这种优势并不适用：

x <- sample(1:100)
y <- sample(1:100)
z <- sample(1:100)

y[sample(1:100, 10)] <- 1 # create some ties

all.equal(x[order(y, z)], c(arma_sort(x, y, z))) # check against R
# [1] TRUE # Good

microbenchmark(r = x[order(y, z)],
               arma = arma_sort(x, y, z),
               times = 1e4)

Unit: microseconds
 expr   min     lq     mean median     uq      max neval cld
    r 44.50 46.360 48.01275 46.930 47.755  294.051 10000   b
 arma 10.76 12.045 16.30033 13.015 13.715 5262.132 10000  a 

x <- sample(1:1000)
y <- sample(1:1000)
z <- sample(1:1000)

y[sample(1:100, 10)] <- 1 # create some ties

all.equal(x[order(y, z)], c(arma_sort(x, y, z))) # check against R
# [1] TRUE # Good

microbenchmark(r = x[order(y, z)],
               arma = arma_sort(x, y, z),
               times = 1e4)

Unit: microseconds
 expr     min       lq     mean   median       uq      max neval cld
    r 113.765 118.7950 125.7387 120.5075 122.4475 3373.696 10000   b
 arma  82.690  91.3925 104.0755  95.2350  99.4325 6040.162 10000  a

它仍然更快，但是当您使用长度为 1000 的向量时，速度不到 2 倍。这可能就是 F. Privé said this operation should be fast enough in R. While moving to C++ using Rcpp can give you great performance advantages, the extent to which you get gains is largely dependent on context, as mentioned many times by Dirk Eddelbuettel 在这里回答各种问题的原因。

1 _{请注意，通常我建议使用 sort() 或 sort_index() 对 Armadillo 向量进行排序（请参阅 Armadillo 文档 here). If you're trying to sort a vec by the values of a second vec, you could usex(arma::sort_index(y)) as I indicated in an answer to a related question here。您甚至可以使用 stable_sort_index() 来保留关系。但是，我无法弄清楚如何使用这些功能来解决您在此处提出的具体问题。}

Armadillo C++：根据另外两个向量对向量进行排序

Armadillo C++: Sorting a vector in terms of two other vectors

c++

r

vector

armadillo

rcpp