Проблема, с которой вы столкнетесь, связана с огромным количеством комбинаций.Даже если вы попытаетесь применить простое решение для сортировки каждой строки, это будет стоить много времени для количества строк, с которыми вы имеете дело.
Возьмем следующий пример с простым подходом, предложенным @Lennyy:
set.seed(123)
n <- 1e7
data <- data.frame(id = 1:n,
a1 = sample(letters, n, replace = T),
a2 = sample(letters, n, replace = T),
a3 = sample(letters, n, replace = T),
stringsAsFactors = FALSE)
system.time(t2 <- table(apply(data[,2:4], 1, function(x) paste0(sort(x), collapse = ","))))
user system elapsed
373.281 1.695 375.445
Это долго ...
Вот вывод для справки:
head(t2)
a,a,a a,a,b a,a,c a,a,d a,a,e a,a,f
603 1657 1620 1682 1759 1734
Нам нужно как-то быстро кодировать каждую строку, не беспокоясь о том, какиестолбец конкретный элемент пришел из.Кроме того, мы должны сделать это таким образом, чтобы гарантировать уникальность.
А как насчет хеш-таблицы?Мы легко можем сделать это с помощью Rcpp.
#include <Rcpp.h>
#include <unordered_map>
using namespace Rcpp;
// [[Rcpp::plugins(cpp11)]]
// [[Rcpp::export]]
IntegerVector countCombos(IntegerMatrix myMat, int numAttr, CharacterVector myAttr) {
unsigned long int numRows = myMat.nrow();
unsigned long int numCols = myMat.ncol();
std::unordered_map<std::string, int> mapOfVecs;
for (std::size_t i = 0; i < numRows; ++i) {
std::vector<int> testVec(numAttr, 0);
for (std::size_t j = 0; j < numCols; ++j) {
++testVec[myMat(i, j) - 1];
}
std::string myKey(testVec.begin(), testVec.end());
auto it = mapOfVecs.find(myKey);
if (it == mapOfVecs.end()) {
mapOfVecs.insert({myKey, 1});
} else {
++(it->second);
}
}
std::size_t count = 0;
IntegerVector out(mapOfVecs.size());
CharacterVector myNames(mapOfVecs.size());
for (const auto& elem: mapOfVecs) {
std::size_t i = 0;
for (auto myChar: elem.first) {
while (myChar) {
myNames[count] += myAttr[i];
--myChar;
}
++i;
}
out[count++] = elem.second;
}
out.attr("names") = myNames;
return out;
}
. Это дает большой выигрыш в эффективности по сравнению с другими опубликованными решениями:
myRows <- 1:nrow(data)
attrCount <- 26
matOfInts <- vapply(2:ncol(data), function(x) {
match(data[, x], letters)
}, myRows, USE.NAMES = FALSE)
system.time(t <- countCombos(matOfInts, attrCount, letters))
user system elapsed
2.570 0.007 2.579
Это в 100 раз быстрее !!!!
И вот результат:
head(t)
jkk ddd qvv ttu aaq ccd
1710 563 1672 1663 1731 1775
Проверка равенства (вывод в другом порядке, поэтому мы должны сначала отсортировать):
identical(sort(unname(t)), as.integer(sort(unname(t2))))
[1] TRUE
Пояснение
Функция countCombos принимает матрицу целых чисел.Эта матрица представляет индексы элементов уникальных атрибутов (в нашем примере это будет представлено letters).
Поскольку мы имеем дело с комбинациями с повторениями, мы можем легко представить их как частоту индексацииvector.
Вектор шаблона:
a b c d e y z
| | | | | | |
v v v v v v v
(0, 0, 0, 0, 0, ... 0, 0)
И вот как определенные комбинации отображаются:
aaa -->> (3, rep(0, 25))
zdd -->> dzd -->> ddz -->> (0, 0, 0, 2, rep(0, 21), 1)
Как только мы создали наш вектор, мы конвертируем егов строку, поэтому ddz становится:
ddz --> c((0,0,0,2, rep(0, 21),1) -->> `00020000000000000000000001`
И это ключ, который используется в нашем хеше.