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

Question

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

考虑三个大小相同的 vector a、b 和 c。在 R 中，以下命令将首先根据 b 对 vector 进行排序，然后，如果出现平局，将进一步根据 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 vector 在 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 

在我的机器上，小 vector 的速度似乎提高了大约 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 的 vector 时，它的速度不到 2 倍。这可能就是为什么 F. Privé 的原因。表示此操作在 R 中应该足够快。虽然使用 Rcpp 迁移到 C++ 可以为您带来巨大的性能优势，但您获得 yield 的程度在很大程度上取决于上下文，正如 Dirk Eddelbuettel 多次提到的那样。在这里回答各种问题。

---

1 _{请注意，通常我建议使用 sort() 或 sort_index() 对 Armadillo vector 进行排序(请参阅 Armadillo 文档 here )。如果您尝试根据第二个 vec 的值对 vec 进行排序，您可以使用 x(arma::sort_index(y)) 正如我在相关问题的回答中指出的那样 here .您甚至可以使用 stable_sort_index() 来保持平局。但是，我无法弄清楚如何使用这些功能来解决您在此处提出的具体问题。}