How are multi-dimensional arrays formatted in memory?

How Are Multi-Dimensional Arrays Formatted in Memory?

Multi-dimensional arrays in memory can be formatted in two main ways: row-major order and column-major order. The choice of format determines how elements of the array are stored in contiguous memory locations. Understanding these formats is crucial for efficient array manipulation and memory access patterns.

Row-Major Order

In row-major order, the elements of each row of a multi-dimensional array are stored in contiguous memory locations. This is the format used by C and C++.

Example

Consider a 2D array:

A = [
  [a00, a01, a02],
  [a10, a11, a12],
  [a20, a21, a22]
]

In row-major order, the elements are stored in memory as follows:

a00, a01, a02, a10, a11, a12, a20, a21, a22

Column-Major Order

In column-major order, the elements of each column of a multi-dimensional array are stored in contiguous memory locations. This is the format used by Fortran and MATLAB.

Example

Consider the same 2D array:

A = [
  [a00, a01, a02],
  [a10, a11, a12],
  [a20, a21, a22]
]

In column-major order, the elements are stored in memory as follows:

a00, a10, a20, a01, a11, a21, a02, a12, a22

Address Calculation

To access an element in a multi-dimensional array, you need to calculate its memory address based on the array's layout (row-major or column-major order).

Row-Major Order Address Calculation

For an element at position (i, j) in an array with dimensions m x n (m rows and n columns), the address can be calculated as:

address = base_address + (i * n + j) * element_size

Column-Major Order Address Calculation

For an element at position (i, j) in an array with dimensions m x n (m rows and n columns), the address can be calculated as:

address = base_address + (j * m + i) * element_size

Practical Examples

Row-Major Order in C/C++

In C/C++, arrays are stored in row-major order by default.

#include <stdio.h>

int main() {
    int array[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // Accessing elements
    printf("%d ", array[0][0]); // Output: 1
    printf("%d ", array[1][1]); // Output: 5
    printf("%d ", array[2][2]); // Output: 9

    return 0;
}

Column-Major Order in Fortran

In Fortran, arrays are stored in column-major order by default.

program main
    implicit none
    integer :: array(3, 3)
    array = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9], [3, 3])

    ! Accessing elements
    print *, array(1, 1)  ! Output: 1
    print *, array(2, 2)  ! Output: 5
    print *, array(3, 3)  ! Output: 9
end program main

Summary

• Row-Major Order: Stores rows of the array in contiguous memory locations. Used by languages like C and C++.
• Column-Major Order: Stores columns of the array in contiguous memory locations. Used by languages like Fortran and MATLAB.
• Address Calculation:
  • Row-Major Order: address = base_address + (i * n + j) * element_size
  • Column-Major Order: address = base_address + (j * m + i) * element_size

Understanding the memory layout of multi-dimensional arrays helps in writing efficient code, particularly for applications involving large data sets and performance-critical operations. For more in-depth knowledge and practical examples on programming concepts and data structures, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.