Skip to content

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_testnum_trainfloat32float64
1001 0001.2 ГБ2.5 ГБ
10010 00012 ГБ25 ГБ
1 0001 00012 ГБ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.