🔴 Сложный ⏱️ 55 минут

Массивы и списки

📋 Содержание урока

Массивы и списки 📦

Открой любой ноутбук с моделью машинного обучения — неважно, обучаешь ли ты линейную регрессию на табличных данных, свёрточную сеть на изображениях или трансформер на текстах. Задолго до того, как речь зайдёт об архитектуре модели или функции потерь, ты столкнёшься с одной и той же строчкой: import numpy as np. Всё, с чем работает модель — признаки объекта, пиксели изображения, эмбеддинг слова, веса нейросети, — в конечном счёте хранится в структуре данных, которая называется массивом. Тензор PyTorch, ndarray NumPy, столбец pandas.DataFrame — это не какие-то экзотические изобретения индустрии искусственного интеллекта, а прямые потомки одной из самых старых и самых простых идей в программировании: разместить однотипные данные подряд в памяти и обращаться к ним по номеру.

Именно эта простота и есть источник силы массива. В прошлом уроке ты разобрался, почему $O(1)$ — лучшая возможная сложность операции: результат не зависит от размера входных данных вообще. Массив — это структура данных, которая по своей физической природе даёт тебе доступ к любому элементу ровно за такую сложность, и понимание того, почему это работает, — не абстрактная теория, а прямой ключ к пониманию, почему numpy.sum(array) отрабатывает на порядки быстрее, чем sum() над обычным Python-списком, почему X - X.mean() для матрицы признаков не требует ни одного явного цикла, и почему np.append() внутри цикла обучения модели — одна из самых частых причин, по которой чужой код внезапно "тормозит в 100 раз".

Урок построен вокруг одного центрального противопоставления: статический массив — жёсткая, но предсказуемая структура фиксированного размера, и динамический массив — гибкая надстройка над ней, которая умеет расти, оставаясь при этом эффективной "в среднем". Список в Python (list) — это динамический массив. NumPy-массив (numpy.ndarray) — гораздо ближе к статическому массиву в его первозданном, "низкоуровневом" виде, и именно поэтому он так хорошо годится на роль строительного блока для тензоров.

🎯 Ты узнаешь:

Что такое непрерывный блок памяти и почему именно он даёт доступу к элементу массива сложность $O(1)$
Как устроен динамический массив (список в Python) изнутри, что такое capacity, over-allocation и почему добавление элемента в конец — это амортизированная сложность $O(1)$, а не строго $O(1)$ на каждую отдельную операцию
Какая сложность у вставки и удаления элемента в начало, середину и конец массива — и почему это принципиально разные числа
Как хранятся в памяти многомерные массивы (матрицы, тензоры) — через понятие row-major order и strides
Почему NumPy-массив в десятки и сотни раз быстрее обычного цикла Python по тем же данным — и как это напрямую связано с непрерывностью памяти, отсутствием интерпретатора на каждой итерации и инструкциями SIMD процессора
Как тензоры PyTorch и TensorFlow буквально являются массивами фиксированной формы (shape) — и почему понимание массива снимает большую часть "магии" вокруг них

История: откуда это взялось?

Идея массива появилась вместе с самими цифровыми компьютерами, потому что она прямо вытекает из физического устройства памяти. Оперативная память компьютера — это, по сути, длинная пронумерованная лента ячеек: у каждой ячейки есть свой адрес, и процессор умеет обращаться по конкретному адресу за фиксированное время, независимо от того, находится он в начале ленты или в конце. Джон фон Нейман, чья архитектура компьютера легла в основу почти всех современных вычислительных машин, ещё в конце 1940-х годов явно закладывал в проекты компьютеров эту идею адресуемой памяти — а массив является, по сути, программной надстройкой над этим физическим фактом: если элементы данных одного размера расположить в памяти подряд, начиная с некоторого адреса, то адрес любого элемента можно вычислить простой арифметикой, не читая всё, что было раньше.

В языке FORTRAN, появившемся в 1957 году, массив был одной из считанных доступных программисту структур данных — и это не случайность, а прямое отражение того, для чего вообще создавался язык: инженерных и научных расчётов, где данные — это, как правило, векторы и матрицы чисел. Само слово FORTRAN расшифровывается как "FORmula TRANslation", и работа с массивами чисел была в нём гражданином первого класса задолго до того, как в других языках появились списки, словари или объекты. Любопытно, что именно из этой линии научных вычислений на Фортране (и его наследников — BLAS, LAPACK) выросли современные библиотеки линейной алгебры, на которых до сих пор в буквальном смысле работает NumPy: значительная часть тяжёлых вычислений в numpy.linalg и в глубоком обучении выполняется кодом, чьи алгоритмические корни уходят именно в эти фортрановские библиотеки полувековой давности.

Динамический массив как отдельная концепция — надстройка над статическим, умеющая расти, — оформился заметно позже, вместе с развитием языков программирования, ориентированных на удобство разработчика, а не только на близость к железу: std::vector в C++ (стандартная библиотека STL, 1990-е), ArrayList в Java, список list в Python. Идея во всех этих реализациях одна и та же — выделять памяти немного "с запасом" и лишь изредка, когда запас заканчивается, перевыделять больший блок и переносить туда все элементы. А сам NumPy в его современном виде появился в 2005 году, когда Трэвис Олифант объединил две конкурировавшие на тот момент библиотеки для Python — Numeric и Numarray — в единый проект. Ключевой мотивацией было именно то, о чём пойдёт речь во второй половине этого урока: обычный список Python плохо приспособлен для быстрых вычислений над большими объёмами однотипных чисел, а научному и инженерному сообществу, привыкшему к Фортрану и MATLAB, нужен был инструмент, дающий скорость статического массива при удобстве языка высокого уровня.

Статический массив: непрерывный блок памяти

Интуиция: шкафчики в один ряд

Представь длинный ряд одинаковых пронумерованных шкафчиков в раздевалке. Шкафчик номер 0 стоит первым, следующий за ним — номер 1, и так далее, без пропусков. Если тебе нужно попасть ровно в шкафчик номер 47, тебе не нужно проходить мимо всех предыдущих сорока семи — ты точно знаешь, что он находится на строго определённом расстоянии от начала ряда, и идёшь прямо туда. Это и есть суть статического массива: элементы одного и того же размера стоят в памяти строго подряд, без промежутков и без произвольного порядка, а значит адрес любого элемента можно вычислить одной короткой формулой, а не найти перебором.

Слово "статический" здесь означает конкретную вещь: размер массива фиксируется в момент его создания и не меняется в течение всего времени его существования. Если тебе нужно больше места — придётся создать новый, больший массив и скопировать туда все старые элементы; сам исходный массив "растянуть на месте" нельзя, потому что сразу за его последним элементом в памяти может лежать уже что-то другое.

Определение

