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.