Skip to content

03. Матрица расстояний: два цикла и один цикл ​

В этом уроке реализуем два из трёх метода расчёта dists в knn.py: compute_distances_two_loops (самый наивный) и compute_distances_one_loop (частичная векторизация). К концу урока вы поймёте, за счёт чего каждая «экономия цикла» вообще возможна — это чистая работа с shape-ами.

Подготовка: «выпрямляем» изображения ​

load_svhn отдаёт train_X формы (num_train, 32, 32, 3). Для KNN каждый объект должен быть одним вектором признаков, поэтому перед fit изображения «выпрямляют»:

python
train_X = train_X.reshape(num_train, -1)   # (num_train, 3072)
test_X = test_X.reshape(num_test, -1)      # (num_test, 3072)

-1 в reshape означает «остальное число элементов подберёшь сам»: 32*32*3 = 3072. После этого X[i] — это вектор (3072,), и расстояние между двумя такими векторами считается поэлементно.

Метод 1. compute_distances_two_loops ​

Что просит TODO ​

python
dists = np.zeros((num_test, num_train), np.float32)
for i_test in range(num_test):
    for i_train in range(num_train):
        # TODO: Fill dists[i_test][i_train]
        pass

Структура дана: два вложенных цикла, по ним пробегает каждый тестовый объект против каждого обучающего. Нужно заполнить ровно одну ячейку dists[i_test, i_train].

Разбор по шагам ​

  1. X[i_test] — вектор тестового объекта, shape (3072,);
  2. self.train_X[i_train] — вектор обучающего объекта, shape (3072,);
  3. X[i_test] - self.train_X[i_train] — поэлементная разность, shape (3072,);
  4. np.abs(...) — модули, shape (3072,);
  5. np.sum(...) — сумма → скаляр;
  6. кладём скаляр в ячейку dists[i_test, i_train].

Решение ​

python
def compute_distances_two_loops(self, X):
    num_train = self.train_X.shape[0]
    num_test = X.shape[0]
    dists = np.zeros((num_test, num_train), np.float32)
    for i_test in range(num_test):
        for i_train in range(num_train):
            dists[i_test, i_train] = np.sum(np.abs(X[i_test] - self.train_X[i_train]))
    return dists

Подводка из оригинала: в исходнике метод заканчивается pass — return dists отсутствует. Без него метод вернёт None, и всё падает. Добавляем return (он же нужен во всех трёх методах расстояний).

Сложность: num_test × num_train итераций, в каждой — O(3072) работы. Для 100 × 1000 это 100 000 вычислений расстояний — в Python-циклах это заметно (сотни миллисекунд), но на стабе приемлемо.

Метод 2. compute_distances_one_loop ​

Что просит TODO ​

python
for i_test in range(num_test):
    # TODO: Fill the whole row of dists[i_test]
    # without additional loops or list comprehensions
    pass

Задача: заполнить целую строку dists[i_test] одним выражением, без внутренних циклов. Идея: один тестовый объект мы всё равно берём в цикле, но против всех обучающих считаем расстояния разом.

Ключ: broadcasting по строкам ​

self.train_X — это матрица (num_train, 3072), а X[i_test] — вектор (3072,). Когда numpy вычитает их, вектор растягивается (broadcast) по всем строкам:

python
diffs = self.train_X - X[i_test]
# (num_train, 3072) - (3072,) → (num_train, 3072)
# каждая строка j: train_X[j] - X[i_test]

Затем np.abs(diffs) — поэлементно, и np.sum(diffs, axis=1) суммирует вдоль осей признаков (оси 1), сводя каждую строку к скаляру:

python
dists[i_test] = np.sum(np.abs(self.train_X - X[i_test]), axis=1)
# (num_train, 3072) → (num_train,)

axis=1 — «схлопнуть второй индекс (колонки)». Результат — вектор длиной num_train, ровно то, что нужно положить в строку dists[i_test].

Решение ​

python
def compute_distances_one_loop(self, X):
    num_train = self.train_X.shape[0]
    num_test = X.shape[0]
    dists = np.zeros((num_test, num_train), np.float32)
    for i_test in range(num_test):
        dists[i_test] = np.sum(np.abs(self.train_X - X[i_test]), axis=1)
    return dists

Почему это быстрее: внутренний проход по num_train × 3072 элементам выполняется C-кодом numpy (векторизация), а не Python-байткодом. Python-цикл остался только по num_test (100 итераций) — это несущественно.

Проверка: оба метода обязаны совпасть ​

Задание требует, чтобы реализации давали один и тот же результат. Проверяем np.allclose (сравнение с допуском — float32 храним неточно):

python
from knn import KNN
from dataset import load_svhn
import numpy as np

train_X, train_y, test_X, test_y = load_svhn("data_stub", 1000, 100)
train_X = train_X.reshape(1000, -1)   # (1000, 3072)
test_X = test_X.reshape(100, -1)      # (100, 3072)

knn = KNN(k=5)
knn.fit(train_X, train_y)

d_two = knn.compute_distances_two_loops(test_X)
d_one = knn.compute_distances_one_loop(test_X)

print(d_two.shape, d_one.shape)          # (100, 1000) (100, 1000)
print("allclose:", np.allclose(d_two, d_one))   # True

Ожидаемый вывод:

text
(100, 1000) (100, 1000)
allclose: True

Проверка скорости ​

Измерим время (на стабе; на реальном SVHN пропорционально):

python
import time

def time_call(fn, *args):
    t0 = time.perf_counter()
    result = fn(*args)
    return result, time.perf_counter() - t0

_, t2 = time_call(knn.compute_distances_two_loops, test_X)
_, t1 = time_call(knn.compute_distances_one_loop, test_X)
print(f"two loops: {t2:.4f}s")
print(f"one loop : {t1:.4f}s")
print(f"speedup  : {t2 / t1:.1f}x")

Ожидаемый вывод (ориентир на эталонной машине; у вас цифры будут своими — это нормально):

text
two loops: 0.4100s
one loop : 0.6000s
speedup  : 0.7x

Честное чтение результатов. Требование задания — корректность (ячейка ноутбука проверяет np.isclose(dists[0, 10], ...)), а не скорость. На эталонной (медленной) машине при маленьком 100×1000 обе реализации одного порядка: Python-оверхед двух циклов — это 100 000 вызовов numpy (~4 мкс каждый), а одноцикловая версия тратит время на прогон массивов (1000, 3072) через память. На обычных современных машинах одноцикловый метод быстрее двухциклового (и разница растёт с num_test), а на машинах с узкой полосой памяти — может быть и наоборот. Поэтому смотрите на %timeit как на наблюдение, а не как на критерий «сдал/не сдал».

Практика ​

1. В compute_distances_two_loops замените np.sum(np.abs(...)) на np.sqrt(np.sum((X[i_test] - self.train_X[i_train]) ** 2)) (L2 вместо L1). Сохранится ли равенство np.allclose между two_loops и one_loop? Что нужно сделать, чтобы «сверить» их снова?

2. Объясните своими словами, почему в one_loop именно axis=1, а не axis=0. Что будет, если поставить axis=0 (подсказка: сравните .shape результата с формой строки dists[i_test])?

3. Напишите в одну строку (без циклов вообще) выражение, которое даст тот же самый dists[i_test] — то есть превратите one_loop в «нулевой цикл» для одного тестового примера. (Полное обобщение на все num_test строк мы сделаем в уроке 04.)

Показать решения

1. Нет, allclose станет False, потому что one_loop всё ещё считает L1, а two_loops — L2. Чтобы сверить, нужно заменить формулу в one_loop на L2-вариант: dists[i_test] = np.sqrt(np.sum((self.train_X - X[i_test]) ** 2, axis=1)). (В самом задании L2 не используется — это только для понимания.)

2. Строка dists[i_test] имеет форму (num_train,). np.sum(..., axis=1) схлопывает ось признаков (колонки, 3072) и оставляет num_train значений — ровно по одному на обучающий объект. axis=0 схлопнул бы ось num_train, и результат имел бы форму (3072,) — несовпадение форм, numpy бросит ошибку на присваивании dists[i_test] = ....

3. dists_one = np.sum(np.abs(self.train_X - X_single), axis=1), где X_single — один тестовый вектор (3072,). Это и есть тело one_loop без цикла — обобщение на все строки через broadcasting по третьей оси — в уроке 04.

Итоги урока ​

  • Изображения перед KNN «выпрямляют»: reshape(n, -1) → (n, 3072);
  • two_loops — два Python-цикла, одна ячейка за итерацию; наивный, медленный;
  • one_loop — строка за один векторный вычитание + axis=1; C-скорость;
  • Обязательна проверка np.allclose между реализациями и замер скорости (одноцикловый — на порядок быстрее);
  • Не забудьте return dists — в скелете его нет.

Следующий урок — 04. Векторизация и broadcasting: убираем последний цикл и считаем всю матрицу dists одним выражением.