Простейшие методы построения таблиц идентификаторов - Хеш-функция
В простейшем случае таблица идентификаторов представляет собой линейный неупорядоченный список, или массив, каждая ячейка которого содержит данные о соответствующем элементе таблицы. Размещение новых элементов в такой таблице выполняется путем записи информации в очередную ячейку массива или списка по мере обнаружения новых элементов в исходной программе. Поиск нужного элемента в таблице будет в этом случае выполняться путем последовательного перебора всех элементов и сравнения их имени с именем искомого элемента, пока не будет найден элемент с таким же именем. Тогда если за единицу времени принять время, затрачиваемое компилятором на сравнение двух строк (в современных вычислительных системах такое сравнение чаще всего выполняется одной командой), то для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений. Время, требуемое на добавление нового элемента в таблицу (TД), не зависит от числа элементов в таблице (N). Но если N велико, то поиск потребует значительных затрат времени. Время поиска (ТП) в такой таблице можно оценить как ТП = 0(N). Поскольку именно поиск в таблице идентификаторов является наиболее часто выполняемой компилятором операцией, такой способ организации таблиц идентификаторов является неэффективным. Он применим только для самых простых компиляторов, работающих с небольшими программами. Поиск может быть выполнен более эффективно, если элементы таблицы отсортированы (упорядочены) естественным образом. Поскольку поиск осуществляется по имени, наиболее естественным решением будет расположить элементы таблицы в прямом или обратном алфавитном порядке. Эффективным методом поиска в упорядоченном списке из N элементов является бинарный, или логарифмический; поиск. Алгоритм логарифмического поиска заключается в следующем: искомый символ сравнивается с элементом (N + 1)/2 в середине таблицы; если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронумерованных от 1 до (N + 1)/2 - 1, или блок элементов от (N + 1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент того, с которым его сравнили. Затем процесс повторяется над нужным блоком в два раза меньшего размера. Так продолжается до тех пор, пока либо искомый элемент не будет найден, либо алгоритм "не дойдет до очередного блока, содержащего один или два элемента (с которыми можно выполнить прямое сравнение искомого элемента). Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в два раза, максимальное число сравнений равно 1 + log2N. Тогда время поиска элемента в таблице идентификаторов можно оценить как ТП = О(1og2 N). Для сравнения: при N = 128 бинарный поиск требует самое большее 8 сравнений, а поиск в неупорядоченной таблице -- в среднем 64 сравнения. Метод называют "бинарным поиском", поскольку на каждом шаге объем рассматриваемой информации сокращается в два раза, а "логарифмпческим" -- поскольку время, затрачиваемое на поиск нужного элемента в массиве, имеет логарифмическую зависимость от общего количества элементов в нем. Недостатком логарифмического поиска является требование упорядочивания таблицы идентификаторов. Так как массив информации, в котором выполняется поиск, должен быть упорядочен, время его заполнения уже будет зависеть от числа элементов в массиве. Таблица идентификаторов зачастую просматривается компилятором еще до' того, как она заполнена, поэтому требуется, чтобы условие упорядоченности выполнялось на всех этапах обращения к ней. Следовательно, для построения такой таблицы можно пользоваться только алгоритмом прямого упорядоченного включения элементов. Если пользоваться стандартными алгоритмами, применяемыми для организации упорядоченных массивов данных, то среднее время, необходимое на помещение всех элементов в таблицу, можно оценить следующим образом:
ТД= О(N*log2 N) + k*О(N2).
Здесь k -- некоторый коэффициент, отражающий соотношение между временами, затрачиваемыми компьютером на выполнение операции сравнения и операции переноса данных. При организации логарифмического поиска в таблице идентификаторов обеспечивается существенное сокращение времени поиска нужного элемента за счет увеличения времени на помещение нового элемента в таблицу. Поскольку добавление новых элементов в таблицу идентификаторов происходит существенно реже, чем обращение к ним, этот метод следует признать более эффективным, чем метод организации неупорядоченной таблицы. Однако в реальных компиляторах этот метод непосредственно также не используется, поскольку существуют более эффективные методы.
Похожие статьи
-
База данные кеширование денормализация Предлагаемое решение -- скомбинировать некоторые идеи кеширования и денормализации в специальной библиотеке...
-
Нейросетевой метод - Автоматическое построение профилей нормального поведения веб-приложений
Нейросетевой метод обнаружения аномалий рассматривается на примере экспериментальной системы обнаружения аномалий NNID (Neural Network Intrusion...
-
Исходя из контекста решаемой задачи, для сравнительного анализа рассмотренных математических моделей обнаружения аномалий можно выбрать следующие...
-
В основе метода EWMA лежит экспоненциальное сглаживание первого порядка [20, 21]: (5.2.1) Где 0<л?1 - константа сглаживания. В роли начального...
-
Начинать следует с определения структуры таблицы, соответствующей предметной области, т. е. с определения полей, которые надо включить в таблицу, типов...
-
Построение модели В данной задаче искомыми неизвестными являются количество полок каждого вида, которые будут произведены в текущем месяце. Таким...
-
Лучевые методы построения оптических эффектов - Моделирование эффектов
Для решения задач построения оптических эффектов: тени, отражения и преломления, - применяются методы прямой и обратной трассировки лучей. Отмечают...
-
Расчет таблицы - Программа построения равновесных стратегий для игры
В ходе разработки программы, для эффективной работы основного алгоритма программы будет понадобилось рассчитать некоторые предрасчетные данные. Для этого...
-
Таким образом, с точки зрения описываемого метода, возможны два класса аномалий: - Аномалии, связанные с обнаружением недопустимых операций. - Аномалии,...
-
Описание метода - Автоматическое построение профилей нормального поведения веб-приложений
В основе метода лежит идея анализа связей между наборами параметров, поступающих в веб-приложение через HTTP-запросы, и операциями над объектами...
-
В данном разделе описывается предлагаемый метод обнаружения уязвимостей веб-приложений на основе контроля поведения веб-приложения. Применение метода Как...
-
Существует несколько способов построения опорного плана. Это метод северо-западного угла, метод наименьшей стоимости, приближенный метод Фогеля. Суть...
-
Построение схемы формирования структурного решения - Методы анализа объектов и решений
Управление данные информационный структурный Структурное решение может приниматься в рамках одного структурного фрагмента информационной модели (модуля),...
-
Понятие KPI "Ключевые показатели эффективности (англ. Key Performance Indicators, KPI) -- показатели деятельности подразделения (предприятия), которые...
-
В данном разделе приводятся описания четырех математических методов обнаружения аномалий. Далее проводится сравнительный анализ и выбирается один метод....
-
Построение диаграмм - Электронные таблицы Excel, оформление документов в текстовом процессоре Word
По данным двух несмежных столбцов "порода овец" и "Средний настриг шерсти" таблицы 1 построила стандартную диаграмму. Диаграммы связаны с теми данными на...
-
Таблицы СУБД Microsoft Access - Разработка информационной системы "Гостиница"
Таблицы - это основной объект базы данных, в котором хранятся все данные, имеющиеся в базе, а также структура базы (поля, их типы, свойства). База данных...
-
МЕТОДОВ МЕТОД СОРТИРОВКИ Пирамидальная сортировка Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность aI, aI+1,...,aK...
-
Описание основных возможностей МКЭ МКЭ представляет собой эффективный метод решения инженерных задач. Область применения метода от анализа напряжений в...
-
Для решения трехмерной задачи упругости с помощью метода конечных элементов были заданы следующие основные параметры: [1]. Количество секций. [2]....
-
Метод цепей Маркова - Автоматическое построение профилей нормального поведения веб-приложений
Определение [26]: Маркова цепь - марковский процесс с дискретным временем, заданный в измеримом пространстве. Стохастический процесс в дискретные моменты...
-
Сеть построена на технологии Fast Ethernet. Кабельные линии представляют собой достаточно сложную конструкцию. Кабель состоит из проводников, заключенных...
-
Необходимо решить систему: Для решения на компьютере примем: , Решая эту систему, получаем в качестве выходных параметров скорости масс, для получения...
-
Формирование области многокритериального выбора вариантов Стоит задача о выборе марки автомобиля с их известными особенностями и характеристиками....
-
Табличный процессор Excel фирмы Microsoft предназначен для ввода, хранения, обработки и выдачи больших объемов, данных в виде, удобном для анализа и...
-
Кодирование по методу Хэмминга - Кодирование информации
Код Хэмминга - систематический код, то есть состоящий из информационных и корректирующих символов, расположенных по строго определенной системе, имеющих...
-
Компьютерные преступления - это предусмотренные уголовным кодексом общественно опасные действия, в которых машинная информация является объектом...
-
Выделение текста и рисунков - Текстовый редактор Word, электронная таблица Excel
Для выделения текста и рисунков, включая элементы, не расположенные в непосредственной близости друг от друга, можно использовать как мышь, так и...
-
Каждая СУБД имеет особенности в представлении структуры таблиц, связей, определении типов данных и т. д. которую необходимо учитывать при проектировании....
-
Постановка задачи Постановка практической задачи ЛП включает следующие основные этапы: - определение показателя эффективности, переменных задачи, -...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Алгоритм для определения силы комбинации - Программа построения равновесных стратегий для игры
В играх типа Omaha для определения силы комбинации необходимо учитывать 9 карт: 4 стартовых карты игрока и 5 общих карт. По стандартным правилам покера...
-
Любой объект можно связать с набором процедур, исполняемых в строго определенные моменты. Процедура ( Procedure ) - это группа операторов языка....
-
Стратегии - Программа построения равновесных стратегий для игры
Так как игра случайная, платежная матрица будет состоять из математических ожиданий возможных сочетаний стратегий. Стратегия в данной игре определяет...
-
Моделирование простейшего потока заявок
Цель работы: изучение свойств и характеристик пуассоновского (простейшего) потока. Сравнение теоретических и модельных значений полученных характеристик....
-
Описание классов и методов - Обзор проблематики и теоретических основ электронного документооборота
В данной работе реализован один публичный класс Form1, в котором и происходит основной функционал программы, посредством выполнения методов по кнопкам....
-
Создание запроса на создание таблицы - Информационные технологии в профессиональной деятельности
Запрос на создание таблицы используется, если необходимо скопировать данные, содержащиеся в таблице, или создать архив этих данных. Запрос на создание...
-
Система мониторинга социальных сетей предоставляет исследователю возможность собрать интересующие его упоминания в социальных сетях по какой-либо...
-
Онлайн исследования в социологии: новые методы анализа данных - Распространение новостной информации
На сегодняшний день анализ социальных сетей и медиа, Интернет-сообществ, пользователей в целом используется в основном в маркетинге. Компания может...
-
Метод Гаусса. Метод Гаусса решения систем линейных уравнений состоит в последовательном исключении неизвестных и описывается следующей процедурой. С...
Простейшие методы построения таблиц идентификаторов - Хеш-функция