Memory layout (C-order vs Fortran-order) in NumPy - Performance Comparison

Time Complexity: Memory layout (C-order vs Fortran-order)

O(n * m)

Understanding Time Complexity

When working with numpy arrays, how data is stored in memory affects how fast operations run.

We want to see how the memory layout changes the time it takes to access array elements.

Scenario Under Consideration

Analyze the time complexity of iterating over a 2D numpy array in different memory orders.

import numpy as np

arr_c = np.arange(10000).reshape(100, 100)  # C-order by default
arr_f = np.asfortranarray(arr_c)            # Fortran-order copy

# Sum elements row-wise for C-order
sum_c = 0
for i in range(arr_c.shape[0]):
    for j in range(arr_c.shape[1]):
        sum_c += arr_c[i, j]

# Sum elements row-wise for Fortran-order
sum_f = 0
for i in range(arr_f.shape[0]):
    for j in range(arr_f.shape[1]):
        sum_f += arr_f[i, j]

This code sums all elements of two arrays with different memory layouts, accessing elements row by row.

Identify Repeating Operations

We look at the loops and how many times elements are accessed.

• Primary operation: Accessing each element in the 2D array.
• How many times: Once per element, total of n * m times (rows * columns).

How Execution Grows With Input

As the array size grows, the number of element accesses grows with the total number of elements.

Input Size (n x m)	Approx. Operations
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: The number of operations grows directly with the total number of elements.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to access all elements grows linearly with the total number of elements in the array.

Common Mistake

[X] Wrong: "Memory layout does not affect how fast we can access elements."

[OK] Correct: Accessing elements in the order they are stored in memory (like C-order for row-wise) is faster because it uses the CPU cache better, while accessing out-of-order causes slower memory reads.

Interview Connect

Understanding how memory layout affects performance shows you care about efficient data handling, a key skill in data science and programming.

Self-Check

"What if we changed the iteration to column-wise access on a C-order array? How would the time complexity and performance be affected?"