Статический массив (static array) — структура данных, хранящая последовательность элементов одного типа (и, соответственно, одного размера в байтах) в непрерывном (contiguous) блоке памяти фиксированного размера, заданного в момент создания массива. Адрес элемента с индексом $i$ вычисляется по формуле
$$\text{address}(A[i]) = \text{base\_address} + i \times \text{element\_size},$$
где $\text{base\_address}$ — адрес самого первого элемента массива (с индексом $0$), а $\text{element\_size}$ — размер одного элемента в байтах. Поскольку эта формула вычисляется за постоянное время независимо от значения $i$ и от общего размера массива $n$, доступ к элементу по индексу имеет сложность $O(1)$.

Обрати внимание: в этой формуле нет ни одного шага, зависящего от $n$ — ни цикла, ни перебора. Именно отсюда и берётся $O(1)$: компьютер не "ищет" элемент, а вычисляет его точный адрес арифметически, ровно за одно умножение и одно сложение, а затем выполняет одно обращение к памяти по этому адресу.

Примеры с разбором

Пример 1 (лёгкий). Массив 32-битных целых чисел (int32, то есть 4 байта на элемент) начинается по адресу $\text{base\_address} = 1000$. Найди адрес элемента с индексом $7$.

По формуле: $\text{address}(A[7]) = 1000 + 7 \times 4 = 1000 + 28 = 1028$. Обрати внимание: чтобы найти этот адрес, не потребовалось знать, сколько всего элементов в массиве, и не потребовалось "проходить" через элементы с индексами $0$–$6$ — только сам номер искомого элемента и размер одного элемента.

Пример 2 (средний). Реализуем статический массив на практике средствами Python и посмотрим, как выглядит доступ по индексу:

import numpy as np

# создаём массив фиксированного размера (5 элементов типа int32)
arr = np.zeros(5, dtype=np.int32)
arr[:] = [10, 20, 30, 40, 50]

print(arr[3])        # 40, доступ за O(1)
print(arr.itemsize)  # 4 — размер одного элемента в байтах
print(arr.nbytes)    # 20 — суммарный размер массива (5 * 4 байта)

Здесь numpy.ndarray ведёт себя ровно как статический массив в определении выше: при создании ему выделяется непрерывный блок памяти ровно под 5 элементов типа int32, и arr.itemsize (4 байта) — это в точности element_size из формулы адреса. Важная деталь, к которой мы ещё вернёмся: если ты попробуешь сделать np.append(arr, 60), NumPy не "дорастит" существующий массив — он создаст совершенно новый массив на 6 элементов и скопирует туда старые 5, потому что за концом исходного блока памяти гарантированно нет свободного места под шестой элемент. Это прямое следствие того, что массив статический.

Пример 3 (сложный). Почему статический массив в принципе нельзя "просто расширить на месте"? Представь блок памяти как участок в плотной жилой застройке: соседний дом мог быть построен на следующий день после твоего, и там уже кто-то живёт — расширить свой дом "вбок", не снося чужой, физически невозможно. Точно так же операционная система, выделяя память под массив на $n$ элементов, гарантирует тебе только эти $n \times \text{element\_size}$ байт — а память сразу за ними может в любой момент быть занята совершенно другими данными твоей же программы. Поэтому "увеличение" статического массива всегда реализуется одинаково: выделить новый блок памяти большего размера, скопировать туда все $n$ старых элементов (это уже $O(n)$ операция, а не $O(1)$), а затем освободить старый блок. Именно эта неизбежная стоимость копирования всего массива целиком — ключевая проблема, которую решает динамический массив, разобранный в следующем разделе.

Почему это важно. Непрерывность памяти — не второстепенная деталь реализации, а единственная причина, по которой массив вообще даёт $O(1)$-доступ. Как только ты переходишь к структуре данных, где элементы не лежат подряд физически (например, к связному списку, который будет темой одного из следующих уроков), формула адреса перестаёт работать в принципе — там для доступа к элементу номер $k$ действительно нужно пройти через $k$ предыдущих элементов, то есть сложность становится $O(n)$. Вся привычная скорость операций array[i] в любом языке программирования — это плата непрерывной памятью за возможность вычислять адрес формулой, а не искать перебором.

Динамический массив: как список в Python растёт сам

Интуиция: парковка с запасом мест

Представь, что ты арендуешь парковочные места для растущего автопарка компании. Арендовать ровно столько мест, сколько машин у тебя сегодня, — плохая идея: как только приедет ещё одна машина, придётся судорожно искать новую, более просторную парковку и перегонять туда весь автопарк целиком. Более разумная стратегия — сразу арендовать с запасом, скажем, вдвое больше мест, чем нужно прямо сейчас. Тогда каждая новая машина занимает свободное место мгновенно, и лишь когда запас окончательно заканчивается, приходится один раз (недёшево) переехать на бо́льшую площадку — снова с запасом.

Именно так работает динамический массив, и именно так реализован список list в Python. Внутри объекта list хранятся два разных числа: size (иногда говорят "length") — сколько элементов реально используется сейчас, и capacity — сколько места фактически выделено под данные. Пока $\text{size} < \text{capacity}$, добавление нового элемента в конец — это просто запись в уже выделенную, но пока пустующую ячейку, дешёвая операция $O(1)$. Лишь когда $\text{size}$ достигает $\text{capacity}$, происходит дорогая операция: выделяется новый, больший блок памяти, и все существующие элементы копируются в него.

Определение

Динамический массив (dynamic array) — структура данных, построенная поверх статического массива с запасом (over-allocation): в дополнение к фактически используемым элементам (size) выделяется дополнительное, временно неиспользуемое место (capacity $>$ size). Когда очередная вставка в конец не помещается в текущий выделенный блок ($\text{size} = \text{capacity}$), выполняется resize: выделяется новый блок памяти большего размера (как правило, в некоторое фиксированное число раз больше старого — коэффициент роста, growth factor), все существующие элементы копируются в него за $O(n)$, после чего вставка продолжается как обычно. Несмотря на то, что отдельная операция resize стоит $O(n)$, амортизированная сложность добавления элемента в конец динамического массива равна $O(1)$: суммарная стоимость всех resize-операций на протяжении $n$ последовательных вставок остаётся $O(n)$, то есть в среднем на одну вставку приходится лишь $O(1)$ работы.

Слово "амортизированная" здесь ключевое, и стоит проговорить его максимально честно: это не значит, что каждая конкретная вставка гарантированно выполняется за $O(1)$ — время от времени одна конкретная вставка окажется дорогой ($O(n)$), потому что именно на ней произойдёт resize. Амортизированная сложность — это утверждение о суммарной стоимости большой последовательности операций, делённой на их число, а не о худшем случае одной отдельно взятой операции.

Примеры с разбором

