Главная » Java, Структуры данных и алгоритмы » Регистрационные файлы (log-файлы)

0

Простейшим способом реализации словаря является неупорядоченный вектор, список или обычная последовательность для хранения пар «ключ-элемент». Такая реализация обычно называется регистрационным файлом (log file), или контрольным следом (audit trail). Основной сферой применения таких видов реализации являются ситуации, где требуется архивация структурированных данных. Например, многие финансовые базы данных хранят таким способом словари всех своих транзакций. Точно так же многие программные операционные системы, такие как Web-серверы и программы удаленной регистрации, хранят регистрационные файлы всех обработанных через Интернет запросов. Типичным сценарием этих приложений является большое количество вводимых данных и небольшое количество поисковых запросов. Например, поиск в регистрационном файле таких систем обычно осуществляется только в случаях необходимости анализа нестандартных ситуаций, вроде сбоя в системе. Таким образом, регистрационные файлы должны поддерживать простой и быстрый ввод данных, возможно, в ущерб времени на поиск. Формально можно сказать, что регистрационный файл представляет собой реализацию словаря Д использующего последовательность S (для полной универсальности), чтобы хранить объекты из D в произвольном порядке (см. рис. 8.2).

Рис. 8.2. Реализация словаря D с помощью регистрационного файла. В этом словаре показаны только ключи, чтобы подчеркнуть неупорядоченную последовательность реализации

В свою очередь, допустим, что последовательность S, используемая для регистрационного файла, реализована вектором или двусвязным списком (см. раздел 5.3). Будем считать реализацию регистрационного файла D как реализацию с помощью неупорядоченной последовательности, поскольку ключи не влияют на линейную организацию своих элементов в S.

Анализ структуры данных регистрационного файла

Необходимое для регистрационного файла пространство составляет Q(n), так как структуры, векторы и связные списки могут отслеживать

и поддерживать используемые объемы памяти пропорционально своим размерам. Кроме того, имея дело с реализацией АТД «словарь» с помощью регистрационного файла, можно легко и красиво определить операцию insertItem(A:,e) одним вызовом метода insertLast в S, который просто добавляет новый объект в конец последовательности. Таким образом, для выполняемой над D операции insertItem(A:,e) потребуется 0(1) времени.

К сожалению, такая реализация не обеспечивает нормального выполнения метода findElement. Операция findElement(A;) осуществляется сканированием всей последовательности S с просмотром каждого из объектов. Например, можно итеративно запускать операцию after из последовательности до тех пор, пока объект с ключом к не будет найден, либо достигнут конец последовательности. Наибольшее время выполнения метода, и это вполне очевидно, будет при безуспешном завершении операции, когда достигнут конец очереди и обследованы все п элементов. Это означает, что метод findElement выполняется за 0(п) времени.

Точно так же в наихудшем случае понадобится линейное время на выполнение операции removeElement(A;), так как, чтобы удалить объект с указанным ключом, его необходимо предварительно найти, проскани- ровав всю последовательность S. Таким образом, наибольшее время выполнения метода removeElement(A;) в регистрационном файле есть 0(п).

Операции findAHElements и removeAHElements всегда будут требовать сканирования последовательности S, следовательно, время их выполнения составит 0(п). Это значит, что они выполняются в линейном времени при успешном и при неуспешном исходе.

В заключение отметим, что реализация словаря с помощью регистрационного файла обеспечивает возможность быстрого ввода, но медленный поиск и удаление. Следовательно, использовать регистрационный файл следует только при небольшом словаре, или предполагается, что число вводов будет значительно превышать количество поисковых запросов или удалений. Конечно, транзакции архивных баз данных и операционных систем в точности соответствуют таким ситуациям. Но существует немало применений, в которых количество вводов в словарь сопоставимо с количеством поисковых запросов и удалений, и в этих случаях реализация с помощью регистрационного файла не очень удобна. Тем не менее для достижения быстрого ввода, поиска и удаления в таких случаях часто может использоваться реализация неупорядоченного словаря, которая приведена ниже.

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

По теме:

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