260 lines
13 KiB
Markdown
260 lines
13 KiB
Markdown
# Сложность и организация вычислений
|
||
|
||
## Зачем оценивать сложность
|
||
|
||
Корректный алгоритм может быть практически бесполезен, если время или память
|
||
растут слишком быстро. Анализ сложности отвечает не на вопрос «сколько секунд»,
|
||
а на вопрос «как изменится потребление ресурсов при росте входа».
|
||
|
||
Для данных будем использовать:
|
||
|
||
- \(n\) — число объектов;
|
||
- \(d\) — число признаков;
|
||
- \(k\) — число классов или компонент;
|
||
- \(T\) — число итераций.
|
||
|
||
## Асимптотические обозначения
|
||
|
||
\(f(n)=O(g(n))\), если существуют \(c>0\) и \(n_0\), такие что
|
||
|
||
\[
|
||
0\leq f(n)\leq c\,g(n)\quad\text{при }n\geq n_0.
|
||
\]
|
||
|
||
\(\Omega(g(n))\) задаёт нижнюю границу, а \(\Theta(g(n))\) — одновременно
|
||
верхнюю и нижнюю с точностью до констант.
|
||
|
||
Например,
|
||
|
||
\[
|
||
3n^2+10n+7=\Theta(n^2),
|
||
\]
|
||
|
||
потому что при больших \(n\) квадратичный член доминирует. Это не означает,
|
||
что коэффициенты и младшие члены всегда неважны: для реальных размеров они
|
||
могут определять более быстрый вариант.
|
||
|
||
## Типичные скорости роста
|
||
|
||
От более медленного роста к более быстрому:
|
||
|
||
\[
|
||
O(1),\quad O(\log n),\quad O(n),\quad
|
||
O(n\log n),\quad O(n^2),\quad O(2^n).
|
||
\]
|
||
|
||
Удвоение \(n\) примерно удваивает линейную работу, увеличивает квадратичную
|
||
в четыре раза и экспоненциальную — радикально. Логарифмическое время возникает,
|
||
когда каждый шаг уменьшает задачу в постоянное число раз, как бинарный поиск.
|
||
|
||
## Анализ циклов
|
||
|
||
Последовательные блоки складываются:
|
||
|
||
\[
|
||
O(n)+O(n^2)=O(n^2).
|
||
\]
|
||
|
||
Вложенные независимые циклы перемножаются:
|
||
|
||
```python
|
||
total = 0.0
|
||
for i in range(n):
|
||
for j in range(d):
|
||
total += X[i, j]
|
||
```
|
||
|
||
Выполняется \(nd\) сложений, значит время \(O(nd)\), а дополнительная память
|
||
\(O(1)\). Не следует автоматически называть это \(O(n^2)\): \(n\) и \(d\) —
|
||
разные параметры.
|
||
|
||
## Стоимость линейной алгебры
|
||
|
||
Для \(\mathbf{A}\in\mathbb{R}^{m\times n}\) и
|
||
\(\mathbf{B}\in\mathbb{R}^{n\times p}\) матричное произведение требует
|
||
приблизительно \(mnp\) умножений и столько же сложений:
|
||
|
||
\[
|
||
\mathbf{C}_{ij}=\sum_{\ell=1}^{n}A_{i\ell}B_{\ell j},
|
||
\qquad O(mnp).
|
||
\]
|
||
|
||
Частные случаи:
|
||
|
||
- матрица-вектор \((n\times d)(d)\): \(O(nd)\);
|
||
- \(\mathbf{X}^\top\mathbf{X}\): \(O(nd^2)\);
|
||
- плотное решение системы \(d\times d\): обычно \(O(d^3)\);
|
||
- хранение \(\mathbf{X}\): \(O(nd)\).
|
||
|
||
Для разреженной матрицы важнее число ненулевых элементов
|
||
\(\operatorname{nnz}(\mathbf{X})\). Умножение на вектор может стоить
|
||
\(O(\operatorname{nnz}(\mathbf{X}))\), если формат хранения поддерживает
|
||
разреженность.
|
||
|
||
## Пример: линейная регрессия
|
||
|
||
Один полный градиент
|
||
|
||
\[
|
||
\nabla L
|
||
=\frac1n\mathbf{X}^\top(\mathbf{Xw}-\mathbf{y})
|
||
\]
|
||
|
||
состоит из:
|
||
|
||
1. \(\mathbf{Xw}\): \(O(nd)\);
|
||
2. вычитания \(\mathbf{y}\): \(O(n)\);
|
||
3. умножения \(\mathbf{X}^\top\mathbf{r}\): \(O(nd)\).
|
||
|
||
Итого \(O(nd)\) времени и \(O(n)\) дополнительной памяти для остатка.
|
||
За \(T\) итераций — \(O(Tnd)\).
|
||
|
||
Нормальные уравнения требуют формирования
|
||
\(\mathbf{X}^\top\mathbf{X}\) за \(O(nd^2)\) и решения системы примерно за
|
||
\(O(d^3)\). Какой подход быстрее, зависит от \(n,d,T\), памяти и
|
||
обусловленности.
|
||
|
||
## Векторизация: та же асимптотика, другое исполнение
|
||
|
||
```python
|
||
import numpy as np
|
||
|
||
rng = np.random.default_rng(0)
|
||
X = rng.normal(size=(1000, 100))
|
||
w = rng.normal(size=100)
|
||
|
||
# Математически это O(nd).
|
||
y_vectorized = X @ w
|
||
print(y_vectorized.shape)
|
||
```
|
||
|
||
Цикл Python и `X @ w` имеют одинаковый порядок \(O(nd)\), но векторизованная
|
||
операция выполняется оптимизированной библиотекой, использует кэш и SIMD,
|
||
а иногда несколько потоков. Big O не отражает эти константы.
|
||
|
||
Векторизация может увеличить пиковую память из-за временных массивов:
|
||
|
||
```python
|
||
# Создаёт временный массив формы X.shape.
|
||
column_energy = (X**2).sum(axis=0)
|
||
|
||
# Эквивалентное свёртывание без явного X**2 может быть экономнее.
|
||
column_energy_einsum = np.einsum("ij,ij->j", X, X)
|
||
print(np.allclose(column_energy, column_energy_einsum))
|
||
```
|
||
|
||
## Память и представление данных
|
||
|
||
Массив `float64` из \(nd\) элементов занимает примерно \(8nd\) байт,
|
||
`float32` — \(4nd\). Для миллиона объектов и тысячи плотных признаков
|
||
`float64` потребует около \(8\) ГБ только для матрицы.
|
||
|
||
Пиковая память включает:
|
||
|
||
\[
|
||
\text{данные}+\text{параметры}+\text{активации}
|
||
+\text{градиенты}+\text{временные массивы}.
|
||
\]
|
||
|
||
Срез NumPy часто является представлением без копирования, но fancy indexing
|
||
обычно создаёт копию. Проверять это можно через `np.shares_memory`.
|
||
|
||
## Локальность и кэш
|
||
|
||
Доступ к последовательным адресам памяти быстрее случайного доступа.
|
||
NumPy по умолчанию хранит двумерные массивы построчно в C-порядке. Поэтому
|
||
обход соседних элементов последней оси обычно лучше использует кэш.
|
||
|
||
Асимптотика двух обходов может совпадать, но фактическое время различаться
|
||
из-за промахов кэша и пропускной способности памяти. Современное вычисление
|
||
часто ограничено не числом арифметических операций, а перемещением данных.
|
||
|
||
## Пакетная обработка
|
||
|
||
Если весь набор не помещается в память устройства, его делят на батчи размера
|
||
\(b\). Для плотного линейного слоя:
|
||
|
||
\[
|
||
\mathbf{H}=\mathbf{X}_{b\times d}\mathbf{W}_{d\times h}
|
||
\]
|
||
|
||
стоимость одного батча \(O(bdh)\), а активации занимают \(O(bh)\). Уменьшение
|
||
\(b\) снижает пиковую память, но может хуже загружать устройство и увеличивать
|
||
накладные расходы. Градиент по мини-батчу также более шумный.
|
||
|
||
## Амортизированная сложность
|
||
|
||
Одна операция может иногда быть дорогой, но дешёвой в среднем по
|
||
последовательности. Добавление в динамический массив обычно \(O(1)\)
|
||
амортизированно: редкое расширение стоит \(O(n)\), но ёмкость увеличивается
|
||
геометрически, и общая стоимость \(n\) добавлений остаётся \(O(n)\).
|
||
|
||
Амортизированная оценка не равна средней по случайному входу: она гарантирует
|
||
стоимость последовательности операций без вероятностной модели входа.
|
||
|
||
## Время обучения и время предсказания
|
||
|
||
Сложность следует оценивать отдельно:
|
||
|
||
- подготовка данных;
|
||
- обучение;
|
||
- предсказание одного объекта и батча;
|
||
- память модели;
|
||
- память промежуточных вычислений.
|
||
|
||
Например, \(k\)-NN почти не обучается, но предсказание по плотным данным требует
|
||
сравнения с \(n\) объектами: \(O(nd)\). Линейная модель дорого оптимизируется,
|
||
но одно предсказание стоит \(O(d)\).
|
||
|
||
## Измерение производительности
|
||
|
||
Теоретическая оценка определяет ожидаемый рост, профилирование находит реальное
|
||
узкое место. Надёжный эксперимент:
|
||
|
||
1. прогревает код;
|
||
2. повторяет измерение;
|
||
3. меняет один размер входа;
|
||
4. фиксирует версии, dtype и устройство;
|
||
5. проверяет корректность сравниваемых результатов.
|
||
|
||
```python
|
||
from time import perf_counter
|
||
|
||
start = perf_counter()
|
||
for _ in range(100):
|
||
_ = X @ w
|
||
elapsed = perf_counter() - start
|
||
print(f"{elapsed / 100:.6e} s per run")
|
||
```
|
||
|
||
Очень короткие операции лучше измерять `timeit`; фоновая нагрузка и
|
||
многопоточность делают единичный замер ненадёжным.
|
||
|
||
## Компромиссы
|
||
|
||
- **Время против памяти:** кэширование ускоряет повторные вычисления, но
|
||
требует памяти.
|
||
- **Точность против скорости:** `float32` быстрее на многих ускорителях, но
|
||
имеет меньший диапазон точности.
|
||
- **Предвычисление против задержки:** индекс строится долго, зато ускоряет
|
||
запросы.
|
||
- **Точная задача против приближения:** случайные проекции и выборка уменьшают
|
||
стоимость ценой контролируемой ошибки.
|
||
|
||
## Типичные ошибки
|
||
|
||
- Big O не является временем в секундах и не учитывает константы.
|
||
- Нельзя скрывать разные переменные одним \(n\), если они растут независимо.
|
||
- Векторизация не меняет автоматически асимптотическую сложность.
|
||
- Оценка памяти без временных массивов часто занижена.
|
||
- Средняя, худшая и амортизированная сложности отвечают на разные вопросы.
|
||
- Более быстрый алгоритм не полезен, если он меняет результат или нарушает
|
||
численную устойчивость.
|
||
|
||
## Резюме
|
||
|
||
Сложность описывает масштабирование времени и памяти. Для ML особенно важны
|
||
\(n,d,k,T\), стоимость матричных операций, плотность данных и пиковая память.
|
||
Асимптотический анализ выбирает класс решения, а измерения и профилирование
|
||
уточняют константы и аппаратные ограничения.
|