Sliding Windows

Let’s assume you would like to sum up all k-tuples in an array like this:

1
2
3
   [0, 1, 2, 3, 4, 5, 6]
=> [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
=> [1, 3, 5, 7, 9, 11]  (here k is 2)

In a language with functional programming elements (like D), you could do the following:

1
2
3
4
5
6
auto i = 0;
generate!(
  () => inputArray[i .. min(i++ + k, inputArray.length)]
         )
          .take(inputArray.length - k +1)
          .map!(sum);

However, for large inputArrays and large k, this takes an unreasonable time, since for each tuple the sum is calculated individually again.

1
2
3
4
5
6
auto v = inputArray[0 .. k].sum;
for (int i = 0; i < inputArray.length - k; i++) {
    v -= inputArray[i];
    v += inputArray[i + k];
    // Do something with the sum of the k-th tuple.
}

This speeds up things a lot.

You may also like to have a look a this question on stackoverflow.com.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.