Пример 1 (лёгкий). Реализуем упрощённый динамический массив вручную, чтобы увидеть разницу между size и capacity явно:

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity

    def append(self, value):
        if self.size == self.capacity:
            self._resize(self.capacity * 2)  # удваиваем capacity
        self.data[self.size] = value
        self.size += 1

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity      # O(new_capacity) — новый блок
        for i in range(self.size):
            new_data[i] = self.data[i]         # O(size) — копируем все элементы
        self.data = new_data
        self.capacity = new_capacity

arr = DynamicArray()
for i in range(5):
    arr.append(i)
    print(f"после вставки {i}: size={arr.size}, capacity={arr.capacity}")

Вывод этой программы: после вставки $0$ — size=1, capacity=1; после вставки $1$ — size=2, capacity=2 (произошёл resize $1\to2$); после вставки $2$ — size=3, capacity=4 (resize $2\to4$); после вставки $3$ — size=4, capacity=4 (место ещё было, resize не потребовался); после вставки $4$ — size=5, capacity=8 (resize $4\to8$). Видно, что capacity скачет не при каждой вставке, а лишь тогда, когда запас закончился, и каждый раз удваивается.

Пример 2 (средний). Посчитаем амортизированную стоимость строго, методом агрегирования (aggregate method) — сложить всю работу за $n$ вставок и поделить на $n$. Пусть capacity растёт удвоением, начиная с $1$: $1, 2, 4, 8, \dots$ Тогда resize-операции происходят на вставках номер $1, 2, 4, 8, 16, \dots$ (в терминах количества уже вставленных элементов), и стоимость каждого resize равна количеству элементов, которые нужно скопировать: $1 + 2 + 4 + 8 + \dots + n/2$.

Это геометрическая прогрессия со знаменателем $2$, и её сумма ограничена:

$$1 + 2 + 4 + \dots + \frac{n}{2} < n.$$

(Сумма геометрической прогрессии $\sum_{k=0}^{\log_2 n - 1} 2^k = 2^{\log_2 n} - 1 = n - 1 < n$.) К этой сумме нужно прибавить ещё $n$ "обычных" дешёвых вставок (по $O(1)$ каждая, суммарно $O(n)$). Итого суммарная работа за $n$ вставок ограничена $O(n) + O(n) = O(n)$, а значит средняя стоимость одной вставки составляет $O(n)/n = O(1)$ — именно это и означает "амортизированная сложность $O(1)$".

Пример 3 (сложный). А что, если вместо удвоения увеличивать capacity каждый раз лишь на константу, скажем на $10$ элементов ($\text{capacity} \to \text{capacity} + 10$)? Такая стратегия называется линейным ростом, в противовес геометрическому (кратному) росту из примеров выше. Посчитаем суммарную стоимость $n$ вставок в этом случае: resize происходит на вставках номер $10, 20, 30, \dots$, то есть примерно $n/10$ раз, и стоимость каждого resize равна текущему размеру массива на тот момент: $10, 20, 30, \dots, n$. Сумма арифметической прогрессии:

$$10 + 20 + 30 + \dots + n \approx \frac{n}{10}\cdot\frac{n}{2} = \frac{n^2}{20} = O(n^2).$$

Суммарная стоимость получилась $O(n^2)$ вместо $O(n)$, а значит средняя (амортизированная) стоимость одной вставки — уже не $O(1)$, а $O(n)$! Этот пример наглядно показывает: именно геометрический (кратный, экспоненциальный) рост capacity — единственная причина, по которой динамический массив вообще даёт амортизированную $O(1)$ вставку. Линейный рост выглядит "экономнее" по памяти на первый взгляд, но катастрофически проигрывает по времени на больших $n$. Именно поэтому все промышленные реализации — CPython list, C++ std::vector, Java ArrayList — используют геометрический рост, хотя и с разными конкретными коэффициентами: std::vector в большинстве реализаций удваивается (иногда коэффициент $1{,}5$), Java ArrayList растёт в $1{,}5$ раза, а сам CPython для встроенного list использует более консервативную формулу роста, дающую коэффициент примерно $1{,}125$ (то есть капасити увеличивается примерно на $12{,}5\%$, а не на все $100\%$) — компромисс между экономией памяти и частотой перевыделений, подобранный эмпирически для типичных программ на Python.

Почему это важно. Понимание амортизированного анализа снимает кажущееся противоречие: как список, у которого "иногда" происходит дорогая $O(n)$-операция копирования, вообще может считаться структурой с $O(1)$-добавлением? Ответ — потому что дорогие операции происходят экспоненциально редко по сравнению с дешёвыми, и в сумме их стоимость не превышает стоимости самих дешёвых операций. Это ровно та же логика, которую ты уже видел в задании 11 предыдущего урока про Big O, но здесь она разобрана до конца и с явной демонстрацией, что произойдёт, если выбрать неправильную (линейную) стратегию роста.

Операции над массивом: доступ, вставка, удаление — и их сложность по позициям

Интуиция: не все позиции равны

Возьмём снова аналогию с рядом шкафчиков, но теперь представим, что тебе нужно не просто открыть существующий шкафчик, а добавить новый в середину ряда — так, чтобы нумерация осталась последовательной. Раз шкафчики стоят вплотную друг к другу без промежутков, единственный способ освободить место посередине — физически сдвинуть все шкафчики, начиная с этой позиции и до самого конца ряда, на одну позицию дальше. Чем ближе к началу ряда нужно вставить новый шкафчик, тем больше шкафчиков придётся сдвинуть. Ровно та же механика управляет сложностью вставки и удаления в массиве: то, что находится физически "после" точки изменения, обязано сдвинуться, чтобы сохранить непрерывность памяти.

Определение

Сложность основных операций над массивом (динамическим, размера $n$) зависит от позиции, в которой происходит операция:

Операция Сложность Почему

Доступ по индексу A[i] $O(1)$ адрес вычисляется формулой, без обхода

Вставка/удаление в конец $O(1)$ амортизированно место уже зарезервировано (capacity), сдвигать нечего

Вставка/удаление в начало $O(n)$ все $n$ существующих элементов сдвигаются на одну позицию

Вставка/удаление в середину $O(n)$ в среднем сдвигается половина элементов, то есть $O(n/2) = O(n)$

Поиск элемента по значению (неотсортированный массив) $O(n)$ нет иного способа, кроме проверки каждого элемента по очереди

Операция	Сложность	Почему
Доступ по индексу `A[i]`	$O(1)$	адрес вычисляется формулой, без обхода
Вставка/удаление в конец	$O(1)$ амортизированно	место уже зарезервировано (capacity), сдвигать нечего
Вставка/удаление в начало	$O(n)$	все $n$ существующих элементов сдвигаются на одну позицию
Вставка/удаление в середину	$O(n)$	в среднем сдвигается половина элементов, то есть $O(n/2) = O(n)$
Поиск элемента по значению (неотсортированный массив)	$O(n)$	нет иного способа, кроме проверки каждого элемента по очереди

