Главная » Java, Структуры данных и алгоритмы » Внешний поиск

0

В этом разделе рассматривается проблема реализации упорядоченного словаря для большого количества объектов, не помещающихся в основной памяти. Одним из наиболее распространенных применений больших словарей является система баз данных. Когда данные не помещаются в основной памяти, они хранятся во внешней памяти (external memory), которой обычно служит жесткий диск. Время доступа к информации значительно выше времени ее передачи, поэтому объекты сгруппированы в смежные секции, называемые блоками, дисковыми блоками (disc blocks). Аналогично назовем процесс передачи блоков между внешней и основной памятью дисковой передачей (disk transfer). Но и при использовании этой терминологии приведенные методики поиска применимы и в случаях, когда основной памятью является кэш центрального процессора, а в качестве внешней рассматривается основная (RAM) память, так как строки кэша также группируются в блоки.

Время доступа к основной памяти на несколько порядков выше времени доступа к диску. Таким образом, основной задачей при хранении словаря во внешней памяти является сведение до минимума количества дисковых передач, необходимых для выполнения запросов или обновлений. В принципе различие скорости обращений к диску и к памяти настолько велико, что следует задуматься над обеспечением большего количества внутренних обращений, которые позволили бы избежать дисковых передач. Поэтому произведем анализ производительности реализации словаря путем определения количества дисковых передач, требующихся для выполнения стандартных словарных операций поиска и обновления. Назовем такой подсчет I/О-сложностью (I/O complexity) используемого алгоритма.

Вначале рассмотрим простую реализацию словаря, использующую последовательность для хранения объектов. Если последовательность реализована как неупорядоченный двусвязный список, то есть как созданный на основе списка регистрационный файл, то каждый ввод будет выполняться с количеством 0(1) передач, но удаление и поиск потребуют, по крайней мере, 0(я) передач, где п — количество объектов в словаре, поскольку каждый следующий запрос может обращаться к новому блоку. Время поиска можно улучшить до 0(п/В) передач (с помощью метода, оставленного для решения в упражнении 3-9.19), где В — количество узлов в списке, который может входить в блок. Но даже такая производительность мала. В качестве альтернативы можно было бы реализовать последовательность с помощью сортированного вектора, то есть поисковой таблицы. В этом случае поиск будет выполняться за 0(log2«) передач (благодаря алгоритму бинарного поиска), что гораздо быстрее. Но такое решение требует G(n/B) передач для реализации ввода или удаления, так как при перемещении объектов вверх или вниз может понадобиться обращение ко всем блокам, хранящим массив. Таким образом, реализации

словаря на основе последовательности с точки зрения внешней памяти, малоэффективны.

Поэтому рассмотрим логарифмические стратегии, использующие сбалансированные бинарные деревья (такие как AVL-деревья или красно-черные деревья), или другие поисковые системы с логарифмическим временем обработки запросов и обновлений (например, skip-списки). Данные методики хранят словарные объекты в узлах бинарного дерева или графах (для skip-списков). Обычно узел, к которому происходит обращение при запросе или обновлении, в каждой из таких структур является ( отдельным узлом. То есть данным методам обычно требуется 0(log2«) передач для выполнения операции запроса или обновления. Это вполне удовлетворительно, но можно значительно улучшить. В частности, приведем способы словарных операций запроса и обновления всего за 0(logBn), что составляет 0(log п / log В) передач, где В намного больше 2.

Повышение производительности при работе с внешней памятью для реализаций словаря, приведенных выше, требует уменьшения дисковых передач — то есть следует добиться производительности в О(В) обращений к внутренней памяти, где В — размер дискового блока. Аппаратное и программное обеспечение, управляющее диском, выполняет такое количество операций только для переноса блока во внутреннюю память. Но это небольшая плата за возможность избежать дисковой передачи.

Однако такое обращение к внутренней памяти не приводит к значительной экономии времени при обращении к диску.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии