このissueを解決してなんかコントリビュート感を出したい。が、C++力なさすぎて実装をまったく追えないのでメモ。
arrange()の場合
まず、Hadleyが「We did work around this for arrange() though,」って言ってるのでそっちがどうなってるか見てみる。
arrange_implはこのへん。値をぜんぶquosureにしたあと、なにやらOrderVisitorsというやつをつくってそれをapply()するとインデックスが出てくるらしい。
variables.names() = quosures.names(); OrderVisitors o(variables, ascending, nargs); IntegerVector index = o.apply(); DataFrameSubsetVisitors visitors(data, data.names()); List res = visitors.subset(index, get_class(data));
これにDataFrameクラスが渡ったときの実装はここ。
OrderVisitors(DataFrame data) :
visitors(data.size()), n(data.size()), nrows(data.nrows())
{
for (int i = 0; i < n; i++)
visitors[i] = order_visitor(data[i], true, i);
}
order_visitor()はこのあたり。
template <bool ascending> OrderVisitor* order_visitor_asc_vector(SEXP vec); inline OrderVisitor* order_visitor(SEXP vec, const bool ascending, const int i) { try { if (ascending) { return order_visitor_asc<true>(vec); } else { return order_visitor_asc<false>(vec); } } catch (const Rcpp::exception& e) { bad_pos_arg(i + 1, e.what()); } }
なにやら場合分けがいろいろある。文字列（STRSXP）なのでOrderCharacterVectorVisitorImplが選ばれる。
template <bool ascending> inline OrderVisitor* order_visitor_asc_vector(SEXP vec) { switch (TYPEOF(vec)) { case INTSXP: return new OrderVectorVisitorImpl<INTSXP, ascending, Vector<INTSXP > >(vec); case REALSXP: return new OrderVectorVisitorImpl<REALSXP, ascending, Vector<REALSXP> >(vec); case LGLSXP: return new OrderVectorVisitorImpl<LGLSXP, ascending, Vector<LGLSXP > >(vec); case STRSXP: return new OrderCharacterVectorVisitorImpl<ascending>(vec); case CPLXSXP: return new OrderVectorVisitorImpl<CPLXSXP, ascending, Vector<CPLXSXP > >(vec); case VECSXP: {
OrderCharacterVectorVisitorImplはこのへん。
template <bool ascending> class OrderCharacterVectorVisitorImpl : public OrderVisitor { public: OrderCharacterVectorVisitorImpl(const CharacterVector& vec_) : vec(vec_), orders(CharacterVectorOrderer(vec).get()) {} inline bool equal(int i, int j) const { return orders.equal(i, j); } inline bool before(int i, int j) const { return orders.before(i, j); } SEXP get() { return vec; }
CharacterVectorOrdererはこのへんと見せかけつつ、
実装はこっち。
https://github.com/tidyverse/dplyr/blob/354b0851cbf7ef41ce9314269e6e677c8d4523dc/src/api.cpp#L95
で、このあたりがみそっぽい。
// retrieve unique strings from the set int n_uniques = set.size(); CharacterVector uniques(set.begin(), set.end()); CharacterVector s_uniques = Language("sort", uniques).fast_eval(); // order the uniques with a callback to R IntegerVector o = r_match(uniques, s_uniques);
要はRの実装であるsortを使ってるから大丈夫という。
row_number()の場合
このへん。
template <bool ascending> Result* row_number_asc(const RObject& data) { switch (TYPEOF(data)) { case INTSXP: return new RowNumber<INTSXP, ascending>(data); case REALSXP: return new RowNumber<REALSXP, ascending>(data); case STRSXP: return new RowNumber<STRSXP, ascending>(data); default: return 0; } }
RowNumberはこのへん。
で、このあたりが実際に並べ替えてるところっぽい。
Visitor visitor(slice);
std::sort(tmp.begin(), tmp.begin() + m, Comparer(visitor));
Comparerはそのちょっと上でtypedefされている。
typedef Compare_Single_OrderVisitor<Visitor> Comparer;
Compare_Single_OrderVisitorはこのあたり。
template <typename OrderVisitorClass> class Compare_Single_OrderVisitor { public: Compare_Single_OrderVisitor(const OrderVisitorClass& obj_) : obj(obj_) {} inline bool operator()(int i, int j) const { if (i == j) return false; if (obj.equal(i, j)) return i < j; return obj.before(i, j); } private: const OrderVisitorClass& obj; };
objは何かというと、ちょっと戻ってComperer()に渡されているvisitorの型Visitorはここで定義されている。
typedef OrderVectorVisitorImpl<RTYPE, ascending, Slice> Visitor;
OrderVectorVisitorImplの実装をみるとこんな感じ。
// version used for ascending = true template <int RTYPE, bool ascending, typename VECTOR> class OrderVectorVisitorImpl : public OrderVisitor { typedef comparisons<RTYPE> compare; public: /** * The type of data : int, double, SEXP, Rcomplex */ typedef typename Rcpp::traits::storage_type<RTYPE>::type STORAGE; OrderVectorVisitorImpl(const VECTOR& vec_) : vec(vec_) {} inline bool equal(int i, int j) const { return compare::equal_or_both_na(vec[i], vec[j]); } inline bool before(int i, int j) const { return compare::is_less(vec[i], vec[j]); } SEXP get() { return vec; } private: VECTOR vec; };
で、is_less()はこんな感じで<で比較してるだけなので、文字列を扱うとだめっぽい。
static inline bool is_less(STORAGE lhs, STORAGE rhs) { if (is_na(lhs)) return false; if (is_na(rhs)) return true; return lhs < rhs; }