Структура данных для хранения подквадратов
Высокоуровневое описание алгоритма зависит от возможности назвать подквадрат Sst и быстро определить, какие точки P содержатся в нем (если они есть). Словарь — наиболее естественная структура данных для реализации таких операций.
содержащий ее, вместе с индексом p’. Заметим, что в общем случае намного больше количества точек n. Таким образом, данная ситуация напоминает ту, что была описана в разделе 13.6 для хеширования: универсальное множество возможных элементов (множество всех подквадратов) намного больше количества индексируемых элементов (подквадраты, содержащие входные точки, которые уже встречались).
Затем, при рассмотрении следующей точки p в случайном порядке, определяется содержащий ее подквадрат Sst и выполняется операция Lookup для каждого из 25 подквадратов, близких к Sst. Для всех точек, обнаруженных этими операциями Lookup, вычисляется расстояние до p. Если ни одно из этих расстояний не меньше δ, то ближайшее расстояние не изменяется; мы вставляем Sst (вместе c p) в словарь и переходим к следующей точке.
Но если будет найдена точка p’, для которой δ‘ = d(p, p’) < δ, то ближайшую пару необходимо обновить. Обновление приводит к весьма масштабным последствиям: так как расстояние ближайшей пары уменьшилось с δ до δ‘, вся коллекция подквадратов вместе с поддерживающим ее словарем становится бесполезной — ведь она приносит пользу только в том случае, если минимальное расстояние равно δ.
Соответственно мы вызываем MakeDictionary для создания нового, пустого словаря, в котором хранятся подквадраты с длиной стороны δ‘/2. Для каждой точки, встреченной до настоящего момента, мы определяем содержащий ее подквадрат (в новом наборе подквадратов), после чего вставляем этот подквадрат в словарь.
После того как это будет сделано, можно переходить к вставке следующей точки в случайном порядке.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Разработка универсального класса хеш-функций
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу