c++ - 使用 Rcpp 复制 dplyr::group_by 的索引功能

Question

作为练习，我正在尝试使用 Rcpp 和 C++ 来获取分组索引，就像 dplyr::group_by 提供的一样。这些是数据中每个组对应的行号(从 0 开始)。

下面是索引的示例。

x <- sample(1:3, 10, TRUE)
x
# [1] 3 3 3 1 3 1 3 2 3 2

df <- data.frame(x)
attr(dplyr::group_by(df, x), "indices")
#[[1]]
#[1] 3 5
#
#[[2]]
#[1] 7 9
#
#[[3]]
#[1] 0 1 2 4 6 8

到目前为止，使用标准库的 std::unordered_multimap，我得出了以下结论:

// [[Rcpp::plugins(cpp11)]]

#include <Rcpp.h>
using namespace Rcpp;

typedef std::vector<int> rowvec;

// [[Rcpp::export]]
std::vector<rowvec> rowlist(std::vector<int> x)
{
    std::unordered_multimap<int, int> rowmap;
    for (size_t i = 0; i < x.size(); i++)
    {
        rowmap.insert({ x[i], i });
    }

    std::vector<rowvec> rowlst;
    for (size_t i = 0; i < rowmap.bucket_count(); i++)
    {
        if (rowmap.begin(i) != rowmap.end(i))
        {
            rowvec v(rowmap.count(i));
            int b = 0;
            for (auto it = rowmap.begin(i); it != rowmap.end(i); ++it, b++)
            {
               v[b] = it->second;
            }
            rowlst.push_back(v);
        }
    }
    return rowlst;
}

在单个变量上运行此结果

rowlist(x)
#[[1]]
#[1] 5 3
#
#[[2]]
#[1] 9 7
#
#[[3]]
#[1] 8 6 4 2 1 0

除了顺序颠倒之外，这看起来不错。但是，我不知道如何扩展它来处理:

• 不同的数据类型；该类型当前已硬编码到函数中
• 不止一个分组变量

(std::unordered_multimap 与 group_by 相比也很慢，但我稍后会处理。)任何帮助将不胜感激。

Answer 1

我已经考虑了这个问题很长一段时间，我的结论是至少可以说这是相当困难的。为了复制 dplyr::group_by 的魔力，您将不得不编写几个类，并设置一个非常巧妙的散列函数来处理各种数据类型和不同数量的列。我已经搜索了 dplyr 源代码，看起来如果您按照 ChunkMapIndex 的创建进行操作，你会得到更好的理解。

说到数据类型，我什至不确定使用 std::unordered_multimap 是否能得到你想要的，因为它不明智而且 difficult使用 double/float 数据类型作为您的键。

考虑到所有提到的挑战，下面的代码将产生与 attr(dplyr::group_by(df, x), "indices") 相同的整数类型输出。我设置它是为了让您开始思考如何处理不同的数据类型。它使用带有辅助函数的模板化方法，因为它是处理不同数据类型的简单有效的解决方案。辅助函数与 Dirk 提供的链接中的函数非常相似。

// [[Rcpp::plugins(cpp11)]]

#include <Rcpp.h>
#include <string>
using namespace Rcpp;

typedef std::vector<int> rowvec;
typedef std::vector<rowvec> rowvec2d;

template <typename T>
rowvec2d rowlist(std::vector<T> x) {

    std::unordered_multimap<T, int> rowmap;
    for (int i = 0; i < x.size(); i++)
        rowmap.insert({ x[i], i });

    rowvec2d rowlst;

    for (int i = 0; i < rowmap.bucket_count(); i++) {
        if (rowmap.begin(i) != rowmap.end(i)) {
            rowvec v(rowmap.count(i));
            int b = 0;
            for (auto it = rowmap.begin(i); it != rowmap.end(i); ++it, b++)
                v[b] = it->second;

            rowlst.push_back(v);
        }
    }

    return rowlst;
}

template <typename T>
rowvec2d tempList(rowvec2d myList, std::vector<T> v) {

    rowvec2d vecOut;

    if (myList.size() > 0) {
        for (std::size_t i = 0; i < myList.size(); i++) {
            std::vector<T> vecPass(myList[i].size());
            for (std::size_t j = 0; j < myList[i].size(); j++)
                vecPass[j] = v[myList[i][j]];

            rowvec2d vecTemp = rowlist(vecPass);
            for (std::size_t j = 0; j < vecTemp.size(); j++) {
                rowvec myIndex(vecTemp[j].size());
                for (std::size_t k = 0; k < vecTemp[j].size(); k++)
                    myIndex[k] = myList[i][vecTemp[j][k]];

                vecOut.push_back(myIndex);
            }
        }
    } else {
        vecOut = rowlist(v);
    }

    return vecOut;
}

// [[Rcpp::export]]
rowvec2d rowlistMaster(DataFrame myDF) {

    DataFrame::iterator itDF;
    rowvec2d result;

    for (itDF = myDF.begin(); itDF != myDF.end(); itDF++) {
        switch(TYPEOF(*itDF)) {
            case INTSXP: {
                result = tempList(result, as<std::vector<int> >(*itDF));
                break;
            }
            default: {
                stop("v must be of type integer");
            }
        }
    }

    return result;
}

它适用于多个分组变量，但速度没有那么快。

set.seed(101)
x <- sample(1:5, 10^4, TRUE)
y <- sample(1:5, 10^4, TRUE)
w <- sample(1:5, 10^4, TRUE)
z <- sample(1:5, 10^4, TRUE)
df <- data.frame(x,y,w,z)

identical(attr(dplyr::group_by(df, x, y, w, z), "indices"), rowlistMaster(df))
[1] TRUE

library(microbenchmark)
microbenchmark(dplyr = attr(dplyr::group_by(df, x, y, w, z), "indices"),
               challenge = rowlistMaster(df))
Unit: milliseconds
     expr       min        lq       mean     median         uq        max neval
    dplyr  2.693624  2.900009   3.324274   3.192952   3.535927   6.827423   100
challenge 53.905133 70.091335 123.131484 141.414806 149.923166 190.010468   100