Как утверждает @akrun, рекурсия в R обычно не так эффективна.Однако, если вам нужно рекурсивное решение, смотрите не дальше gtools::permutations.Вот реализация:
permGtools <- function(n, r, v) {
if (r == 1)
matrix(v, n, 1)
else if (n == 1)
matrix(v, 1, r)
else {
X <- NULL
for (i in 1:n) X <- rbind(X, cbind(v[i], permGtools(n - 1, r - 1, v[-i])))
X
}
}
Кстати, чтобы получить полный исходный код, просто наберите gtools::permutations в консоли и нажмите Enter.Для получения дополнительной информации см. Как просмотреть исходный код функции?
А вот некоторые временные параметры:
system.time(perm(1:8))
user system elapsed
34.074 10.641 44.815
system.time(permGtools(8,8,1:8))
user system elapsed
0.253 0.001 0.255
И просто для примера:
system.time(permGtools(9, 9, 1:9))
user system elapsed
2.512 0.046 2.567
Почему реализация OP медленнее?
Если вы не читаете подробности, перейдите к сводке.
ДляДля начала мы можем просто увидеть, что реализация OP делает более рекурсивные вызовы, чем реализация в gtools.Чтобы показать это, мы добавляем count <<- count + 1L в начало каждой функции (примечание. Мы используем оператор присваивания <<-, который сначала ищет в родительской среде).Например:
permGtoolsCount <- function(n, r, v) {
count <<- count + 1L
if (r == 1)
.
.
А теперь мы протестируем несколько длин:
iterationsOP <- sapply(4:7, function(x) {
count <<- 0L
temp <- permCount(1:x)
count
})
iterationsOP
[1] 65 326 1957 13700
iterationsGtools <- sapply(4:7, function(x) {
count <<- 0L
temp <- permGtoolsCount(x, x, 1:x)
count
})
iterationsGtools
[1] 41 206 1237 8660
Как видите, реализация OP делает больше вызовов в каждом случае.На самом деле, он в 1033 * раз превышает количество рекурсивных вызовов.
iterationsOP / iterationsGtools
[1] 1.585366 1.582524 1.582053 1.581986
Как мы уже говорили, рекурсия в R имеет плохую репутацию.Я не смог найти ничего точно определяющего, почему именно этот случай, кроме того, что R не использует хвостовую рекурсию .
На данный момент, трудно поверить, что создание примерно в 1,58 раза большеРекурсивные вызовы объясняют ускорение в 175 раз, которое мы видели выше (т. е. 44.815 / 0.255 ~= 175).
Мы можем профилировать код с помощью Rprof, чтобы получить дополнительную информацию:
Rprof("perm.out", memory.profiling = TRUE)
a1 <- perm(1:8)
Rprof(NULL)
summaryRprof("perm.out", memory = "both")$by.total
total.time total.pct mem.total self.time self.pct
"perm" 43.42 100.00 15172.1 0.58 1.34
"rbind" 22.50 51.82 7513.7 22.50 51.82
"rownames<-" 20.32 46.80 7388.7 20.30 46.75
"c" 0.02 0.05 23.7 0.02 0.05
"length" 0.02 0.05 0.0 0.02 0.05
Rprof("permGtools.out", memory.profiling = TRUE)
a2 <- permGtools(8, 8, 1:8)
Rprof(NULL)
summaryRprof("permGtools.out", memory = "tseries")$by.total
total.time total.pct mem.total self.time self.pct
"rbind" 0.34 100.00 134.8 0.18 52.94
"cbind" 0.34 100.00 134.8 0.08 23.53
"permGtools" 0.34 100.00 134.8 0.06 17.65
"matrix" 0.02 5.88 0.0 0.02 5.88
Одна вещь, которая выскакивает сразу (кроме времени), это огромное использование памяти реализацией OP.Реализация OP использует примерно 15 Гбайт памяти, тогда как реализация gtools использует только 134 Мб .
Копать глубже
В приведенном вышемы просто смотрим на использование памяти в общем виде, установив для параметра памяти значение both.Есть еще одна настройка, которая называется tseries, которая позволяет вам отслеживать использование памяти с течением времени.
head(summaryRprof("perm.out", memory = "tseries"))
vsize.small vsize.large nodes duplications stack:2
0.02 4050448 25558992 49908432 2048 "perm":"perm"
0.04 98808 15220400 1873760 780 "perm":"perm"
0.06 61832 12024184 1173256 489 "perm":"perm"
0.08 45400 0 861728 358 "perm":"perm"
0.1 0 14253568 0 495 "perm":"perm"
0.12 75752 21412320 1436120 599 "perm":"perm"
head(summaryRprof("permGtools.out", memory = "tseries"))
vsize.small vsize.large nodes duplications stack:2
0.02 4685464 39860824 43891512 0 "permGtools":"rbind"
0.04 542080 552384 12520256 0 "permGtools":"rbind"
0.06 0 0 0 0 "permGtools":"rbind"
0.08 767992 1200864 17740912 0 "permGtools":"rbind"
0.1 500208 566592 11561312 0 "permGtools":"rbind"
0.12 0 151488 0 0 "permGtools":"rbind"
Здесь много чего происходит, но на чем стоит остановиться, это поле duplications.Из документации на summaryRprof мы имеем:
Также записывается количество повторных вызовов внутренней функции во временном интервале.duplicate вызывается кодом C, когда необходимо скопировать аргументы.
Сравнение количества копий в каждой реализации:
sum(summaryRprof("perm.out", memory = "tseries")$duplications)
[1] 121006
sum(summaryRprof("permGtools.out", memory = "tseries")$duplications)
[1] 0
Итак, мы видим, что реализация OP требует много копийбыть произведенным.Я предполагаю, что это не удивительно, учитывая, что нужный объект является параметром в прототипе функции.Таким образом, P - это матрица перестановок, которая должна быть возвращена, и она постоянно увеличивается и увеличивается с каждой итерацией.И с каждой итерацией мы передаем ее perm.В реализации gtools вы заметите, что это не так, поскольку это просто два числовых значения и вектор для его параметров.
Сводка
Итак, у вас есть ОПоригинальная реализация не только делает более рекурсивные вызовы, но и требует много копий, которые, в свою очередь, приводят к потере памяти для резких ударов по эффективности.