{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Расстояния между точками\n", "\n", "Длина вектора и расстояние между точками np.linalg.norm, расстояния от точки до многих, таблица всех попарных расстояний транслированием и ближайший сосед каждой точки.\n", "\n", "Курс NumPy · урок `np-distances` · [урок на сайте](https://ds-edu-trainer.vercel.app/courses/numpy/distances).\n", "\n", "Выполняйте ячейки по порядку (Shift+Enter), начиная с первой — она готовит урок. После каждого упражнения идёт\n", "ячейка проверки: она печатает ✓ / ✗ и итог." ], "id": "intro" }, { "cell_type": "code", "metadata": { "cellView": "form", "jupyter": { "source_hidden": true } }, "source": [ "# @title Подготовка урока — выполните эту ячейку первой\n", "# Проверяет версии пакетов, записывает файлы данных в папку data/ и определяет _check — проверку упражнений.\n", "import base64, os, zlib\n", "\n", "for _name, _min in {\"numpy\":\"2.0\"}.items():\n", " try:\n", " _have = __import__(_name).__version__\n", " except ImportError:\n", " print(f\"Нет пакета {_name}: выполните %pip install {_name} и перезапустите ядро\")\n", " continue\n", " if tuple(int(x) for x in _have.split(\".\")[:2]) < tuple(int(x) for x in _min.split(\".\")):\n", " print(f\"Урок написан для {_name} {_min} и новее, у вас {_have}: выполните %pip install -U {_name} и перезапустите ядро\")\n", "\n", "# ─── Проверка упражнений: тот же раннер, что у задач на сайте ───\n", "# ─── Запуск тестов ───────────────────────────────────────────────────────────\n", "\n", "_TIMEOUT = 2.0 # секунд на тест; отдельный тест может задать свой: test_x.timeout = 10\n", "\n", "\n", "def _call_with_timeout(target, seconds: float) -> bool:\n", " \"\"\"Запускает target() в отдельном потоке. Возвращает False, если за seconds он не завершился.\"\"\"\n", " import sys\n", " import threading\n", "\n", " if sys.platform == \"emscripten\": # Python в браузере: потоков нет, таймаут обеспечивает страница\n", " target()\n", " return True\n", " # Большой стек нужен, чтобы глубокая рекурсия давала RecursionError, а не аварийное завершение Python.\n", " for megabytes in (256, 64, 0):\n", " try:\n", " threading.stack_size(megabytes * 1024 * 1024)\n", " worker = threading.Thread(target=target, daemon=True)\n", " worker.start()\n", " except (ValueError, RuntimeError, MemoryError):\n", " continue\n", " worker.join(seconds)\n", " return not worker.is_alive()\n", " target() # потоки недоступны — запускаем без таймаута\n", " return True\n", "\n", "\n", "def _test_info(fn) -> dict:\n", " \"\"\"Описание теста, его лимит времени и сообщение на случай зависания.\"\"\"\n", " limit = getattr(fn, \"timeout\", _TIMEOUT)\n", " hint = getattr(fn, \"timeout_hint\", \"\")\n", " message = (\n", " f\"тест не завершился за {limit:g} с — возможно, бесконечный цикл или рекурсия: \"\n", " \"проверьте, что границы/аргументы изменяются на каждом шаге\" + (f\". {hint}\" if hint else \"\")\n", " )\n", " return {\"title\": (fn.__doc__ or fn.__name__).strip(), \"timeout\": limit, \"timeout_message\": message}\n", "\n", "\n", "def _error_result(title: str, error: BaseException, user_file: str | None) -> dict:\n", " \"\"\"Результат упавшего теста: статус, сообщение, тип исключения и строка в коде решения.\"\"\"\n", " line = None\n", " if user_file: # самый глубокий кадр в коде решения; ошибка внутри самих тестов — без номера строки\n", " tb = error.__traceback__\n", " while tb is not None:\n", " if tb.tb_frame.f_code.co_filename == user_file:\n", " line = tb.tb_lineno\n", " tb = tb.tb_next\n", " status, message = \"error\", f\"{type(error).__name__}: {error}\"\n", " if isinstance(error, NotImplementedError):\n", " status, message, line = \"not_written\", \"функция ещё не написана\", None\n", " elif isinstance(error, AssertionError):\n", " status, message = \"failed\", str(error) or \"проверка не прошла\"\n", " elif isinstance(error, RecursionError):\n", " message = \"RecursionError: слишком глубокая рекурсия — проверьте базовый случай и то, что задача уменьшается\"\n", " elif isinstance(error, MemoryError) or (isinstance(error, OverflowError) and \"index-sized\" in str(error)):\n", " message = f\"{type(error).__name__}: не хватило памяти — возможно, создаётся слишком большая структура данных\"\n", " return {\"title\": title, \"status\": status, \"message\": message, \"error_type\": type(error).__name__, \"line\": line}\n", "\n", "\n", "def _run_tests(verbose: bool = True, on_start=None, on_result=None, user_file: str | None = None) -> list[dict]:\n", " \"\"\"Запускает тесты задачи (_TESTS — функции из tests.py) по порядку, каждый — с таймаутом.\n", "\n", " Возвращает список результатов: {\"title\", \"status\", \"message\", \"error_type\", \"line\"}, где status —\n", " passed · failed · error · not_written · timeout · not_run. Если тест завис, при verbose=True печатает\n", " итог и завершает процесс: зависший поток остановить нельзя. on_start(i) и on_result(i, результат)\n", " вызываются по мере выполнения; user_file — имя файла с кодом решения для номеров строк в ошибках.\n", " \"\"\"\n", " import os\n", " import sys\n", "\n", " if verbose:\n", " try: # ✓ и кириллица в консоли Windows со старой кодировкой\n", " sys.stdout.reconfigure(encoding=\"utf-8\")\n", " except Exception: # noqa: BLE001 — reconfigure может не быть (перенаправленный вывод, браузер)\n", " pass\n", "\n", " tests = list(_TESTS)\n", " results: list[dict] = []\n", " not_written = hung = False\n", " for index, fn in enumerate(tests):\n", " info = _test_info(fn)\n", " outcome: dict = {}\n", "\n", " def target(fn=fn, outcome=outcome):\n", " try:\n", " fn()\n", " except BaseException as e:\n", " outcome[\"error\"] = e\n", "\n", " if on_start:\n", " on_start(index)\n", " if not _call_with_timeout(target, info[\"timeout\"]):\n", " results.append({\"title\": info[\"title\"], \"status\": \"timeout\", \"message\": info[\"timeout_message\"], \"error_type\": None, \"line\": None})\n", " for other in tests[index + 1:]:\n", " results.append({\"title\": _test_info(other)[\"title\"], \"status\": \"not_run\", \"message\": \"не запускался: предыдущий тест завис\", \"error_type\": None, \"line\": None})\n", " hung = True\n", " break\n", " error = outcome.get(\"error\")\n", " if error is None:\n", " result = {\"title\": info[\"title\"], \"status\": \"passed\", \"message\": \"\", \"error_type\": None, \"line\": None}\n", " else:\n", " result = _error_result(info[\"title\"], error, user_file)\n", " not_written = not_written or result[\"status\"] == \"not_written\"\n", " results.append(result)\n", " if on_result:\n", " on_result(index, result)\n", "\n", " if not_written: # пока функция не написана, «даром» пройденные тесты не засчитываются\n", " for r in results:\n", " if r[\"status\"] == \"passed\":\n", " r.update(status=\"not_written\", message=\"не засчитан, пока функция не написана\")\n", " for r in results:\n", " if len(r[\"message\"]) > 300:\n", " r[\"message\"] = r[\"message\"][:300] + \"…\"\n", "\n", " if verbose:\n", " if not_written:\n", " print(\"Функция ещё не написана — замените raise NotImplementedError своим кодом.\\n\")\n", " for r in results:\n", " mark = {\"passed\": \"✓\", \"not_run\": \"–\"}.get(r[\"status\"], \"✗\")\n", " print(f\"{mark} {r['title']}\")\n", " if r[\"message\"]:\n", " print(f\" {r['message']}\")\n", " passed = sum(r[\"status\"] == \"passed\" for r in results)\n", " print(\"─\" * 40)\n", " print(f\"Прошло {passed} из {len(results)}\" + (\" — всё верно!\" if passed == len(results) else \"\"))\n", " if hung:\n", " print(\"Выполнение остановлено: один из тестов завис.\")\n", " sys.stdout.flush()\n", " os._exit(1)\n", " return results\n", "\n", "\n", "def _check(*tests, names=()):\n", " \"\"\"Запускает проверки упражнения и печатает ✓ / ✗ и итог — как на сайте.\"\"\"\n", " for name in names:\n", " if \".\" in name: # «Класс.метод» из заготовки: класс должен быть объявлен\n", " if not isinstance(globals().get(name.split(\".\")[0]), type):\n", " print(f\"✗ класс {name.split('.')[0]} не объявлен — выполните ячейку упражнения\")\n", " return\n", " continue\n", " if name not in globals():\n", " print(f\"✗ переменная {name} не создана — выполните ячейку упражнения\")\n", " return\n", " if globals()[name] is Ellipsis:\n", " print(f\"✗ {name} пока равна ... — замените многоточие своим кодом\")\n", " return\n", " globals()[\"_TESTS\"] = list(tests)\n", " _run_tests()" ], "execution_count": null, "outputs": [], "id": "setup" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Где ближайший магазин? Какие два города дальше всего друг от друга? Какие покупатели похожи? Всё это —\n", "вопросы о **расстояниях**. Точку на карте удобно хранить как массив из двух координат, а много точек — как\n", "таблицу `(n, 2)`: строка — точка.\n", "\n", "## Расстояние между двумя точками\n", "\n", "Расстояние по прямой — теорема Пифагора из урока о векторизации: разности координат, квадраты, сумма, корень.\n", "Для этого есть готовая функция `np.linalg.norm` — **норма**, то есть длина вектора. Модуль `np.linalg` —\n", "линейная алгебра, раздел математики о векторах и матрицах. Расстояние между точками — длина их разности:" ], "id": "text-9" }, { "cell_type": "code", "metadata": {}, "source": [ "# Длина вектора и расстояние\n", "import numpy as np\n", "\n", "v = np.array([3, 4])\n", "print(np.sqrt((v ** 2).sum()))\n", "print(np.linalg.norm(v))\n", "\n", "a = np.array([1, 1])\n", "b = np.array([4, 5])\n", "print(np.linalg.norm(a - b)) # расстояние между точками a и b" ], "execution_count": null, "outputs": [], "id": "norm" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Вопрос.** Что выведет `print(np.linalg.norm(np.array([6, 8])))`?\n", "\n", "- `14.0`\n", "- `10.0`\n", "- `100.0`\n", "\n", "
Ответ\n", "\n", "`10.0`\n", "\n", "Норма — корень из суммы квадратов: √(36 + 64) = √100 = 10. 14 — простая сумма координат, 100 — сумма квадратов без корня.\n", "\n", "
" ], "id": "quiz-22" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## От одной точки до многих\n", "\n", "Три кафе — таблица `(3, 2)`, наша точка — массив `(2,)`. Их разность — транслирование: точка вычитается из\n", "**каждой строки** таблицы, и получается таблица разностей `(3, 2)`. А `np.linalg.norm(…, axis=1)` считает\n", "длину каждой строки — как агрегаты с `axis`, — то есть расстояние до каждого кафе:" ], "id": "text-31" }, { "cell_type": "code", "metadata": {}, "source": [ "# Расстояния до трёх кафе\n", "cafes = np.array([[0, 0], [2, 1], [5, 5]])\n", "me = np.array([1, 1])\n", "print(cafes - me) # разность с каждой строкой\n", "print(np.linalg.norm(cafes - me, axis=1)) # длина каждой строки — три расстояния" ], "execution_count": null, "outputs": [], "id": "to-many" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 1. Ближайший магазин\n", "\n", "В `shops` — координаты шести магазинов (км), в `home` — координаты дома. Сохраните в `dists` расстояние от дома\n", "до каждого магазина, а в `nearest` — номер строки ближайшего магазина.\n", "\n", "
Подсказка 1\n", "\n", "Всё как в демонстрации с кафе выше: там точка — `me`, таблица — `cafes`.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "Разности — `shops - home`, таблица `(6, 2)`; длина каждой строки — `np.linalg.norm` с `axis=1`.\n", "\n", "
\n", "
Подсказка 3\n", "\n", "Номер наименьшего — `argmin`.\n", "\n", "
" ], "id": "nearest-task" }, { "cell_type": "code", "metadata": {}, "source": [ "shops = np.array([\n", " [1.0, 2.0],\n", " [4.0, 6.0],\n", " [-2.0, 3.0],\n", " [3.0, -1.0],\n", " [0.5, 5.0],\n", " [6.0, 2.0],\n", "])\n", "home = np.array([2.0, 3.0])\n", "dists = ...\n", "nearest = ..." ], "execution_count": null, "outputs": [], "id": "nearest" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 1 — выполните после своего решения\n", "def test_dists():\n", " \"dists — расстояния до шести магазинов\"\n", " assert isinstance(dists, np.ndarray), \"dists — одно число: без оси norm считает длину всей таблицы\"\n", " assert dists.shape == (6,), f\"у dists форма {dists.shape}, а магазинов 6: нужна норма каждой строки\"\n", " assert np.allclose(dists, [1.414214, 3.605551, 4.0, 4.123106, 2.5, 4.123106], atol=1e-5), f\"dists = {np.round(dists, 3)} — это не расстояния от дома до магазинов\"\n", "\n", "\n", "def test_nearest():\n", " \"nearest — номер ближайшего магазина\"\n", " assert nearest == 0, f\"nearest = {nearest} — это не номер ближайшего магазина\"\n", "\n", "_check(test_dists, test_nearest, names=[\"dists\",\"nearest\"])" ], "execution_count": null, "outputs": [], "id": "nearest-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "shops = np.array([\n", " [1.0, 2.0],\n", " [4.0, 6.0],\n", " [-2.0, 3.0],\n", " [3.0, -1.0],\n", " [0.5, 5.0],\n", " [6.0, 2.0],\n", "])\n", "home = np.array([2.0, 3.0])\n", "dists = np.linalg.norm(shops - home, axis=1)\n", "nearest = dists.argmin()\n", "```\n", "\n", "
" ], "id": "nearest-solution" }, { "cell_type": "markdown", "metadata": {}, "source": [ "> **Типичная ошибка: norm без axis.**\n", ">\n", "> Без `axis=1` `np.linalg.norm` считает длину всей таблицы разностей как одного большого вектора — получается одно\n", "> число, а не расстояние до каждой точки. Если ждали массив, а пришло число, — добавьте `axis=1`." ], "id": "component-49" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Все попарные расстояния\n", "\n", "Расстояния между **всеми** парами точек дают таблицу `(n, n)`: в строке `i`, столбце `j` — расстояние от точки\n", "`i` до точки `j`. Её строят тем же приёмом, что таблицу всех пар в модуле о транслировании и все исходы трёх\n", "кубиков в мини-проекте о костях. Возьмём три точки `pts` формы `(3, 2)`. `pts[:, np.newaxis, :]` имеет форму\n", "`(3, 1, 2)`, `pts[np.newaxis, :, :]` — `(1, 3, 2)`; их разность транслируется до трёхмерного `(3, 3, 2)`:\n", "в `diff[i, j]` лежит `pts[i] - pts[j]` — две разности координат для пары точек `i` и `j`. Норма по последней\n", "оси — `axis=2` — превращает каждую пару разностей в расстояние, и остаётся таблица `(3, 3)`:" ], "id": "text-53" }, { "cell_type": "code", "metadata": {}, "source": [ "# Таблица расстояний между тремя точками\n", "pts = np.array([[0, 0], [3, 4], [6, 0]])\n", "diff = pts[:, np.newaxis, :] - pts[np.newaxis, :, :]\n", "print(diff.shape)\n", "print(diff[1, 0]) # pts[1] - pts[0]\n", "table = np.linalg.norm(diff, axis=2)\n", "print(table)" ], "execution_count": null, "outputs": [], "id": "pairwise" }, { "cell_type": "markdown", "metadata": {}, "source": [ "`pts[np.newaxis, :, :]` можно и не писать: по первому правилу транслирования `pts` сам дополнится единицей\n", "слева до `(1, 3, 2)`, так что `pts[:, np.newaxis, :] - pts` даёт то же самое.\n", "\n", "На диагонали нули: расстояние от точки до самой себя. Таблица симметрична: от `i` до `j` столько же, сколько\n", "от `j` до `i`." ], "id": "text-64" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 2. Самые далёкие города\n", "\n", "В `towns` — координаты пяти городов. Постройте для них таблицу попарных расстояний `dist` и сохраните\n", "в `max_dist` наибольшее расстояние между\n", "двумя городами.\n", "\n", "
Подсказка 1\n", "\n", "Разности — `towns[:, np.newaxis, :] - towns[np.newaxis, :, :]`.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "`dist = np.linalg.norm(разности, axis=2)`; наибольшее — `max`.\n", "\n", "
" ], "id": "farthest-task" }, { "cell_type": "code", "metadata": {}, "source": [ "towns = np.array([[0, 0], [3, 4], [6, 0], [7, 5], [2, 9]])\n", "dist = ...\n", "max_dist = ..." ], "execution_count": null, "outputs": [], "id": "farthest" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 2 — выполните после своего решения\n", "def test_dist():\n", " \"dist — таблица 5 × 5\"\n", " assert isinstance(dist, np.ndarray), f\"dist — это {type(dist).__name__}, а нужна таблица расстояний\"\n", " assert dist.shape != (5, 5, 2), \"у dist форма (5, 5, 2) — это разности; норму нужно взять по последней оси\"\n", " assert dist.shape == (5, 5), f\"у dist форма {dist.shape}, а нужна (5, 5): все пары пяти городов\"\n", " assert abs(dist[0, 1] - 5) < 1e-9, \"от города 0 до города 1 должно быть 5: проверьте разности\"\n", "\n", "\n", "def test_max():\n", " \"max_dist — наибольшее расстояние\"\n", " assert np.shape(max_dist) == (), \"max_dist — массив, а нужно одно число\"\n", " assert abs(max_dist - 9.848858) < 1e-5, f\"max_dist = {max_dist} — это не наибольшее расстояние между городами\"\n", "\n", "_check(test_dist, test_max, names=[\"dist\",\"max_dist\"])" ], "execution_count": null, "outputs": [], "id": "farthest-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "towns = np.array([[0, 0], [3, 4], [6, 0], [7, 5], [2, 9]])\n", "dist = np.linalg.norm(towns[:, np.newaxis, :] - towns[np.newaxis, :, :], axis=2)\n", "max_dist = dist.max()\n", "```\n", "\n", "
" ], "id": "farthest-solution" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Как найти для каждой точки **ближайшую другую**? `argmin` по строке найдёт ноль на диагонали — саму точку.\n", "Диагональ нужно исключить: заполним её бесконечностью `np.inf` — числом, которое больше любого другого.\n", "`np.fill_diagonal(a, значение)` записывает значение на диагональ таблицы — меняет её на месте:" ], "id": "text-79" }, { "cell_type": "code", "metadata": {}, "source": [ "# Ближайший сосед каждой точки\n", "demo = table.copy()\n", "np.fill_diagonal(demo, np.inf)\n", "print(demo)\n", "print(demo.argmin(axis=1))" ], "execution_count": null, "outputs": [], "id": "neighbor" }, { "cell_type": "markdown", "metadata": {}, "source": [ "> **Типичная ошибка: fill_diagonal ничего не возвращает.**\n", ">\n", "> Как `a.sort()` из урока о сортировке, `np.fill_diagonal` меняет таблицу на месте и возвращает `None`. Запись\n", "> `no_self = np.fill_diagonal(dist.copy(), np.inf)` сохранит в `no_self` не таблицу, а `None`, и следующая строка\n", "> упадёт с `'NoneType' object has no attribute`. Сначала сделайте копию, потом заполняйте её отдельной строкой." ], "id": "component-86" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 3. Ближайший сосед\n", "\n", "Сделайте копию `dist` в `no_self`, заполните её диагональ `np.inf` и сохраните в `neighbor` номер ближайшего\n", "другого города для каждого города, а в `neighbor_dist` — расстояние до него.\n", "\n", "
Подсказка 1\n", "\n", "`no_self = dist.copy()`, затем `np.fill_diagonal(no_self, np.inf)`.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "По строкам: `no_self.argmin(axis=1)` и `no_self.min(axis=1)`.\n", "\n", "
" ], "id": "closest-task" }, { "cell_type": "code", "metadata": {}, "source": [ "no_self = ...\n", "neighbor = ...\n", "neighbor_dist = ..." ], "execution_count": null, "outputs": [], "id": "closest" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 3 — выполните после своего решения\n", "def test_dist_kept():\n", " \"dist не изменился\"\n", " assert (dist.diagonal() == 0).all(), \"в dist изменилась диагональ: заполняйте копию\"\n", "\n", "\n", "def test_neighbor():\n", " \"neighbor — ближайший другой город\"\n", " assert np.shape(neighbor) == (5,), f\"у neighbor форма {np.shape(neighbor)}, а городов 5: нужен argmin по строкам\"\n", " assert neighbor.tolist() != [0, 1, 2, 3, 4], \"каждый город ближе всего к самому себе: уберите диагональ из поиска\"\n", " assert neighbor.tolist() == [1, 3, 1, 1, 1], f\"neighbor = {neighbor.tolist()} — это не ближайшие другие города\"\n", "\n", "\n", "def test_neighbor_dist():\n", " \"neighbor_dist — расстояние до ближайшего\"\n", " assert np.shape(neighbor_dist) == (5,), \"neighbor_dist — пять расстояний — по одному на город\"\n", " assert np.allclose(neighbor_dist, [5.0, 4.123106, 5.0, 4.123106, 5.09902], atol=1e-5), f\"neighbor_dist = {np.round(neighbor_dist, 3)}\"\n", "\n", "_check(test_dist_kept, test_neighbor, test_neighbor_dist, names=[\"no_self\",\"neighbor\",\"neighbor_dist\"])" ], "execution_count": null, "outputs": [], "id": "closest-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "no_self = dist.copy()\n", "np.fill_diagonal(no_self, np.inf)\n", "neighbor = no_self.argmin(axis=1)\n", "neighbor_dist = no_self.min(axis=1)\n", "```\n", "\n", "
" ], "id": "closest-solution" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Итоги\n", "\n", "- `np.linalg.norm(v)` — длина вектора; расстояние между точками — `np.linalg.norm(a - b)`.\n", "- До многих точек — `np.linalg.norm(points - p, axis=1)`.\n", "- Попарные расстояния — разность `(n, 1, 2)` и `(1, n, 2)`, норма по `axis=2`.\n", "- `np.inf` — бесконечность; `np.fill_diagonal` — записать значение на диагональ." ], "id": "text-99" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Подробнее в справочнике:** [numpy/linalg](https://ds-edu-trainer.vercel.app/reference/numpy/linalg) · [numpy/broadcasting](https://ds-edu-trainer.vercel.app/reference/numpy/broadcasting)" ], "id": "more" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python" }, "colab": { "provenance": [] } }, "nbformat": 4, "nbformat_minor": 5 }