Appearance
04. Векторизация: расстояния без циклов
В этом уроке реализуем compute_distances_no_loops — последнюю и главную цель раздела о расстояниях: всю матрицу dists одним numpy-выражением. Здесь же честно разберём, сколько памяти это стоит, и когда «полный векторинг» надо резать на части (чанки).
Ключевая идея: добавить оси с None
В уроке 03 мы умели вычитать один тестовый вектор из всей обучающей матрицы, потому что numpy сам растягивал вектор по строкам:
python
self.train_X - X[i] # (num_train, 3072) - (3072,) → (num_train, 3072)Теперь нужно сделать это одновременно для всех тестовых векторов. Для этого каждому массиву добавляем новую ось размерности 1 через None (она же np.newaxis):
python
X[:, None, :] # (num_test, 3072) → (num_test, 1, 3072)
self.train_X[None, :, :] # (num_train, 3072) → (1, num_train, 3072)Вычитание растягивает обе «единичные» оси и даёт массив всех пар:
python
diff = X[:, None, :] - self.train_X[None, :, :]
# (num_test, 1, 3072) - (1, num_train, 3072) → (num_test, num_train, 3072)
# diff[i, j] = X[i] - train_X[j] — как в двух циклах, но одним C-вызовомЗатем np.abs(diff) поэлементно, и .sum(axis=2) схлопывает ось признаков (2-я ось, 3072), оставляя матрицу расстояний:
python
dists = np.abs(X[:, None, :] - self.train_X[None, :, :]).sum(axis=2)
# (num_test, num_train)Мини-пример руками
Пусть D = 2 признака, 2 тестовых и 3 обучающих:
python
X = [[1, 2],
[4, 0]] # (2, 2)
train = [[0, 0],
[1, 1],
[3, 3]] # (3, 2)X[:, None, :] - train[None, :, :] → (2, 3, 2):
diff[0]=[[1,2]-[0,0], [1,2]-[1,1], [1,2]-[3,3]]=[[1,2],[0,1],[-2,-1]]diff[1]=[[4,0]-[0,0], [4,0]-[1,1], [4,0]-[3,3]]=[[4,0],[3,-1],[1,-3]]
Модули и сумма по последней оси:
dists[0]=[3, 1, 3]dists[1]=[4, 4, 4]
Итого dists = [[3, 1, 3], [4, 4, 4]] — ровно то, что давали бы два цикла.
Решение
python
def compute_distances_no_loops(self, X):
num_train = self.train_X.shape[0]
num_test = X.shape[0]
dists = np.abs(X[:, None, :] - self.train_X[None, :, :]).sum(axis=2)
return dists.astype(np.float32).astype(np.float32) — на всякий случай фиксируем тип: если данные случайно пришли float64, промежуточный массив был бы вдвое тяжелее (см. ниже).
Сколько памяти съедает «трёхмерный» промежуточный массив
Выражение создаёт во временной памяти массив (num_test, num_train, 3072). Считаем байты: num_test × num_train × 3072 × 4 (float32).
| num_test | num_train | float32 | float64 |
|---|---|---|---|
| 100 | 1 000 | 1.2 ГБ | 2.5 ГБ |
| 100 | 10 000 | 12 ГБ | 25 ГБ |
| 1 000 | 1 000 | 12 ГБ | 25 ГБ |
На типичном ноутбуке 1.2 ГБ — терпимо, 12 ГБ — уже «машине больно» (может начать использовать swap и резко замедлиться). Поэтому на больших выборках полный векторинг упирается не в скорость вычислений, а в память.
Когда векторинг быстрее, а когда нет (честно)
В %timeit в ноутбуке вы увидите времена всех трёх реализаций. Что важно понять:
- Требование задания — корректность (все три реализации дают одинаковый
dists, проверяетсяnp.iscloseна конкретных ячейках). Скорость — наблюдение, а не экзамен. - Классический результат на современных машинах:
no_loopsбыстрееone_loop, аone_loopбыстрееtwo_loops— выигрыш растёт с числом тестовых образцов, потому что Python-циклы (two_loops) добавляют накладные расходы на каждый изnum_test × num_trainвызовов. - Наш эталон для цифр: на машине, на которой сверялись решения, при
100×1000все три реализации оказались одного порядка (0.4–0.7 с), а при1000×1000—two_loopsдаже быстрее, потому что узким местом стала пропускная способность памяти (огромный промежуточный массив), а не Python-оверхед. Ваш результат может отличаться — это нормально. Главное:np.allcloseмежду реализациями —True.
xml
<svg viewBox="0 0 640 200" font-family="sans-serif" font-size="14">
<!-- memory vs speed axes -->
<line x1="60" y1="160" x2="600" y2="160" stroke="var(--border)" stroke-width="1"/>
<line x1="60" y1="160" x2="60" y2="30" stroke="var(--border)" stroke-width="1"/>
<text x="330" y="185" text-anchor="middle" fill="var(--muted)">число образцов (num_test × num_train)</text>
<text x="35" y="95" text-anchor="middle" fill="var(--muted)" transform="rotate(-90 35 95)">накладные расходы / память</text>
<!-- two loops: high python overhead early -->
<path d="M 70 55 C 180 75, 350 120, 590 140" fill="none" stroke="var(--c1)" stroke-width="2.5"/>
<text x="560" y="132" text-anchor="end" fill="var(--c1)">two_loops (Python-оверхед)</text>
<!-- one loop -->
<path d="M 70 95 C 200 95, 380 115, 590 122" fill="none" stroke="var(--c2)" stroke-width="2.5"/>
<text x="560" y="112" text-anchor="end" fill="var(--c2)">one_loop</text>
<!-- no loops: flat compute but memory grows -->
<path d="M 70 110 C 250 105, 400 108, 590 100" fill="none" stroke="var(--c3)" stroke-width="2.5"/>
<text x="560" y="92" text-anchor="end" fill="var(--c3)">no_loops (векторинг)</text>
<text x="330" y="25" text-anchor="middle" fill="var(--muted)">на «медленных» CPU память может догнать и обогнать overhead — смотрите на своей машине</text>
</svg>Чанки: векторинг, который влезает в память
Если тестовая выборка большая, считаем dists по блокам строк — промежуточный массив становится (chunk, num_train, 3072):
python
def compute_distances_chunked(self, X, chunk_size=100):
num_train = self.train_X.shape[0]
num_test = X.shape[0]
dists = np.zeros((num_test, num_train), np.float32)
for start in range(0, num_test, chunk_size):
stop = min(start + chunk_size, num_test)
block = X[start:stop, None, :] - self.train_X[None, :, :]
dists[start:stop] = np.abs(block).sum(axis=2).astype(np.float32)
return distsРезультат идентичен полному вектингу (np.allclose — True), а пиковая память ограничена chunk_size. Это стандартный приём, который мы встретим и в нейросетях (batching).
Проверка
python
import numpy as np
from knn import KNN
from dataset import load_svhn
train_X, train_y, test_X, test_y = load_svhn("data_stub", 1000, 100)
Xtr = train_X.reshape(1000, -1)
Xte = test_X.reshape(100, -1)
knn = KNN(k=5).fit(Xtr, train_y)
d2 = knn.compute_distances_two_loops(Xte)
d1 = knn.compute_distances_one_loop(Xte)
d0 = knn.compute_distances_no_loops(Xte)
print(d0.shape, d0.dtype) # (100, 1000) float32
print("two vs one :", np.allclose(d2, d1)) # True
print("two vs none:", np.allclose(d2, d0)) # True
# точечная проверка, как в ноутбуке:
print(np.isclose(d0[0, 10], np.sum(np.abs(Xte[0] - Xtr[10])))) # TrueОжидаемый вывод:
text
(100, 1000) float32
two vs one : True
two vs none: True
TrueПрактика
1. Перепишите no_loops для L2-расстояния одной строкой (подсказка: возведите разность в квадрат до суммы: np.sqrt(((X[:, None, :] - self.train_X[None, :, :]) ** 2).sum(axis=2))). Проверьте на малом примере, что формула совпадает с ручным L2 для пары (0,0) и (3,4) (ответ: 5).
2. С какой chunk_size пиковый промежуточный массив в compute_distances_chunked не превысит 1 ГБ, если num_train = 10000 и данные float32? (Считайте: chunk × 10000 × 3072 × 4 ≤ 1e9.)
3. Напишите один print, который покажет разницу между d0 и d1 по максимуму абсолютной ошибки: print(np.abs(d0 - d1).max()). Почему он не обязан быть строго 0, а np.allclose тем не менее возвращает True?
Показать решения
1.
python
def compute_distances_l2_no_loops(self, X):
return np.sqrt(((X[:, None, :] - self.train_X[None, :, :]) ** 2).sum(axis=2)) \
.astype(np.float32)Проверка: np.sqrt((3**2 + 4**2)) = 5.
2. chunk ≤ 1e9 / (10000 × 3072 × 4) = 1e9 / 1.2288e8 ≈ 8.1 → chunk_size = 8 (или округлим вниз, например 8). На практике чаще берут круглые 16/32 и мирятся с 2–4 ГБ, если RAM позволяет.
3. print(np.abs(d0 - d1).max()) — покажет число порядка 1e-4…1e-5. Это округление float32: обе реализации складывают одни и те же 3072 числа, но в разном порядке (в one_loop — построчно, в no_loops — в порядке SIMD-блоков), и сложение чисел с плавающей точкой не коммутативно в точности эпсилона. np.allclose допускает маленькую относительную ошибку — поэтому True.
Итоги урока
- Векторинг = добавить оси
None:X[:, None, :] - train_X[None, :, :]→(nt, nn, D)→.sum(axis=2)→dists; - Промежуточный массив
(nt, nn, 3072)— этоnt×nn×3072×4байта: 1.2 ГБ на100×1000, 12 ГБ на100×10000; - На больших данных векторинг режут чанками — результат тот же, память ограничена;
- Скорость зависит от машины: проверяйте
np.allclose(обязательно) и%timeit(для понимания), не ожидая «канонического» порядка.
Следующий урок — 05. Предсказание и метрики: учим KNN голосовать (argpartition + bincount) и считаем precision/recall/F1/accuracy.