<<
>>

Структура данных для хранения подквадратов

Высокоуровневое описание алгоритма зависит от возможности назвать подква- драт Sst и быстро определить, какие точки P содержатся в нем (если они есть). Словарь — наиболее естественная структура данных для реализации таких опе- раций.
Универсальное множество U возможных элементов представляет собой множество всех подквадратов, а множество S, хранимое в структуре данных, со- стоит из подквадратов с точками из множества P', встречавшимися до настоящего момента. А конкретно, для каждой точки p' P' в словаре хранится подквадрат,

содержащий ее, вместе с индексом p`. Заметим, что A/* = lJ⅜⅞)f в общем случае намного больше количества точек n. Таким образом, данная ситуация напоминает ту, что была описана в разделе 13.6 для хеширования: универсальное множество возможных элементов (множество всех подквадратов) намного больше количества индексируемых элементов (подквадраты, содержащие входные точки, которые уже встречались).

Затем, при рассмотрении следующей точки p в случайном порядке, определя- ется содержащий ее подквадрат Sst и выполняется операция Lookup для каждого из 25 подквадратов, близких к S. Для всех точек, обнаруженных этими операциями Lookup, вычисляется расстояние до p.

Если ни одно из этих расстояний не меньше δ, то ближайшее расстояние не изменяется; мы вставляем St (вместе c p) в словарь и переходим к следующей точке.

Но если будет найдена точкаp', для которой δ' = d(p,p') < δ, то ближайшую пару необходимо обновить. Обновление приводит к весьма масштабным последствиям: так как расстояние ближайшей пары уменьшилось с δ до δ', вся коллекция под- квадратов вместе с поддерживающим ее словарем становится бесполезной — ведь она приносит пользу только в том случае, если минимальное расстояние равно δ. Соответственно мы вызываем MakeDictionary для создания нового, пустого сло- варя, в котором хранятся подквадраты с длиной стороны δ'/2. Для каждой точки, встреченной до настоящего момента, мы определяем содержащий ее подквадрат (в новом наборе подквадратов), после чего вставляем этот подквадрат в словарь. После того как это будет сделано, можно переходить к вставке следующей точки в случайном порядке.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Структура данных для хранения подквадратов:

  1. 3. Использование программ для ЭВМ, баз данных и топологий ИМС третьими лицами
  2. Свободное воспроизведение программ для ЭВМ и баз данных. Декомпилирование программ для ЭВМ
  3. § 6. Авторско-правовая охрана программ для ЭВМ, баз данных и топологий интегральных микросхем
  4. 12.2.2. Правовое регулирование информационных отношений при производстве и распространении программ для ЭВМ и баз данных
  5. 1. Понятие программы для ЭВМ, базы данных и топологии интегральной микросхемы и основные правила их охраны
  6. Упражнение для выявления структуры вашего характера
  7. 4. Хранение в камерах хранения транспортных организаций
  8. 4. Хранение в камерах хранения транспортных организаций
  9. Жизненная задача и высшее «Я» для оральной структуры
  10. Структура массово-информационной деятельности: сбор, обработка, компоновка, передача, восприятие, трансформация, хранение и использование массовой информации. Потенциальная, принятая и реальная информация. Семантический, синтаксический и прагматический аспекты массово-информационных текстов.
  11. КРИТЕРИИ ОЦЕНКИ ПРОИЗВЕДЕНИЯ с ТОЧКИ ЗРЕНИЯ его ЖАНРОВО–ТЕМАТИЧЕСКОЙ СТРУКТУРЫ и ЗРИТЕЛЬСКОГО ВОСПРИЯТИЯ (для исследователей экранной продукции)
  12. 5.2.17. Укрепления благосостояния своих лучших сотрудников для увеличения функциональности всех элементов, составляющих структуру и архитектуру цели
  13. Григорьев Ю.А., Ревунков Г.И.. Банки данных, 2002
  14. Оценка данных о личности.