Wie kann ich einen gleitenden Durchschnitt eines Vektors (effizient) berechnen?

Question

Ich habe einen Vektor und ich möchte den gleitenden Durchschnitt davon berechnen (mit einem Fenster der Breite 5).

Zum Beispiel, wenn der Vektor in Frage [1,2,3,4,5,6,7,8], dann

• der erste Eintrag des resultierenden Vektors sollte die Summe aller Einträge in [1,2,3,4,5] (d.h. 15); Der zweite Eintrag des resultierenden Vektors sollte die Summe aller Einträge in [2,3,4,5,6] (d.
• usw.

Am Ende sollte der resultierende Vektor [15,20,25,30] sein. Wie kann ich das machen?

Answer 1

Die conv Funktion ist bis Ihre Gasse:

>> x = 1:8; 
>> y = conv(x, ones(1,5), 'valid') 

y = 
    15 20 25 30 

Benchmark

Drei Antworten, drei verschiedene Methoden ... Hier ist eine kurze Benchmark (verschiedene Eingangsgrößen, feste Fensterbreite von 5) unter Verwendung von timeit; fühlen Sie sich frei, Löcher darin zu stoßen (in den Kommentaren), wenn Sie denken, dass es verfeinert werden muss.

conv ergibt sich als der schnellste Ansatz; es ist etwa doppelt so schnell wie coin's approach (using filter) und etwa vier mal so schnell wie Luis Mendo's approach (using cumsum).

ist hier ein anderer Maßstab (feste Eingangsgröße von 1e4, unterschiedliche Fensterbreiten). Hier ist Luis Mendo's cumsum approach der klare Gewinner, weil seine Komplexität in erster Linie von der Länge der Eingabe bestimmt wird und unempfindlich für die Breite des Fensters ist.

Fazit

Um es zusammenzufassen, sollten Sie

• den conv Ansatz verwenden, wenn Ihr Fenster relativ klein ist,
• den cumsum Ansatz verwenden, wenn Ihr Fenster relativ groß ist.

-Code (für Benchmarks)

function benchmark 

    clear all 
    w = 5;     % moving average window width 
    u = ones(1, w); 
    n = logspace(2,6,60); % vector of input sizes for benchmark 
    t1 = zeros(size(n)); % preallocation of time vectors before the loop 
    t2 = t1; 
    th = t1; 

    for k = 1 : numel(n) 

     x = rand(1, round(n(k))); % generate random row vector 

     % Luis Mendo's approach (cumsum) 
     f = @() luisMendo(w, x); 
     tf(k) = timeit(f); 

     % coin's approach (filter) 
     g = @() coin(w, u, x); 
     tg(k) = timeit(g); 

     % Jubobs's approach (conv) 
     h = @() jubobs(u, x); 
     th(k) = timeit(h); 
    end 

    figure 
    hold on 
    plot(n, tf, 'bo') 
    plot(n, tg, 'ro') 
    plot(n, th, 'mo') 
    hold off 
    xlabel('input size') 
    ylabel('time (s)') 
    legend('cumsum', 'filter', 'conv') 

end 

function y = luisMendo(w,x) 
    cs = cumsum(x); 
    y(1,numel(x)-w+1) = 0; %// hackish way to preallocate result 
    y(1) = cs(w); 
    y(2:end) = cs(w+1:end) - cs(1:end-w); 
end 

function y = coin(w,u,x) 
    y = filter(u, 1, x); 
    y = y(w:end); 
end 

function jubobs(u,x) 
    y = conv(x, u, 'valid'); 
end 

---

function benchmark2 

    clear all 
    w = round(logspace(1,3,31)); % moving average window width 
    n = 1e4; % vector of input sizes for benchmark 
    t1 = zeros(size(n)); % preallocation of time vectors before the loop 
    t2 = t1; 
    th = t1; 

    for k = 1 : numel(w) 
     u = ones(1, w(k)); 
     x = rand(1, n); % generate random row vector 

     % Luis Mendo's approach (cumsum) 
     f = @() luisMendo(w(k), x); 
     tf(k) = timeit(f); 

     % coin's approach (filter) 
     g = @() coin(w(k), u, x); 
     tg(k) = timeit(g); 

     % Jubobs's approach (conv) 
     h = @() jubobs(u, x); 
     th(k) = timeit(h); 
    end 

    figure 
    hold on 
    plot(w, tf, 'bo') 
    plot(w, tg, 'ro') 
    plot(w, th, 'mo') 
    hold off 
    xlabel('window size') 
    ylabel('time (s)') 
    legend('cumsum', 'filter', 'conv') 

end 

function y = luisMendo(w,x) 
    cs = cumsum(x); 
    y(1,numel(x)-w+1) = 0; %// hackish way to preallocate result 
    y(1) = cs(w); 
    y(2:end) = cs(w+1:end) - cs(1:end-w); 
end 

function y = coin(w,u,x) 
    y = filter(u, 1, x); 
    y = y(w:end); 
end 

function jubobs(u,x) 
    y = conv(x, u, 'valid'); 
end 

Answer 2

Wenn Sie die Größe Ihrer Eingangsvektor erhalten wollen, schlage ich vor filter

>> x = 1:8; 
>> y = filter(ones(1,5), 1, x) 

y = 
    1  3  6 10 15 20 25  30 

>> y = (5:end) 

y = 
    15 20 25 30 

Answer 3

Eine weitere Möglichkeit besteht darin, zu verwenden cumsum.Dieser Ansatz erfordert wahrscheinlich weniger Operationen als conv tut: // uk:

x = 1:8 
n = 5; 
cs = cumsum(x); 
result = cs(n:end) - [0 cs(1:end-n)]; 

ein wenig Zeit zu sparen, können Sie die letzte Zeile von

%// clear result 
result(1,numel(x)-n+1) = 0; %// hackish way to preallocate result 
result(1) = cs(n); 
result(2:end) = cs(n+1:end) - cs(1:end-n);