Ключевая идея этой таблицы: у операций доступа по индексу и добавления в конец сложность не зависит от размера массива, а у операций, требующих сдвига элементов (вставка/удаление где угодно, кроме самого конца), сложность линейно растёт вместе с размером массива.

Примеры с разбором

Пример 1 (лёгкий). Массив prices = [100, 250, 75, 300, 120] хранит цены товаров в интернет-магазине. Найди сложность операций prices[2] (получить третью цену) и prices.append(400) (добавить цену нового товара в конец).

Обе операции — $O(1)$: prices[2] вычисляет адрес третьего элемента формулой (доступ по индексу) и ничего не сдвигает; prices.append(400) в подавляющем большинстве случаев просто записывает значение в уже зарезервированную ячейку после последнего элемента (амортизированная $O(1)$, если только не наступает именно этот резкий момент resize).

Пример 2 (средний). А что если новый товар нужно добавить не в конец, а на первое место в списке (например, потому что он сейчас в самой активной акции и должен показываться первым)? Смотрим на код и считаем стоимость:

prices = [100, 250, 75, 300, 120]
prices.insert(0, 50)   # вставляем 50 в начало
print(prices)          # [50, 100, 250, 75, 300, 120]

Чтобы освободить позицию с индексом $0$ под новое значение $50$, Python обязан физически сдвинуть все существующие 5 элементов на одну позицию вправо (в CPython это делается эффективной операцией memmove над массивом указателей, но её стоимость всё равно линейно зависит от числа сдвигаемых элементов) — то есть insert(0, x) в списке длины $n$ имеет сложность $O(n)$. Если такую вставку в начало сделать $n$ раз подряд (например, в цикле, добавляя элементы "задом наперёд"), суммарная стоимость составит $O(n) + O(n-1) + \dots + O(1) = O(n^2)$ — квадратичный алгоритм там, где на первый взгляд кажется, что происходит просто $n$ "быстрых" вставок.

Пример 3 (сложный). Сравним на практике реальную скорость вставки в начало списка list против аналогичной операции у структуры collections.deque, специально спроектированной для эффективной работы с обоими концами:

import time
from collections import deque

n = 50_000

# вставка в начало обычного списка — O(n) на каждую вставку
start = time.perf_counter()
lst = []
for i in range(n):
    lst.insert(0, i)
print("list.insert(0, ...):", time.perf_counter() - start, "сек")

# вставка в начало deque — O(1) на каждую вставку
start = time.perf_counter()
dq = deque()
for i in range(n):
    dq.appendleft(i)
print("deque.appendleft(...):", time.perf_counter() - start, "сек")

На типичном ноутбуке версия с list.insert(0, ...) для $n=50\,000$ занимает несколько секунд (квадратичный рост стоимости), тогда как версия с deque.appendleft(...) отрабатывает практически мгновенно — доли секунды, потому что deque внутри устроен иначе (как двусторонняя цепочка блоков, а не единый непрерывный массив) и специально спроектирован так, чтобы добавление с обоих концов стоило $O(1)$, а не $O(n)$. Разбор устройства deque и других структур с эффективными операциями на обоих концах — тема следующего урока про стеки и очереди; здесь важно унести практический вывод: массив — не универсально лучшая структура данных на все случаи, а структура, эффективная ровно для тех операций, для которых её физическая непрерывность работает в твою пользу.

Почему это важно. Выбор структуры данных под конкретный паттерн использования — одно из самых практических умений в разработке, и цена ошибки здесь измеряется не абстрактными баллами, а реальными секундами (или часами) выполнения пайплайна обработки данных. Код, который выглядит невинно ("просто добавляю элементы в список в цикле"), может незаметно превратиться в $O(n^2)$-алгоритм, если добавление идёт не в тот конец. В контексте ML это особенно актуально при построении обучающих выборок и очередей заданий (data loader'ов): если внутри пайплайна данные накапливаются вставкой в начало списка, а не в конец, обработка миллиона примеров может занять на порядки больше времени, чем должна.

Многомерные массивы: строки, столбцы и порядок в памяти

Интуиция: таблица, вытянутая в одну ленту

Матрица или таблица выглядит на бумаге как двумерная сетка строк и столбцов, но физическая память компьютера — всегда одномерная лента адресов, без понятия "строка" и "столбец" на аппаратном уровне. Значит, чтобы хранить двумерный массив, его данные нужно "развернуть" в одну линию — и от того, в каком порядке это делается, зависит и формула адреса, и (что окажется критически важным дальше) реальная скорость доступа к элементам.

Определение

Наиболее распространённый способ хранения двумерного массива размера $(\text{num\_rows}, \text{num\_cols})$ — row-major order ("построчный порядок", C-order): в памяти подряд сначала идут все элементы первой строки, затем все элементы второй строки, и так далее. Адрес элемента $A[i][j]$ вычисляется по формуле
$$\text{address}(A[i][j]) = \text{base\_address} + (i \times \text{num\_cols} + j) \times \text{element\_size}.$$
Альтернативный порядок — column-major order ("постолбцовый порядок", Fortran-order), при котором в памяти подряд идут элементы по столбцам, а не по строкам; NumPy поддерживает оба варианта через параметр order='C' (по умолчанию) и order='F'.

Формула для row-major order — прямое обобщение формулы адреса одномерного массива: индекс $i \times \text{num\_cols} + j$ — это просто "порядковый номер" элемента $A[i][j]$, если считать, будто вся матрица уже вытянута в одну строку.

Примеры с разбором

Пример 1 (лёгкий). Дана матрица $4 \times 3$ (4 строки, 3 столбца) типа int32 (4 байта), хранящаяся в row-major order с base_address = 2000. Найди адрес элемента $A[2][1]$.

$$\text{address}(A[2][1]) = 2000 + (2 \times 3 + 1) \times 4 = 2000 + 7 \times 4 = 2000 + 28 = 2028.$$

Проверим логику вручную: элементы идут в порядке $A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2], A[2][0], A[2][1], \dots$ — элемент $A[2][1]$ действительно восьмой по счёту (с учётом нулевой индексации — под номером $7$), что и даёт смещение $7 \times 4 = 28$ байт от начала.

Пример 2 (средний). Сравним, как хранится "матрица" при наивной реализации как списка списков в Python против NumPy-массива:

import numpy as np

# список списков — НЕ непрерывный блок памяти!
matrix_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# NumPy 2D массив — единый непрерывный блок памяти
matrix_np = np.array(matrix_list, dtype=np.int32)
print(matrix_np.strides)  # (12, 4) — шаг между строками и между столбцами в байтах

