Ответ 1
Поскольку ответа на этот вопрос не было, я подумал, что поставил бы вопрос, что есть действительно лучший способ решить эту проблему - такую, которая также может быть потенциально в тысячи раз быстрее. (Если это не поможет, сообщите мне, но я думал, что здесь будет лучше, чем ничего)
Всякий раз, когда я слышу "скользящее среднее" или "скользящее окно", свертка FFT сразу же появляется у меня в голове. Это связано с тем, что он может справляться с этими типами проблем с помощью чрезвычайно эффективного. Поскольку все "скользящие" делаются за кулисами, я думаю, что у него также есть вся синтаксическая красота, о которой вы могли бы просить.
(Следующий код доступен в одном файле в https://gist.github.com/1320175)
Начнем с моделирования некоторых данных (я использую целые числа здесь для простоты, но, конечно, вам не нужно).
require(plyr)
set.seed(12345)
n = 10
n.sum = 2
a = sample.int(10, n, replace=T)
df = data.frame(n=1:n, a)
> df
n a
1 1 8
2 2 9
3 3 8
4 4 9
5 5 5
6 6 2
7 7 4
8 8 6
9 9 8
10 10 10
Теперь мы будем прекомпилировать n-a
за один раз.
n.minus.a = with(df, n - a)
Затем определите ядро k
, которое, когда свернуто с нашим входом n.minus.a
, выполнит суммирование (или усреднение/сглаживание/все остальное) к нашим данным.
k = rep(0, n)
k[1:n.sum] = 1
С помощью всех настроек мы можем определить функцию, которая эффективно выполняет эту свертку в частотной области через fft()
.
myConv <- function(x, k){
Fx = fft(x)
Fk = fft(k)
Fxk = Fx * Fk
xk = fft(Fxk, inverse=T)
(Re(xk) / n)[-(1:(n.sum-1))]
}
Синтаксис для выполнения этого приятный и простой:
> myConv(n.minus.a, k)
[1] -14 -12 -10 -5 4 7 5 3 1
Все это также происходит под капотом, когда вы используете функцию удобства convolve()
в R.
> convolve(n.minus.a, k)[1:(length(n.minus.a)-n.sum+1)]
[1] -14 -12 -10 -5 4 7 5 3 1
Теперь мы сравниваем это с ручным методом, чтобы показать, что все результаты эквивалентны:
> sliding(df, 2, function(df) with(df, data.frame(n = n[1], a = a[1], b = sum(n - a))))
n a b
1 1 8 -14
2 2 9 -12
3 3 8 -10
4 4 9 -5
5 5 5 4
6 6 2 7
7 7 4 5
8 8 6 3
9 9 8 1
Наконец, мы сделаем n=10^4
и протестируем все эти методы для скорости:
> system.time(myConv(n.minus.a, k))
user system elapsed
0.002 0.000 0.002
> system.time(convolve(n.minus.a, k, type='circ')[1:(length(n.minus.a)-n.sum+1)])
user system elapsed
0.002 0.000 0.002
> system.time(sliding(df, 2, function(df) with(df, data.frame(n = n[1], a = a[1], b = sum(n - a)))))
user system elapsed
7.944 0.018 7.962
Методы FFT возвращаются почти мгновенно, и даже с этим грубым временем почти в 4000 раз быстрее, чем ручной метод.
Конечно, в эту парадигму не может быть всякая проблема скольжения, но для таких числовых задач, как этот, используя sum()
(а также средние средневзвешенные значения и т.д.), он отлично работает. Во всяком случае, обычно стоит, по крайней мере, немного поработать над Google, чтобы узнать, доступно ли ядро фильтра, которое будет делать трюк для заданного пробля. Удачи!