Массив любого числа измерений разворачивается в один непрерывный блок байт. Двумерная матрица 3x3, трехмерный тензор и таблица из CSV в момент загрузки в NumPy выглядят для процессора одинаково: линейная последовательность ячеек с известным шагом. Главный практический вывод из этого прост: адрес элемента считается арифметикой по индексам, а скорость обхода зависит от того, совпадает ли порядок ваших циклов с порядком ячеек в памяти.
Для двумерного случая формула в row-major (построчно) такая: смещение = (i * M + j) * sizeof(T), где M - число столбцов, i - строка, j - столбец. В column-major (постолбцово) она меняется на смещение = (j * N + i) * sizeof(T), где N - число строк. Третьего варианта нет: многомерный массив линеаризуется одним из этих двух способов, и выбор определяет, попадают ли соседние по циклу элементы в одну кэш-линию.
Обход, который не совпадает с раскладкой, заставляет процессор загружать кэш-линию ради одного нужного значения. На больших матрицах разница между двумя порядками обхода может быть заметной, а точную величину измеряйте на своем железе: она зависит от размера кэша, шага обхода и типа данных.
Как массивы хранятся в памяти: от одномерного к многомерному
Адресация массива опирается на один факт: все элементы занимают непрерывный блок, а компилятор или интерпретатор знает базовый адрес блока и размер одного элемента. Любое обращение по индексу превращается в сложение и умножение, без поиска по таблицам и без переходов по цепочке указателей.
Логические измерения существуют только в исходном коде. В памяти всегда одна линейная лента байт, а количество измерений задает лишь формулу пересчета индекса в смещение.
Одномерный массив: линейная последовательность
Для одномерного массива формула минимальна: адрес(i) = base + i * sizeof(T). В C объявление int arr[5] резервирует 20 байт при 4-байтовом int, как в типичных 64-битных сборках Linux и Windows. Адрес arr[3] равен base + 12, а &arr[4] отстоит от &arr[0] ровно на 16 байт. Проверить раскладку можно этой же адресной арифметикой, без отладчика.
Список в Python устроен иначе: он хранит массив указателей по 8 байт на 64-битной платформе, а сами числа лежат отдельными объектами. Линейность сохраняется на уровне указателей, но не на уровне значений. Базовый адрес, выравнивание и различия статических и динамических массивов разобраны в статье Элементы массива лежат в непрерывной области памяти.
В NumPy одномерный массив float64 длины N имеет shape (N,) и strides (8,): шаг между соседними элементами равен 8 байтам. Это те же 8 байт, что и sizeof(double), просто выраженные в байтах на один индекс. Атрибут ndarray.strides определяет отображение индекса элемента в смещение в памяти: каждое значение strides — множитель индекса по соответствующей оси при вычислении смещения в байтах (numpy.ndarray — NumPy Manual).
Двумерный массив: строка за строкой или столбец за столбцом
Матрица 3x3 с числами от 1 до 9 в row-major ложится в память как 1 2 3 4 5 6 7 8 9. В column-major тот же набор выглядит как 1 4 7 2 5 8 3 6 9. Обе последовательности содержат одни и те же 9 значений, отличается только порядок.
В языке C массивы хранятся в row-major порядке: последний индекс изменяется быстрее всего (ISO/IEC 9899:2017). Тип массива в C описывает непрерывно размещенный непустой набор объектов с заданным типом элемента, поэтому int a[3][4] - это массив из 3 элементов, каждый из которых массив из 4 int, то есть один непрерывный блок. C использует row-major порядок (лексикографический порядок доступа) с индексацией от нуля (Row- and column-major order — Wikipedia).
Fortran использует column-major порядок (colexicographical access order) с индексацией от единицы, и двумерный массив в Fortran трактуется как набор столбцовых векторов (Arrays — Fortran Tutorial). Это отличается от C и некоторых других языков, где принят row-major. R также использует column-major порядок.
NumPy по умолчанию работает в C-порядке и принимает order='C' либо order='F' при создании массива или reshape (Memory layout of multi-dimensional arrays).
| Среда | Порядок по умолчанию | Как изменить |
|---|---|---|
| C, C++ | row-major | порядок задан типом массива, переключателя нет |
| Fortran | column-major | порядок задан языком |
| R | column-major | порядок задан языком |
| NumPy | C-порядок (row-major) | order='C' или order='F' |
Для MATLAB, LAPACK и BLAS в проверенных источниках подтверждения column-major по умолчанию не нашлось, поэтому здесь мы этот пункт не утверждаем.
Многомерный массив: обобщение на N измерений
Для N-мерного массива удобно ввести strides - шаги по каждому измерению. В row-major stride последнего измерения равен 1, а stride измерения k равен произведению размеров всех измерений после k. Для shape (2, 3, 4) получится strides (12, 4, 1) в элементах.
Адрес элемента считается как base + сумма по всем измерениям index[k] * stride[k]. Для элемента [1, 2, 3] в массиве (2, 3, 4) смещение равно 1*12 + 2*4 + 3*1 = 23 элемента. Формула не усложняется при росте размерности, растет только число слагаемых.
В NumPy атрибут ndarray.strides - это кортеж байтов для шага по каждому измерению при обходе массива, и каждое значение strides является множителем индекса по соответствующей оси при вычислении смещения в байтах (numpy.ndarray — NumPy Manual). Для (2, 3, 4) float64 это (96, 32, 8). Посмотреть фактические значения можно через arr.strides, и это самый быстрый способ проверить, копировался массив или нет.
Формула адресации двумерного массива: row-major и column-major
Для матрицы N строк на M столбцов с элементами размера S байт формулы выглядят так:
- row-major: адрес(i, j) = base + (i * M + j) * S
- column-major: адрес(i, j) = base + (j * N + i) * S
Пример: int a[3][4] с 4-байтовым int. Элемент a[2][1] лежит по смещению (2*4 + 1) * 4 = 36 байт от base. Последний элемент a[2][3] - по смещению 44 байта, а весь массив занимает 48 байт. Проверка формулы простая: смещение последнего элемента всегда равно (N*M - 1) * S.
Тот же логический элемент в column-major раскладке (Fortran integer a(3, 4), индексы с единицы) лежит по смещению (1*3 + 2) * 4 = 20 байт. Одни и те же данные, разные смещения. Это причина, по которой матрицу нельзя перенести между языками простым memcpy без пересчета индексов.
В NumPy при itemsize = 8 двумерный массив N x M в C-порядке имеет strides (M*8, 8), в Fortran-порядке (8, N*8). Матрица 10000x10000 float64 в C-порядке: strides (80000, 8). В F-порядке: (8, 80000).
Раскладку многомерных массивов в C, Java и Python, а также разницу между логическим индексом и физическим смещением подробно разбирает материал Массив в оперативной памяти - это непрерывный блок.
Порядок обхода и производительность: почему row-major быстрее для C, а column-major для Fortran
Процессор читает память не по байту, а кэш-линиями. В процессорах Intel x86 кэш-линии имеют размер 64 байта, и данные выбираются по 64 байта за раз; этот же размер соответствует burst-передаче DDR DRAM (Where is the L1 memory cache of Intel x86 processors documented?). Одна линия вмещает 16 значений float64 или 16 значений int32. Если цикл идет по элементам подряд, каждая линия используется целиком: одна загрузка дает 16 полезных чисел.
Если шаг обхода равен длине строки, из линии используется только одно значение. Для float64 и шага в 10000 элементов полезная доля составляет 8 байт из 64, то есть одна восьмая линии, а число обращений к памяти вырастает пропорционально. Аппаратный префетчер, который хорошо предсказывает последовательный доступ, такой шаг отслеживает хуже.
На матрице 10000x10000 float64 объемом 800 МБ данные не помещаются ни в один кэш. Обход по строкам читает каждую линию почти полностью, обход по столбцам тянет новую линию на каждой итерации. На таком размере разница во времени может быть заметной; конкретное число зависит от процессора, объема L3 и частоты памяти. На маленькой матрице 256x256 float64, а это 512 КБ и почти весь L2, разница может быть незаметна, поэтому эффект проверяют на реальном размере задачи.
Сложность алгоритма при этом не меняется: оба варианта делают N*M операций сложения. Меняется число промахов кэша, и именно оно дает множитель, из-за которого цикл с одинаковым количеством итераций может работать дольше. Формулы, работа кэш-линий и блочная обработка циклов описаны в статье Row-major и column-major: как порядок обхода многомерных массивов влияет на кэш и производительность.
NumPy с векторизованными операциями сам выбирает эффективный обход внутри C-кода, поэтому a.sum(axis=1) и a.sum(axis=0) на C-упорядоченном массиве расходятся по времени: первая сумма идет вдоль строк, вторая прыгает по столбцам с шагом в длину строки. На больших массивах разница измерима, хотя внутренние циклы NumPy оптимизированы и провала в разы обычно нет.
Практические примеры на C, Python и NumPy
C: расчет смещения и два порядка обхода
int a[3][4]; /* row-major, 48 байт */
/* смещение a[i][j] = (i * 4 + j) * 4 байт */
/* a[2][1] -> (2*4 + 1)*4 = 36 */
/* быстрый обход: j меняется внутри, шаг 1 элемент */
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += a[i][j];
/* медленный обход: шаг равен длине строки */
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += a[i][j];
Компилятор не всегда переставляет такие циклы сам. Для чисел с плавающей точкой перестановка меняет порядок сложений и итоговый результат, поэтому при строгой модели вычислений циклы переставляют вручную, а затем сверяют результат с эталоном.
Python: список списков и цена обхода по столбцам
import timeit
matrix = [[0] * 2000 for _ in range(2000)]
def by_rows(m):
s = 0
for row in m:
for v in row:
s += v
return s
def by_cols(m):
s = 0
for j in range(len(m)):
for i in range(len(m)):
s += m[i][j]
return s
# timeit.repeat(..., number=1) на ваших данных
Замеряйте на своих данных: timeit.repeat(..., number=1) покажет реальное соотношение. Ожидаемая картина такая: обход по строкам быстрее, потому что элементы строки лежат в одном массиве указателей, а обход по столбцам прыгает между 2000 разными списками. Отдельная проблема - память: матрица 2000x2000 хранит 4 миллиона указателей, это 32 МБ только на адреса, плюс объекты int.
Для 10000x10000 вложенный список потребует 100 миллионов указателей, около 800 МБ, а каждый int вне диапазона кэшированных малых чисел добавит еще около 28 байт. Для табличных данных такую структуру лучше не использовать.
NumPy: order, strides и векторизация
import numpy as np
a = np.zeros((10000, 10000), dtype=np.float64, order='C')
a.strides # (80000, 8)
b = np.zeros((10000, 10000), dtype=np.float64, order='F')
b.strides # (8, 80000)
a.sum(axis=1) # вдоль строк, шаг 8 байт
a.sum(axis=0) # по столбцам, шаг 80000 байт
np.ravel(a, order='K') # обход в порядке памяти
a.T.strides # (8, 80000): транспонирование без копии
Транспонирование через .T не копирует данные, а меняет strides: такие операции дают view, ссылающийся на те же данные, что и исходный массив (Memory layout of multi-dimensional arrays). NumPy вообще стремится создавать view, а не копии, поэтому изменение данных view изменяет данные исходного массива. Операции, которым нужен непрерывный блок, вызовут копирование, поэтому перед тяжелыми вычислениями проверяйте arr.flags['C_CONTIGUOUS'] и при необходимости вызывайте np.ascontiguousarray.
Про reshape в проверенных источниках подтверждено только общее стремление NumPy создавать view, а не копии; гарантировать, что reshape вернет именно представление, нельзя. Проверить факт копирования можно через np.shares_memory или посмотрев на атрибут .base результата.
Как оптимизировать обработку больших наборов данных: советы для DevOps и сисадминов
- Согласуйте порядок циклов с раскладкой. Для C и NumPy в C-порядке внешний цикл идет по строкам, внутренний по столбцам. Внутренний цикл всегда должен иметь шаг 1 элемент.
- Заменяйте циклы Python на векторизованные операции. Внутренние циклы NumPy написаны на C и обходят данные в правильном порядке без вашего участия. Ручной цикл по 10^8 элементов в Python проигрывает не в разы, а на порядки.
- Выбирайте order осознанно. Данные, которые читаются по строкам (логи, метрики по времени), лучше держать в C-порядке; если вы агрегируете один признак по всем записям, F-порядок убирает часть промахов кэша.
- Проверяйте strides и контигуальность. arr.strides и arr.flags показывают, что реально лежит в памяти, а не то, что вы предполагали после срезов и транспонирования.
- Не раздувайте объем впустую. Разреженные матрицы хранят иначе: разреженные форматы в SciPy могут выполнять операции быстрее и использовать меньше памяти, чем соответствующее плотное представление, и экономия растет с размером матрицы (Sparse Matrices — Matt Eding). Формат CSR использует три подмассива: data, indices и indptr. Но применять разреженные форматы стоит только при достаточной разреженности: хранить преимущественно ненулевую матрицу через несколько подмассивов контрпродуктивно. Критерии выбора формата и формулы оценки памяти собраны в статье Плотное и разреженное хранение массивов: критерии выбора формата.
Расчетный объем массива и фактическое потребление памяти расходятся из-за заголовков объектов, выравнивания и оверхеда аллокатора. Сравнить оценку с реальностью помогают профайлеры, методика измерений описана в материале Как измерить память под массивы.
Типичные ошибки при работе с многомерными массивами
- Путаница row-major и column-major на стыке языков. Матрица, записанная Fortran, при чтении C-кодом без пересчета индексов воспринимается транспонированной. Решение: фиксировать порядок явно и в NumPy читать такие данные с order='F'.
- Ошибка в ручном расчете индекса. Для int a[3][4] смещение считают как (i * 3 + j) вместо (i * 4 + j) и выходят за границы блока, читая чужие данные. Контрольная проверка: последний элемент лежит по смещению (N*M - 1) * S.
- Вложенные списки Python для больших матриц. 100 миллионов указателей занимают около 800 МБ, к ним добавляются объекты int, и это еще до начала вычислений.
- Игнорирование strides при reshape и срезах. Операция может вернуть копию, и потребление памяти удваивается незаметно для кода. Проверяйте np.shares_memory и атрибут .base.
- Обход двумерного массива во вложенных циклах не в том порядке. Результат совпадает с правильным, но время работы может вырасти. На ревью такой код выглядит корректно, поэтому порядок циклов проверяют отдельно.
Итог: что важно запомнить о хранении и адресации массивов
- Массив хранится линейно: base плюс смещение, и для двумерного случая правило не меняется.
- Row-major: адрес(i, j) = base + (i * M + j) * S. Column-major: адрес(i, j) = base + (j * N + i) * S.
- Многомерность описывается через strides, адрес равен base + сумма index[k] * stride[k].
- C и C++ работают построчно, Fortran и R - постолбцово, NumPy позволяет задать порядок через order='C' или order='F'.
- Порядок обхода задает число промахов кэша: при шаге, равном длине строки, из 64-байтовой линии используется 8 байт для float64.
- В NumPy контролируйте arr.strides, arr.flags['C_CONTIGUOUS'] и копирование при reshape, а тяжелые вычисления выполняйте векторизованно.
- Для разреженных наборов выбирайте формат хранения под нагрузку: плотный массив или CSR, разница в объеме может быть существенной.
Практический шаг прямо сейчас: возьмите свой самый тяжелый цикл по массиву, проверьте порядок обхода через strides и сравните время двух вариантов обхода на реальном размере данных. Если разница есть, перестановка циклов даст ускорение без изменения логики и без потери точности.