为什么我的 Rcpp 实现查找唯一项的数量比基本 R 慢？

Question

我正在尝试编写一个函数来计算字符串向量中唯一项的数量（我的问题稍微复杂一些，但这是可重现的。我是根据我为 C++ 找到的答案这样做的。这里是我的代码：

C++

int unique_sort(vector<string> x) {
    sort(x.begin(), x.end());
    return unique(x.begin(), x.end()) - x.begin();
}

int unique_set(vector<string> x) {
    unordered_set<string> tab(x.begin(), x.end());
    return tab.size();
}

回复:

x <- paste0("x", sample(1:1e5, 1e7, replace=T))
microbenchmark(length(unique(x)),unique_sort(x), unique_set(x), times=3)

结果：

Unit: milliseconds
              expr        min         lq       mean     median         uq
 length(unique(x))   365.0213   373.4018   406.0209   381.7823   426.5206
    unique_sort(x) 10732.1918 10847.0532 10907.6882 10961.9146 10995.4363
     unique_set(x)  1948.6517  2230.3383  2334.4040  2512.0249  2527.2802

查看 unique 函数的 R 源代码（有点难以理解），它似乎在数组上使用循环将唯一元素添加到散列并检查该散列是否元素已经存在。

因此，我认为它应该等同于 unordered_set 方法。我不明白为什么 unordered_set 方法要慢 5 倍。

TLDR：为什么我的 C++ 代码很慢？

Answer 1

首先，请使示例可重现。以上缺少 Rcpp 属性、C++11 插件和必要的 header 导入。

其次，这里显示的问题是对 R 中的数据执行 深度复制 到C++ 结构。基准测试中的大部分时间都花在了复制过程中。此过程是由选择使用 std::vector<std::string> 而不是 Rcpp::CharacterVector 触发的，后者保存 SEXP、s-expression 或指向数据的指针。通过否定 Rcpp objects 提供的代理模型，它只执行 浅拷贝 ，将数据导入 C++[=45= 会立即产生成本] 比 Why is this simplistic cpp function version slower? 中描述的仅仅微秒大得多。

说了这么多，我们来说说如何修改上面的例子来使用Rcppobjects。首先，请注意 Rcpp objects 有一个名为 .sort() 的成员函数，它可以准确地对具有缺失值的 Rcpp::CharacterVector 进行排序（有关详细信息，请参阅 Rcpp FAQ Section 5.5: Sorting with STL on a CharacterVector produces problematic results，这假定没有大写或特殊语言环境）。其次，SEXP 类型可用作构造 std::unordered_set 的一种方式，即使数据作为 Rcpp::CharacterVector 导入也是如此。这些修改可以在 C++ 函数中找到，在它们的声明中带有 "native"。

#include <Rcpp.h> #include <unordered_set> #include <algorithm> // [[Rcpp::plugins(cpp11)]] // [[Rcpp::export]] int unique_sort(std::vector<std::string> x) { sort(x.begin(), x.end()); return unique(x.begin(), x.end()) - x.begin(); } // [[Rcpp::export]] int unique_set(std::vector<std::string> x) { std::unordered_set<std::string> tab(x.begin(), x.end()); return tab.size(); } // [[Rcpp::export]] int unique_sort_native(Rcpp::CharacterVector x) { x.sort(); return std::unique(x.begin(), x.end()) - x.begin(); } // [[Rcpp::export]] int unique_set_native(Rcpp::CharacterVector x) { std::unordered_set<SEXP> tab(x.begin(), x.end()); return tab.size(); }

测试代码：

# install.packages(c("microbenchmark")) # Note, it is more efficient to supply an integer rather than a vector # in sample()'s first parameter. x <- paste0("x", sample(1e5, 1e7, replace=T)) # Run a microbenchmark microbenchmark::microbenchmark( length(unique(x)), length(unique.default(x)), unique_sort(x), unique_set(x), unique_sort_native(x), unique_set_native(x), times = 10 )

输出：

Unit: milliseconds expr min lq mean median uq max neval length(unique(x)) 208.0 235.3 235.7 237.2 240.2 247.4 10 length(unique.default(x)) 230.9 232.8 238.8 233.7 241.8 266.6 10 unique_sort(x) 12759.4 12877.1 12993.8 12920.1 13043.2 13416.7 10 unique_set(x) 2528.1 2545.3 2590.1 2590.3 2631.3 2670.1 10 unique_sort_native(x) 7452.6 7482.4 7568.5 7509.0 7563.6 7917.8 10 unique_set_native(x) 175.8 176.9 179.2 178.3 182.3 183.4 10

因此，当使用 Rcpp objects 避免 深度复制 时，unique_set_native 函数击败 length(unique()) 调用大约 30毫秒。

为什么我的 Rcpp 实现查找唯一项的数量比基本 R 慢？

Why is my Rcpp implementation for finding the number of unique items slower than base R?

c++

r

rcpp