Calculate mean max value per timeframe of array

user_4182658 0
Viewed 122

I have an array of data that is recorded by a sensor at 1 second time intervals. I am trying to calculate the max mean value for each time interval for the recorded data. If I have 2 hours worth of data, I want to calculate the max mean value for 1 second intervals, 2 second intervals, 3 second intervals etc... all the way up to 2 hours.

For example, given the following 3 values:

[8, 14, 11]

I want to return the following:

[
   {
      "Interval": 1,
      "MeanMax": 14,
   },
   {
      "Interval": 2,
      "MeanMax": 12.5,
   },
   {
      "Interval": 3,
      "MeanMax": 11,
   }
]

I have created the following function which is returning the correct value but it is very slow from a performance perspective. It takes approx 30 seconds to calculate the output for a 2 hour block of data. It is calculating all possible mean values for the given interval and then returning the largest.

let sampleData = Array.from({length: 20}, () => Math.floor(Math.random() * 20));
console.log("SampleData: " + sampleData)

let meanMaxByTimeFrame = [];

for(var intervalInSeconds = 1; intervalInSeconds <= sampleData.length; intervalInSeconds++){
    let allAveragesForCurrentInterval = [];
  for(var sampleDataIndex = 0; sampleDataIndex < sampleData.length; sampleDataIndex++){
    if((sampleDataIndex + intervalInSeconds) > sampleData.length){
        break;
    }
    let sum = sampleData.slice(sampleDataIndex, sampleDataIndex + intervalInSeconds).reduce((a, b) => a + b, 0);
    let avg = sum/intervalInSeconds;
    allAveragesForCurrentInterval.push(avg);
  }
  meanMaxByTimeFrame.push({'Interval': intervalInSeconds, 'MeanMax': Math.max.apply(Math, allAveragesForCurrentInterval)});
}

console.log(meanMaxByTimeFrame)

Any help would be much appreciated

math algorithm javascript
2 Answers

Good old imperative code will do. That, and using a windowing technique.

That is: we only need to scan the array once, for each window size:

[ 1, 2, 3, 4]
The sum of the first 3 elements is 6:
[ 1, 2, 3, 4]
 --------

The next sum is 6 - 1 (the element that goes out) + 4 (the element that goes in).


[ 1, 2, 3, 4]
    --------

So we keep the sum and divide by the window size to get the averages.

A full solution:

console.time();

function maxOfAverages(source, windowSize) {
  if (windowSize > source.length || windowSize < 1) return null;
  let sum = 0,
    idx = 0;

  while (idx < windowSize) sum += source[idx++];

  let maxOfAverages = sum / windowSize;

  while (idx < source.length) {
    sum = sum - source[idx - windowSize] + source[idx];
    const avg = sum / windowSize;
    if (avg > maxOfAverages) maxOfAverages = avg;
    idx++;
  }

  return maxOfAverages;
}

let sampleData = Array.from({ length: 2000 }, () =>
  Math.floor(Math.random() * 20)
);
console.log("SampleData: " + sampleData);

let meanMaxByTimeFrame = [];

for (let interval = 1; interval <= sampleData.length; interval++) {
  const meanMax = maxOfAverages(sampleData, interval);
  meanMaxByTimeFrame.push({ Interval: interval, MeanMax: meanMax });
}

console.timeEnd();

console.log(meanMaxByTimeFrame);

Disclaimer: this technique doesn't cope well with vastly different values. E.g., if there are more than 15 orders of magnitude of difference between minimum and maximum values, rounding errors are going to creep up in the sum. So, if you have lots of digits and very different numbers, you could want to recalculate the sum every time. Still, use while/for loops and leave the functional stuff to every non critical part of the application.

user_13957580

First you should not allways recalculate the upper-border from the loops. You could store these values before. But this will help you only a bit.
Second you allways recalculate the sum although you have done this without adding the last value before. In order to avoid this I store the sum in an new sumArray so I had only to add one and not all values. At the start with intervalInSeconds=1 I haven't any sum from before so I add instead nothing.

With this solution I could reduce the time e.g. for 1000 intervalls from 3100 ms to only 90 ms.

let sampleData = Array.from({length: 100}, () => Math.floor(Math.random() * 20));
console.log("SampleData: " + sampleData)

let meanMaxByTimeFrame = [];

let start = performance.now();

let sampleDataLength = sampleData.length;
let sampleDataMaxIndex = sampleDataLength;
let sumArray = [];

for(var intervalInSeconds = 1; intervalInSeconds <= sampleDataLength; intervalInSeconds++){
  let allAveragesForCurrentInterval = [];
  for(var sampleDataIndex = 0; sampleDataIndex < sampleDataMaxIndex; sampleDataIndex++){
    sumArray[sampleDataIndex] =  sampleData[sampleDataIndex+intervalInSeconds-1] + ((intervalInSeconds === 1) ? 0 : sumArray[sampleDataIndex]);
    let avg =  sumArray[sampleDataIndex]/intervalInSeconds;
    allAveragesForCurrentInterval.push(avg);
  }
  meanMaxByTimeFrame.push({'Interval': intervalInSeconds, 'MeanMax': Math.max.apply(Math, allAveragesForCurrentInterval)});
  sampleDataMaxIndex--;
}

console.log(meanMaxByTimeFrame)

let time = performance.now();
console.log('Duration: ' + (time - start) + ' ms.');

If you want to run it: https://jsfiddle.net/7f0zrnq2/1/

user_53245110
Related