matrix_list — это список из трёх отдельных списков-объектов, каждый из которых хранится в своём собственном, отдельно выделенном блоке памяти где-то в куче; сам внешний список хранит лишь три указателя на эти блоки, а никакой единой "матрицы" в памяти физически не существует. matrix_np, напротив, — это один сплошной блок из 9 чисел int32 (36 байт), и вывод matrix_np.strides == (12, 4) буквально означает: "чтобы перейти к следующей строке, сдвинься на 12 байт (три числа по 4 байта — целая строка), а чтобы перейти к следующему столбцу — на 4 байта (один элемент)". Это и есть формула адреса из определения, выраженная на языке NumPy: strides — это в точности коэффициенты $(\text{num\_cols} \times \text{element\_size},\ \text{element\_size})$ из формулы row-major адреса.

Пример 3 (сложный). Одно из самых красивых практических следствий понятия strides — то, что операция транспонирования матрицы в NumPy (A.T) не копирует ни единого байта данных:

import numpy as np

A = np.arange(12).reshape(3, 4)   # матрица 3x4
print(A.strides)                  # (16, 4) — шаг по строкам, шаг по столбцам

B = A.T                           # транспонированная матрица 4x3
print(B.strides)                  # (4, 16) — шаги просто поменялись местами!
print(B.base is A)                # True — B смотрит на ту же самую память, что A

A.T не создаёт новый блок памяти на 12 элементов и не переставляет их физически — вместо этого NumPy создаёт лёгкий объект-"представление" (view), у которого просто переставлены местами шаги strides и переставлена местами форма shape ($3{\times}4$ становится $4{\times}3$). Когда ты потом читаешь B[i][j], NumPy вычисляет тот же самый физический адрес, что и раньше, просто применяя другую комбинацию шагов — то есть транспонирование, интуитивно кажущееся операцией $O(n)$ или даже $O(n^2)$ (переставить все элементы), на самом деле выполняется за $O(1)$, потому что не трогает данные вовсе, а лишь переинтерпретирует, как их читать. Это прямое и практичное следствие того, что многомерный массив — всего лишь одномерная лента памяти плюс формула, описывающая, как по ней "гулять".

Почему это важно. Изображение в машинном обучении — это, как правило, трёхмерный массив (высота, ширина, число каналов), а батч изображений для обучения сети — уже четырёхмерный массив (размер батча, высота, ширина, каналы) либо (размер батча, каналы, высота, ширина), в зависимости от соглашения конкретного фреймворка. Понимание того, что "многомерность" — это лишь удобная абстракция поверх одной непрерывной ленты памяти и формулы адреса, объясняет сразу несколько вещей: почему операции вроде транспонирования или reshape в NumPy и PyTorch бывают почти мгновенными (если не требуют физической перестановки байтов), а иногда неожиданно требуют копирования (если запрошенная форма несовместима с текущими strides без физической перестановки данных) — и почему в документации то и дело встречается предупреждение "returns a view, not a copy".

NumPy-массивы и векторизация: фундамент тензоров в машинном обучении

Интуиция: зачем вообще нужен NumPy, если уже есть список

Список Python — гибкая и удобная структура: в него можно положить числа, строки, вложенные списки и объекты произвольных классов вперемешку, размер меняется на лету. Но за эту гибкость приходится платить: список хранит не сами значения подряд в памяти, а лишь указатели на объекты, которые могут быть разбросаны по куче как угодно, и каждое число внутри Python — это не просто 4 или 8 "голых" байт, а полноценный объект со своим заголовком, счётчиком ссылок и служебной информацией (обычно 28 байт и больше даже для маленького целого числа). Когда тебе нужно сложить миллион чисел из списка, интерпретатор на каждой итерации цикла заново распознаёт тип объекта, разыменовывает указатель, выполняет операцию сложения через универсальный, "общий на все типы" механизм — и так миллион раз подряд. NumPy устраняет все эти накладные расходы разом, жертвуя гибкостью ради скорости: массив numpy.ndarray хранит только "голые" числа одного заранее выбранного типа (dtype) в одном непрерывном блоке памяти — ровно как статический массив, разобранный в начале этого урока, — а операции над ним выполняются не построчным Python-циклом, а одним вызовом заранее скомпилированного C-кода, который проходит по этой ленте памяти напрямую.

Определение

NumPy-массив (numpy.ndarray) — типизированный (все элементы одного dtype, то есть одного размера в байтах), непрерывный в памяти многомерный массив с фиксированной формой (shape), заданной при создании. Векторизация — техника выполнения операции сразу над всем массивом (или его срезом) одним вызовом низкоуровневой функции, реализованной на C или Fortran, вместо явного цикла на уровне интерпретатора Python. Векторизованная операция быстрее эквивалентного цикла по трём независимым причинам: (1) отсутствие накладных расходов интерпретатора байткода на каждой итерации, (2) более эффективное использование кэша процессора благодаря непрерывности памяти (cache locality), (3) использование векторных инструкций процессора (SIMD), способных выполнять одну арифметическую операцию сразу над несколькими числами за такт.

Примеры с разбором

Пример 1 (лёгкий). Сравним скорость суммирования миллиона чисел циклом Python против векторизованной операции NumPy:

import numpy as np
import time

n = 1_000_000
data_list = list(range(n))
data_np = np.arange(n)

start = time.perf_counter()
total = 0
for x in data_list:
    total += x
print("цикл Python:", time.perf_counter() - start, "сек")

start = time.perf_counter()
total_np = np.sum(data_np)
print("np.sum:", time.perf_counter() - start, "сек")

На типичном железе цикл Python суммирует миллион чисел за десятки миллисекунд, а np.sum — за доли миллисекунды: разница обычно в 30–100 раз в пользу NumPy, и не потому что "NumPy написан лучше", а потому что цикл Python на каждой из миллиона итераций заново выполняет разыменование объекта, диспетчеризацию типа и байткод-инструкции интерпретатора, тогда как np.sum — это один вызов плотного C-цикла, проходящего по уже готовой, непрерывной ленте чисел.

Пример 2 (средний). Векторизация особенно ярко видна в задаче, которую делает почти каждый ML-пайплайн перед обучением модели — стандартизация признаков (приведение к нулевому среднему и единичной дисперсии):

import numpy as np

# матрица признаков: 5 объектов, 3 признака
X = np.array([
    [170, 65, 25],
    [180, 80, 30],
    [160, 55, 22],
    [175, 70, 28],
    [165, 60, 24],
], dtype=np.float64)

mean = X.mean(axis=0)   # среднее по каждому столбцу (признаку)
std = X.std(axis=0)     # стандартное отклонение по каждому столбцу
X_scaled = (X - mean) / std
print(X_scaled)

Ни одного явного цикла for по объектам или признакам в этом коде нет — X - mean вычитает вектор mean из каждой строки матрицы X разом (эта операция называется broadcasting, "распространение": NumPy автоматически "растягивает" вектор из трёх чисел, применяя его к каждой из пяти строк). За кулисами всё равно выполняется столько же арифметических операций, сколько выполнил бы эквивалентный двойной цикл по строкам и столбцам — но выполняются они не интерпретатором Python инструкция за инструкцией, а скомпилированным C-кодом, который пробегает по непрерывному блоку памяти напрямую, используя ту самую формулу адреса base_address + i * element_size из начала урока.

