Что является самым быстрым способом в R вычислить рекуррентную последовательность определяется какОптимизация вычисления рекурсивной последовательности
x[1] <- x1
x[n] <- f(x[n-1])
Я предполагаю, что вектор х правильной длины выделяется заранее. Есть ли более разумный способ, чем просто цикл?
Вариант: распространить это на векторах:
x[,1] <- x1
x[,n] <- f(x[,n-1])
Ну, если вам нужно всю последовательность, как быстро он может быть? предполагая, что функция O (1), вы не можете сделать лучше, чем O (n), и прокрутка даст вам именно это.
Да, обычно существует немного постоянных опережений O() .. – gappy
И еще хуже, иногда вы можете получить O (n^2) в R, если вы делаете такие вещи, как замена всего объекта каждый раз, когда вы его модифицируете. Я думаю, что исходный вопрос состоял в том, чтобы избежать этой проблемы ... – Harlan
В общем случае синтаксис x $ y < - f (z) должен перераспределять x каждый раз, что было бы очень медленным, если x - большой объект. Но, оказывается, R имеет некоторые трюки, так что функция замены списка [[<- не перераспределяет весь список каждый раз. Так что я думаю, что вы можете достаточно эффективно сделать:
x[[1]] <- x1
for (m in seq(2, n))
x[[m]] <- f(x[[m-1]])
Единственным расточительным аспектом здесь является то, что вы должны сгенерировать массив длины п-1 для для цикла, который не является идеальным, но это, вероятно, не гигантский вопрос. Вы можете заменить его на цикл while, если хотите. Обычные приемы векторизации (lapply и т.д.) не будет работать здесь ...
(двойные скобки дают вам элемент списка, который является то, что вы, вероятно, хотите, а не одноточечного список.)
Для получения дополнительной информации см. Chambers (2008). Программное обеспечение для анализа данных. п. 473-474.
Вы можете рассмотреть возможность написания его в C/C++/Fortran и использовать удобный пакет inline для обработки, компоновки и загрузки для вас.
Конечно, ваша функция f() может быть реальным ограничением, если нужно оставаться функцией R. В примере Rcpp есть пример callback-from-C++-to-R, но для этого требуется немного больше работы, чем использование встроенного.
Dirk, можно передать указатель функции R на C? Я не думал. – gappy
Да, я просто посмотрел на него снова в источниках Rcpp. Это немного грязно в документах, которые мне нужно реорганизовать, - посмотрите в конце примера в примере (RcppExample) после загрузки Rcpp и соответствующего кода в файле src/RcppExample.cpp, а также в Rcpp.h и Rcpp.cpp. Не тривиально, но выполнимо. Было бы неплохо, если бы это было так. –
Что касается вопроса о том, может ли это быть полностью «векторизовано» каким-либо образом, я думаю, что ответ, вероятно, «нет». Основная идея программирования массива состоит в том, что операции применяются ко всему набору значений одновременно. Точно так же для вопросов «неудобно параллельных» вычислений. В этом случае, поскольку ваш рекурсивный алгоритм зависит от каждого предыдущего состояния, не будет возможности получить скорость от параллельной обработки: он должен запускаться последовательно.
Это, как говорится, обычный совет для ускорения вашей программы. Например, сделайте как можно больше вычислений вне вашей рекурсивной функции. Сортируй все. Предопределите длины массивов, чтобы они не могли расти во время цикла. И т.д. See this question for a similar discussion. Существует также пример псевдокода в Tim Hesterberg's article on efficient S-Plus Programming.
Решить рекуррентное отношения;)
IS F (х) представима в виде комбинации cumsum() 'с, cumprod()' ы? –
Несколько комментариев: i) итерация, а не рекурсия здесь не экономит много времени; ii) кажется, что единственный способ ускорить дело - это код C, возможно, встроенный. Я надеялся, что будет пакет, который мог бы сделать работу для меня выразительным образом. Не тот случай. – gappy
Является ли проблема, что f() очень медленная или что n очень велико?Возможно, вы сможете внести улучшения в R, если это последний случай, но да, переписывание f() в C может быть необходимо, если это первый ... – Harlan