Appearance
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].
Разбор по шагам
X[i_test]— вектор тестового объекта, shape(3072,);self.train_X[i_train]— вектор обучающего объекта, shape(3072,);X[i_test] - self.train_X[i_train]— поэлементная разность, shape(3072,);np.abs(...)— модули, shape(3072,);np.sum(...)— сумма → скаляр;- кладём скаляр в ячейку
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 одним выражением.