Пример 3 (сложный). Ровно та же самая идея — типизированный, непрерывный многомерный массив фиксированной формы — лежит в основе тензоров глубокого обучения. Один батч цветных изображений $32{\times}32$ пикселя, собранный для обучения свёрточной сети, — это четырёхмерный тензор:

import numpy as np

batch_size, channels, height, width = 64, 3, 32, 32
batch = np.random.rand(batch_size, channels, height, width).astype(np.float32)

print(batch.shape)     # (64, 3, 32, 32)
print(batch.strides)   # шаги по каждой из четырёх осей в байтах
print(batch.nbytes)    # 64*3*32*32*4 = 786 432 байта — один сплошной блок памяти

batch.shape == (64, 3, 32, 32) читается так: 64 изображения в батче, у каждого 3 канала (красный, зелёный, синий), у каждого канала — сетка $32{\times}32$ пикселя. Формально это ничем не отличается от двумерной матрицы из предыдущего раздела — просто формула адреса теперь использует не два, а четыре слагаемых-шага (strides), по одному на каждую ось. Именно так представлены данные внутри torch.Tensor в PyTorch или tf.Tensor в TensorFlow: тензор — это, по сути, ndarray с двумя дополнительными возможностями (перенос вычислений на GPU и автоматическое дифференцирование для обучения через обратное распространение ошибки), но фундамент — тот же самый непрерывный типизированный блок памяти фиксированной формы, который ты только что разобрал вручную по формуле адреса. Веса свёрточного слоя такой сети — тоже тензор фиксированной формы, например (out_channels, in_channels, kernel_height, kernel_width), а веса полносвязного слоя — просто двумерная матрица (in_features, out_features).

Почему это важно. Разница между "написать цикл на Python" и "написать одну строчку с NumPy" — это на практике разница между моделью, которая обучается часами, и моделью, которая обучается минутами, при абсолютно идентичной математике. А понимание того, что тензор PyTorch — это концептуально тот же самый статический типизированный массив, только с добавленными возможностями GPU и автоградиента, снимает значительную часть ощущения "магии" вокруг глубокого обучения: shape, dtype, stride, broadcasting — это ровно те же понятия, что ты только что разобрал на примере обычных массивов, просто применённые к структурам с намного бо́льшим числом измерений.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Статический массив типа int64 (8 байт на элемент) начинается по адресу $5000$. Найди адрес элемента с индексом $12$.

Задание 2. Массив типа float32 (4 байта на элемент) занимает адреса с $2000$ по $2039$ включительно. Сколько элементов в массиве?

Задание 3. Определи сложность каждой из операций: (а) arr[5], (б) arr.append(x) (в конец), (в) arr.insert(0, x) (в начало).

Задание 4. Динамический массив стартует с capacity=2 и растёт удвоением. После скольких вставок capacity впервые станет равна $32$?

Задание 5. Почему статический массив нельзя "расширить на месте", просто дописав элементы сразу за последним?

Задание 6. Список products = ["хлеб", "молоко", "сыр"]. Какая сложность у операции products.pop() (удалить последний элемент) и у products.pop(0) (удалить первый элемент)?

Задание 7. Матрица $5{\times}4$ (5 строк, 4 столбца) типа int32, хранится в row-major order с base_address = 1000. Найди адрес элемента $A[3][2]$.

Задание 8. Чем принципиально отличается список списков ([[1,2],[3,4]]) от numpy.array([[1,2],[3,4]]) с точки зрения расположения в памяти?

Задание 9. Почему np.append(arr, x) внутри цикла на $n$ итераций — плохая практика с точки зрения сложности?

Задание 10. Тензор изображения имеет форму (3, 32, 32) — 3 канала, 32 на 32 пикселя. Сколько всего чисел он хранит и сколько байт займёт при типе float32?

Средние (задания 11–20)

Задание 11. Динамический массив растёт удвоением, начиная с capacity=1. Выполнено $100$ последовательных вставок. Оцени суммарную стоимость всех resize-операций (в количестве скопированных элементов) и покажи, что она меньше $100$.

Задание 12. Реализация DynamicArray из урока использует _resize(self.capacity * 2). Перепиши логику так, чтобы рост был не удвоением, а увеличением на фиксированную константу +4, и объясни, как это повлияет на амортизированную сложность append.

Задание 13. Список из $n=10\,000$ элементов. Оцени, во сколько раз (по порядку величины) операция lst.insert(0, x), выполненная $n$ раз подряд в цикле, медленнее, чем lst.append(x), выполненная $n$ раз подряд.

Задание 14. Матрица $6{\times}6$ типа float64 (8 байт) хранится в row-major order, base_address=0. Найди адрес элемента $A[5][5]$ (последний элемент).

Задание 15. NumPy-массив A формы (4, 5) типа int32 имеет strides = (20, 4). Объясни, что означает каждое из этих двух чисел, и подтверди их вычислением из формы и размера типа.

Задание 16. Объясни, почему транспонирование NumPy-матрицы (A.T) выполняется за $O(1)$, тогда как транспонирование "вручную" (создание нового списка списков с переставленными индексами в Python) требует $O(n \cdot m)$ операций для матрицы $n{\times}m$.

Задание 17. Матрица признаков X формы (1000, 20) (1000 объектов, 20 признаков). Напиши одну строку на NumPy, которая вычисляет стандартизированную матрицу (X - X.mean(axis=0)) / X.std(axis=0) и объясни, сколько явных циклов Python в ней используется.

Задание 18. Батч изображений имеет форму (batch_size, channels, height, width) = (32, 3, 64, 64). Сколько всего чисел содержит этот тензор, и как изменится это число, если увеличить batch_size вдвое?

Задание 19. Почему цикл for x in python_list: total += x работает заметно медленнее, чем np.sum(numpy_array), даже если оба массива содержат одинаковые числа и одинаковый размер $n$? Перечисли минимум две независимые причины.

Задание 20. Объясни своими словами, почему тензор PyTorch (torch.Tensor) можно считать "обобщением" NumPy-массива, а не принципиально другой структурой данных.

Продвинутые (задания 21–30)

Задание 21. Докажи формально, что суммарная стоимость всех resize-операций динамического массива с ростом-удвоением на $n$ вставок ограничена $2n$ (а не только асимптотически $O(n)$).

Задание 22. При каком коэффициенте роста $r > 1$ (capacity \to capacity \times r) суммарная стоимость resize-операций на $n$ вставок всё ещё остаётся $O(n)$? Обоснуй на уровне геометрической прогрессии.

Задание 23. Тензор в PyTorch имеет форму (N, C, H, W). Как изменится формула вычисления адреса (в терминах strides) при переходе от NCHW к формату NHWC ((N, H, W, C)) при том же количестве данных?

