Member_2_2394978
asked on
Efficient moving window average implementation
Hi *,
I have the attached code, which I use to compute a moving window average. However, it is rather slow. Is there a more efficient way to implement it? Is there a built in function for this kind of thing.
outputTabs and outputTrel are waht I want moving averages of.
I am using Octave, however as it is so similar to Matlab any suggestions for Matlab would also be useful, and I may be able to implement it in Octave as well.
Many thanks,
James
I have the attached code, which I use to compute a moving window average. However, it is rather slow. Is there a more efficient way to implement it? Is there a built in function for this kind of thing.
outputTabs and outputTrel are waht I want moving averages of.
I am using Octave, however as it is so similar to Matlab any suggestions for Matlab would also be useful, and I may be able to implement it in Octave as well.
Many thanks,
James
inc = 1000;
windowWidth = 1000;
beginning = 1;%finish-windowWidth-inc;
k = 1;
for start=beginning:inc:finish-windowWidth
% Find window of absolute spikes
window1 = find(outputTabs(numberIndices{n})<=start+windowWidth);
window2 = find(outputTabs(numberIndices{n}(window1))>=start);
window = outputTrel(numberIndices{n}(window1(window2)));
if numel(window)>0
avg{n}(k) = mean(window);
error{n}(k) = std(window);
numInPat{n}(k) = (100/(numel(window)))*(numel(find(window>0)));
else
avg{n}(k) = 0;
error{n}(k) = 0;
numInPat{n}(k) = 0;
end
k = k + 1;
end
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
For standard deviation remember that stddev = sqrt(mean(x^2) - mean(x)^2) so if you use phoffric's excellent suggestion to speed up the means, also track the mean of the squares so you can get the stddev just as quickly.
In case the above formula is diffucult to read:
standard deviation = square root of (the average of the X^2 values minus the square of the mean)
In case the above formula is diffucult to read:
standard deviation = square root of (the average of the X^2 values minus the square of the mean)
One way to calculate moving average without for loop is using build in MATLAB FILTER function:
http://www.mathworks.com/help/techdoc/ref/filter.html
See the Example section.
However, this works if the signal is spaced regularly. It looks like this is not your case since you have to find outputTabs values in a current window. I don't think you can avoid loops.
One possible way to speed this up is to avoid running find operation across whole outputTabs vector all the times.
First, store temporary vectors into a variables. Indexing and other operations do take time. For example, why you have to index outputTabs(numberIndices{n }) at every loop?
Second, make sure the vector is sorted. Since your segments for moving average are not overlapping, you can take advantage removing those values that has been used already.
Something like this (I didn't test it, sorry for possible mistakes):
If you want more help please make your code runnable defining all variables and providing small data to test.
http://www.mathworks.com/help/techdoc/ref/filter.html
See the Example section.
However, this works if the signal is spaced regularly. It looks like this is not your case since you have to find outputTabs values in a current window. I don't think you can avoid loops.
One possible way to speed this up is to avoid running find operation across whole outputTabs vector all the times.
First, store temporary vectors into a variables. Indexing and other operations do take time. For example, why you have to index outputTabs(numberIndices{n
Second, make sure the vector is sorted. Since your segments for moving average are not overlapping, you can take advantage removing those values that has been used already.
Something like this (I didn't test it, sorry for possible mistakes):
tmpTabs = outputTabs(numberIndices{n});
tmpTrel = outputTrel(numberIndices{n});
lastfound = 0;
for start=beginning:inc:finish-windowWidth
winidx = find(tmpTabs(lastfound=1:end)>=start && tmpTabs(lastfound=1:end)<=start+windowWidth);
if numel(winidx)>0
window = tmpTrel(winidx+lastfound);
lastfound = winidx(end);
...
else
...
end
end
If you want more help please make your code runnable defining all variables and providing small data to test.
I forgot, that you are running Octave, not MATLAB. As for FILTER function, I think Octave has it. Hope other thoughts will be also compatible.
as it is a convolution why not using the conv function?
conv() and kernel with (ones(windowsize)/windowsi ze
I've tested it out and its quite fast:
conv() and kernel with (ones(windowsize)/windowsi
I've tested it out and its quite fast:
len = [10000,300000,2000000];
windowsize = 2000;
% convolution
for turn=1:numel(len)
randomsignal = rand(len(turn),1);
tic
kernel = ones(windowsize,1)/windowsize;
movingavg_c = conv(randomsignal,kernel);
toc
end
Elapsed time is 0.012252 seconds.
Elapsed time is 0.330076 seconds.
Elapsed time is 2.189201 seconds.
ASKER
Many thanks for all your suggestions.
phorric, your suggestions is very elegant however for simplicity I think Kendor's suggestion lends itself better to Octave/Matlab. If I was doing this in C (and I may be) this this would be perfect (and I shall remember it!).
yuk99: as you point out the code I already have could be made more streamline, however it still seems to be going quite slow do to the loops.
Kendor: is there a way to do the std like this as well? I can't think how to form the kernel.
Many thanks,
James
phorric, your suggestions is very elegant however for simplicity I think Kendor's suggestion lends itself better to Octave/Matlab. If I was doing this in C (and I may be) this this would be perfect (and I shall remember it!).
yuk99: as you point out the code I already have could be made more streamline, however it still seems to be going quite slow do to the loops.
Kendor: is there a way to do the std like this as well? I can't think how to form the kernel.
Many thanks,
James
James,
My implementation in matlab (years ago) was extremely easy. A convolution has many more operations. You should try to implement the moving average suggestion in octave, and you should see a significant performance improvement.
Paul
My implementation in matlab (years ago) was extremely easy. A convolution has many more operations. You should try to implement the moving average suggestion in octave, and you should see a significant performance improvement.
Paul
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
remains to say that the implementation you choose depends on how good/fast matlab/octave has implemented either conv or filter - I believe they must be super fast as they are often used. Otherwise you better go with phoffrics style of implementation.
you find some pseudo codeand nice explanation here:
http://www.dspguide.com/ch2/2.htm
you find some pseudo codeand nice explanation here:
http://www.dspguide.com/ch2/2.htm
ASKER
Many thanks to all for suggestions.
Cheers,
James
Cheers,
James
MATLAB has a function that gets the mean and standard deviation at the same time. If you have a function like that it could speed it up a bit.