Maximum Fixed-Length Contiguous Subarray

I recently taught a course about improving code for performance. An obvious performance improvement is to not execute unnecessary operations. I lacked a good example when I gave the course, but here is one: Find value of the largest contiguous sub-array of fixed length in a huge array.

This is a toy example, of course, but it shows the idea quite well.

The Code is on GitHub.

Small Example

Input:

• array: [7, 9, 2, 0, 5, 2, 0, 1, 1, 2]
• sub-array length m = 3

Contiguous sub-arrays of the given length:

1. [7, 9, 2], value = 18
2. [9, 2, 0], value = 11
3. [2, 0, 5], value = 7
4. [0, 5, 2], value = 7
5. [5, 2, 0], value = 7
6. [2, 0, 1], value = 3
7. [0, 1, 1], value = 2
8. [1, 1, 2], value = 4

Output: 18

Inefficient Solution

The following solution makes use of the slicing notation. It is short, easy to read and mostly pretty efficient:

from typing import List


def find_biggest_subarray_slice(array: List[int], m: int) -> int:
    return max(sum(array[i : i + m]) for i in range(len(array) - m + 1))

Except that it has one flaw: It makes too many additions and accesses list elements way more often than necessary

Efficient Solution

from typing import List


def find_biggest_subarray_iterative(array: List[int], m: int) -> int:
    value = sum(array[0:m])
    largest_sub_array = value
    for remove, add in zip(array, array[m:]):
        value = value - remove + add
        largest_sub_array = max(value, largest_sub_array)
    return largest_sub_array

Comparison

The inefficient solution is in $\mathcal{O}((n - m) \cdot m)$, the efficient one is in $\mathcal{O}(n - m)$. So you will notice the difference clearly when you compare the execution times with big $m$.

The inefficient solution changes its execution time like as shown in the image below for increasing m and contant n = 100,000:

In contrast, the efficient solution looks like this:

Two things to notice:

• Worst-Case: For the inefficient solution, it is $m = n/2$. For the efficient solution, it is $m = 1$.
• Level: The efficient solution is always below 0.03s. The inefficient one is only for the best-case scenario ($n=m$) below that. And even then, the efficient solution is at 0.0008s whereas the inefficient one is at 0.001s.
• Speed-ups: If you look at $m = 60,000$, the more efficient solution gives a 1000× speedup!

See also

• Maximum Contiguous Subarray Sum