Задание 24. Массив A формы (1000,) типа float64. Операция A[::2] (взять каждый второй элемент) в NumPy возвращает view (представление), а не копию. Объясни через понятие strides, как это возможно.

Задание 25. Почему список Python (list) не подходит для хранения миллиона чисел, если единственная цель — быстрые математические операции над ними (сложение, умножение, статистика), хотя формально list тоже поддерживает индексацию за $O(1)$?

Задание 26. Реализуй (псевдокодом или Python) операцию удаления элемента по индексу i из статического массива размера n (без сохранения порядка не разрешается — порядок элементов должен сохраниться) и укажи её сложность.

Задание 27. Датасет из $n$ строк построчно читается из файла и накапливается в структуре данных перед конвертацией в NumPy-массив. Сравни две стратегии: (а) python_list.append(row) на каждой строке, затем np.array(python_list) один раз в конце; (б) np.append(numpy_array, row) на каждой строке. Оцени асимптотическую сложность каждой стратегии.

Задание 28. Квадратная матрица $n \times n$ хранится в row-major order. Напиши формулу адреса для элемента на главной диагонали $A[k][k]$ и объясни, почему все диагональные элементы отстоят друг от друга на одинаковое расстояние в памяти.

Задание 29. Почему операция numpy_array.reshape(...) иногда возвращает view (без копирования, $O(1)$), а иногда вынуждена сделать полную копию данных ($O(n)$)? Приведи условие.

Задание 30. Обучающий пайплайн должен на каждой итерации добавлять новый пример в конец обучающей выборки размера, растущего до миллионов элементов, а также иногда удалять устаревшие примеры из начала (стратегия "скользящего окна" данных). Какую структуру — list, numpy.ndarray с ручным управлением capacity, или collections.deque — ты бы выбрал, и почему, с точки зрения сложности операций на обоих концах?

Частые ошибки

❌ Ошибка: «Список Python — это то же самое, что массив в C, только удобнее» ✅ Правильно: Список Python — это динамический массив указателей на объекты, а не массив самих чисел; каждое число — отдельный объект со своими накладными расходами 💡 Почему: Именно поэтому list заметно медленнее и "тяжелее" по памяти, чем NumPy-массив того же логического содержимого — элементы list физически не лежат подряд, подряд лежат только указатели на них.

❌ Ошибка: «append() в конец списка — всегда операция $O(1)$, без исключений» ✅ Правильно: append() — амортизированно $O(1)$: подавляющее большинство вызовов дешёвые, но время от времени случается дорогой resize стоимостью $O(n)$ 💡 Почему: Путаница между "почти всегда быстро" и "гарантированно быстро в каждом отдельном случае" может привести к неверным ожиданиям в системах, чувствительных к задержке одной конкретной операции (real-time системы), где важен не средний, а худший случай.

❌ Ошибка: «Раз вставка в конец списка быстрая, то и вставка в начало должна быть такой же быстрой» ✅ Правильно: Вставка в начало требует сдвинуть все существующие элементы — это $O(n)$, принципиально отличная сложность от вставки в конец 💡 Почему: Позиция вставки критически важна именно из-за непрерывности памяти: элементы, стоящие в памяти "после" точки вставки, физически обязаны сдвинуться, чтобы освободить место, а элементы "до" точки вставки трогать не нужно.

❌ Ошибка: «NumPy-массив можно расширять так же дёшево, как список Python, просто используя np.append» ✅ Правильно: У numpy.ndarray нет резервного capacity — np.append каждый раз создаёт новый массив и копирует все данные заново, что при многократном вызове в цикле даёт $O(n^2)$ 💡 Почему: NumPy проектировался для быстрых операций над уже собранным массивом фиксированного размера, а не для частого построчного роста; для накопления данных лучше сначала собрать их в обычном списке, а в NumPy-массив конвертировать один раз в конце.

❌ Ошибка: «Многомерный массив физически хранится как настоящая многомерная сетка ячеек в памяти» ✅ Правильно: Физическая память — всегда одномерная лента; "многомерность" — это исключительно формула адреса (row-major order и strides), а не физическое расположение 💡 Почему: Понимание этого объясняет, почему такие операции, как транспонирование или некоторые виды reshape, могут выполняться мгновенно ($O(1)$) — они лишь меняют формулу интерпретации той же самой одномерной ленты данных, а не физически переставляют числа.

❌ Ошибка: «Векторизация в NumPy ускоряет код просто потому, что библиотека "оптимизированнее написана"» ✅ Правильно: Ускорение — результат трёх конкретных, объяснимых факторов: отсутствия интерпретатора байткода на каждой итерации, эффективного использования кэша процессора благодаря непрерывности памяти, и векторных SIMD-инструкций 💡 Почему: Понимание конкретных причин, а не общей фразы "NumPy быстрее", позволяет заранее предсказывать, когда векторизация даст максимальный выигрыш (плотные числовые операции над большими массивами), а когда её эффект будет скромным (мелкие массивы, операции с сильной ветвящейся логикой на каждый элемент).

Главное запомнить

✅ Статический массив хранит элементы одного типа в непрерывном блоке памяти фиксированного размера; адрес элемента $A[i] = \text{base\_address} + i \times \text{element\_size}$ вычисляется за $O(1)$, без обхода

✅ Динамический массив (список Python) — статический массив с запасом (over-allocation): пока $\text{size} < \text{capacity}$, добавление в конец дёшево; когда запас заканчивается, происходит resize — выделение нового блока и копирование всех элементов, $O(n)$

✅ Амортизированная сложность добавления в конец динамического массива — $O(1)$: суммарная стоимость всех resize-операций на $n$ вставок ограничена $O(n)$ благодаря геометрическому (кратному) росту capacity, а не линейному

✅ Сложность операций над массивом сильно зависит от позиции: доступ по индексу и вставка/удаление в конец — $O(1)$; вставка/удаление в начало или середину — $O(n)$, потому что требует сдвига остальных элементов

✅ Многомерный массив физически хранится как одна непрерывная лента памяти; "многомерность" реализуется формулой адреса — row-major order и вектор strides, задающий шаг по каждой оси

✅ Транспонирование и некоторые виды reshape в NumPy выполняются за $O(1)$, потому что меняют только strides и shape (метаданные), не трогая сами данные — это называется view, в отличие от copy

✅ NumPy-массив (ndarray) — типизированный непрерывный статический массив: фиксированный dtype, фиксированная shape, никакого запаса capacity, в отличие от list

✅ Векторизация ускоряет вычисления по трём причинам: нет накладных расходов интерпретатора на каждой итерации, лучше используется кэш процессора благодаря непрерывности памяти, задействуются SIMD-инструкции процессора

