Contiguous arrays and stride tricks in NumPy - Time & Space Complexity

Time Complexity: Contiguous arrays and stride tricks

O(n)

Understanding Time Complexity

We want to understand how accessing and manipulating contiguous arrays using stride tricks affects the time it takes to run code.

How does the way data is stored and accessed change the work done as the array grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(1000000)
window_size = 5

# Create a sliding window view using stride tricks
windows = np.lib.stride_tricks.sliding_window_view(arr, window_size)

# Sum each window
result = windows.sum(axis=1)

This code creates overlapping windows of size 5 over a large array and sums each window.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Summing each window of size 5 across the array.
• How many times: The sum operation repeats once for each window, about n - window_size + 1 times.

How Execution Grows With Input

As the array size grows, the number of windows grows roughly the same as the array length, so the total work grows proportionally.

Input Size (n)	Approx. Operations
10	~6 sums of 5 elements each = 30 operations
100	~96 sums of 5 elements each = 480 operations
1000	~996 sums of 5 elements each = 4980 operations

Pattern observation: The total operations increase roughly linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum all windows grows in direct proportion to the size of the input array.

Common Mistake

[X] Wrong: "Using stride tricks makes the operation constant time regardless of input size."

[OK] Correct: Stride tricks create views without copying data, but summing each window still requires visiting each element, so time grows with input size.

Interview Connect

Understanding how data layout and views affect performance helps you write efficient code and explain your choices clearly in interviews.

Self-Check

What if we changed the window size to grow with the input size? How would the time complexity change?

Practice

1. What does it mean when a NumPy array is contiguous?

easy

A. It has more than one dimension.

B. It contains only positive numbers.

C. Its data is stored in one continuous block of memory.

D. It is a copy of another array.

Solution

1. Step 1: Understand contiguous memory

   A contiguous array stores all its elements in one continuous block of memory, which helps with fast access and efficient computation.

2. Step 2: Compare with other options

   Options B, C, and D describe other properties unrelated to memory layout.

3. Final Answer:

   Its data is stored in one continuous block of memory. -> Option C

4. Quick Check:

   Contiguous = continuous memory block [OK]

Hint: Contiguous means data is stored without gaps [OK]

Common Mistakes:

• Confusing contiguous with array shape
• Thinking contiguous means sorted data
• Assuming contiguous means a copy

2. Which of the following is the correct way to create a view using NumPy stride tricks?

easy

A. np.array(arr, copy=True)

B. np.copy(arr).reshape(3,3)

C. arr.flatten()

D. np.lib.stride_tricks.as_strided(arr, shape=(3,3), strides=(8,8))

Solution

1. Step 1: Identify stride tricks usage

   The function np.lib.stride_tricks.as_strided creates a view with a new shape and strides without copying data.

2. Step 2: Check other options

   Options B, C, and D create copies or flatten arrays, not views with stride tricks.

3. Final Answer:

   np.lib.stride_tricks.as_strided(arr, shape=(3,3), strides=(8,8)) -> Option D

4. Quick Check:

   Stride tricks use as_strided() [OK]

Hint: Use as_strided() to create views with custom strides [OK]

Common Mistakes:

• Using copy() instead of as_strided()
• Flattening instead of changing strides
• Confusing reshape with stride tricks

3. What will be the output of this code?

import numpy as np
arr = np.arange(6)
view = np.lib.stride_tricks.as_strided(arr, shape=(3,), strides=(2*arr.itemsize,))
view[0] = 100
print(arr)

medium

A. [100 1 2 3 4 100]

B. [100 1 2 3 4 5]

C. [100 1 100 3 4 5]

D. [0 1 2 3 4 5]

Solution

1. Step 1: Understand stride and view

   The view selects elements with stride 2*itemsize, so it accesses arr[0], arr[2], arr[4]. Changing view[0] changes arr[0], changing view[1] changes arr[2], etc.

2. Step 2: Analyze the assignment and print

   view[0] = 100 sets arr[0] = 100. The print shows arr with arr[0] changed, arr[2] and arr[4] unchanged.

3. Final Answer:

   [100 1 2 3 4 5] -> Option B

4. Quick Check:

   Stride view modifies original array [OK]

Hint: Stride selects spaced elements; modifying view changes original [OK]

Common Mistakes:

• Assuming view is a copy, not a view
• Ignoring stride size effect
• Expecting all elements to change

4. Identify the error in this code snippet:

import numpy as np
arr = np.arange(4)
view = np.lib.stride_tricks.as_strided(arr, shape=(3,3), strides=(8,8))
print(view)

medium

A. The shape is incompatible with the original array size.

B. The strides are incorrect for the array's data type.

C. as_strided cannot be used on 1D arrays.

D. The code will run without errors and print a 3x3 view.

Solution

1. Step 1: Check shape vs original array size

   The original array has 4 elements, but the requested view shape is (3,3) = 9 elements, which is larger than original data.

2. Step 2: Understand stride_tricks constraints

   as_strided creates views without copying, so shape must fit within original data size. Here, it does not, causing invalid memory access.

3. Final Answer:

   The shape is incompatible with the original array size. -> Option A

4. Quick Check:

   View shape must fit original array size [OK]

Hint: View shape must not exceed original array size [OK]

Common Mistakes:

• Ignoring array size vs view shape
• Assuming as_strided copies data
• Misunderstanding stride meaning

5. You have a large 1D NumPy array representing sensor data. You want to create a 2D sliding window view of size 4 without copying data. Which approach correctly uses stride tricks to achieve this?

hard

A. Use np.lib.stride_tricks.as_strided with shape=(len(arr)-3, 4) and strides=(arr.itemsize, arr.itemsize).

B. Use arr.reshape(-1, 4) to create windows.

C. Use np.copy(arr).reshape(-1, 4) to avoid modifying original data.

D. Use arr.flatten() and then slice manually.

Solution

1. Step 1: Understand sliding window with stride tricks

   Sliding window views use as_strided with shape=(number_of_windows, window_size) and strides that move one element at a time for rows and one element for columns.

2. Step 2: Check options for correct usage

   Use np.lib.stride_tricks.as_strided with shape=(len(arr)-3, 4) and strides=(arr.itemsize, arr.itemsize). correctly sets shape and strides to create overlapping windows without copying. Options B and C reshape but do not create sliding windows. Use arr.flatten() and then slice manually. flattens but does not create windows.

3. Final Answer:

   Use np.lib.stride_tricks.as_strided with shape=(len(arr)-3, 4) and strides=(arr.itemsize, arr.itemsize). -> Option A

4. Quick Check:

   Sliding windows need as_strided with correct shape and strides [OK]

Hint: Sliding windows need as_strided with overlapping strides [OK]

Common Mistakes:

• Using reshape instead of stride tricks
• Copying data unnecessarily
• Incorrect stride values causing wrong windows