✅ Тензоры PyTorch и TensorFlow — прямое обобщение NumPy-массива: тот же непрерывный типизированный массив фиксированной формы, плюс поддержка GPU и автоматического дифференцирования

✅ np.append в цикле и list.insert(0, x) в цикле — классические источники неожиданной $O(n^2)$-сложности там, где ожидалась линейная; для операций на обоих концах структуры используй collections.deque

Связь с другими темами курса

🔙 Откуда пришли: Из урока 251 — понятие сложности алгоритмов (Big O), необходимое, чтобы формально говорить о разнице между $O(1)$, $O(n)$ и амортизированным $O(1)$, разобранными в этом уроке

🔜 Куда идём:

Стеки и очереди (урок 253) — структуры данных, ограничивающие доступ к массиву определённой дисциплиной (LIFO/FIFO), и collections.deque, уже упомянутый здесь как решение для эффективных операций на обоих концах
Связные списки (урок 254) — альтернатива массиву, жертвующая $O(1)$-доступом по индексу ради $O(1)$-вставки в любое место без сдвига элементов; прямое сопоставление с этим уроком покажет, что не существует структуры данных, одинаково хорошей во всём
Хеш-таблицы (урок 255) — структура, построенная поверх массива с использованием хеш-функции для вычисления позиции, что даёт амортизированный $O(1)$-доступ по произвольному ключу, а не только по числовому индексу

🎯 В машинном обучении: NumPy-массив — буквальный фундамент любого числового вычисления в Python-экосистеме данных: pandas.DataFrame хранит столбцы как NumPy-массивы, scikit-learn принимает данные в виде NumPy-массивов, а тензоры PyTorch и TensorFlow — прямое расширение той же самой идеи на GPU с автоматическим дифференцированием. Понимание непрерывности памяти и амортизированной сложности напрямую объясняет, почему векторизованный код на порядки быстрее циклов Python, и почему конкретные операции построения датасета (например, построчное добавление примеров) стоит проектировать с оглядкой на то, какую структуру данных использовать на каждом этапе.

Интересные факты

📌 CPython (стандартная реализация Python) использует для роста списка коэффициент, отличный от классического "удвоения" из учебников: примерно $1{,}125$ (то есть рост на $\approx 12{,}5\%$), а не в 2 раза. Это сознательный компромисс между частотой перевыделений памяти и экономией самой памяти — при удвоении на больших списках можно было бы впустую держать зарезервированным до половины выделенной памяти.

📌 Операция A.T (транспонирование) в NumPy настолько дёшева ($O(1)$, без копирования данных), что её можно безопасно вызывать много раз подряд в цикле без потери производительности — а вот последующее преобразование транспонированного массива в C-непрерывный вид через np.ascontiguousarray(A.T), наоборот, требует полноценного копирования, потому что переставленные strides больше не соответствуют "естественному" построчному порядку.

📌 Термин "тензор" в машинном обучении исторически пришёл из физики и дифференциальной геометрии XIX–XX веков (тензоры напряжений, тензор кривизны в общей теории относительности Эйнштейна), где он означал куда более строгий математический объект с определёнными правилами преобразования при смене системы координат. В глубоком обучении слово используется гораздо вольнее — практически как синоним "многомерного массива фиксированной формы", без сохранения исходной геометрической строгости термина.

📌 Одна из причин, почему обучение нейросетей так сильно ускорилось с переходом на GPU, — то, что графические процессоры изначально проектировались для массово-параллельной обработки пикселей изображения (по сути, больших многомерных массивов чисел) в видеоиграх, и лишь позже сообщество машинного обучения обнаружило, что та же самая архитектура идеально подходит для матричных операций над тензорами весов нейросети — ещё один этап истории, в котором массивы данных и специализированное железо для их параллельной обработки развивались рука об руку.

Лайфхаки и полезные трюки

💡 Если нужно накапливать данные построчно (в цикле, при чтении файла, в процессе пайплайна), копи их в обычном списке Python и превращай в NumPy-массив (np.array(the_list)) один раз в самом конце — а не вызывай np.append на каждой итерации: разница в сложности между $O(n)$ и $O(n^2)$ на больших датасетах ощущается как секунды против часов.

💡 Если структуре данных нужны эффективные операции на обоих концах (например, скользящее окно данных, буфер последних $N$ событий), используй collections.deque вместо обычного списка — операции appendleft/popleft у него $O(1)$, тогда как у list аналогичные операции на левом конце — $O(n)$.

💡 Перед тем как писать явный цикл for по элементам NumPy-массива, задай себе вопрос "а можно ли это выразить как операцию над массивом целиком?" — сложение, вычитание, сравнение, агрегации (sum, mean, max) и broadcasting покрывают подавляющее большинство задач без единого явного Python-цикла, и почти всегда дают ускорение на порядок и больше.

💡 Если после reshape, transpose или сложного среза NumPy-массив начинает работать неожиданно медленно в последующих вычислениях, проверь array.flags['C_CONTIGUOUS'] — если False, массив уже не является плотным непрерывным блоком в стандартном порядке, и явное приведение через np.ascontiguousarray(array) перед тяжёлыми вычислениями может заметно ускорить дальнейшую работу.

💡 При проектировании собственной структуры данных, где заранее известен примерный конечный размер (например, известно число строк в файле до его чтения), полезно сразу выделить массив нужного размера (np.empty(n) или [None] * n для списка) и заполнять его по индексу, а не расти добавлением по одному элементу — это полностью убирает даже амортизированные издержки resize.

💡 Разница между list и numpy.ndarray — не "какой из них лучше", а "для какой задачи какой предназначен": list — гибкая структура для разнородных данных и частых структурных изменений (вставки, удаления в произвольных местах), numpy.ndarray — специализированный инструмент для быстрых массовых числовых вычислений над однотипными данными фиксированного размера. Хороший ML-код обычно использует оба — list на этапе сбора и предобработки "сырых" данных, numpy.ndarray/тензоры на этапе собственно вычислений.

Массив — самая простая по формулировке и при этом самая фундаментальная структура данных во всём программировании: один непрерывный блок памяти и одна арифметическая формула для вычисления адреса. Но именно эта простота делает её универсальным строительным блоком — от list в первой строчке кода, которую пишет любой начинающий программист, до многомерных тензоров, на которых обучаются модели с миллиардами параметров. Разобравшись, почему доступ по индексу — это $O(1)$, почему добавление в конец списка — амортизированный $O(1)$, а вставка в начало — честный $O(n)$, ты получаешь не абстрактное знание, а рабочий инструмент: способность заранее, до запуска кода, понимать, где твой пайплайн обработки данных будет быстрым, а где неожиданно "упрётся" в квадратичную сложность. Это понимание не устареет и не потеряет значения — оно лежит в основании абсолютно всего, что ты будешь делать дальше с NumPy, pandas, PyTorch и любой другой библиотекой, работающей с данными.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →