Обработка таблицы

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

При обработке таблиц нас главным образом интересуют среднее время проверки (Ге), средняя длина поиска (SL) и среднее время поиска (Ts).

Те — среднее время, требующееся для того, чтобы извлечь элемент из таблицы и сравнить его ключ с заданным. SL — среднее число элементов таблицы, проверенных до обнаружения совпадения ключей. Ts — среднее время, требующееся для того, чтобы найти элемент с заданным ключом.. В качестве грубой аппроксимации можно принять его равным средней длине поиска, умноженной на среднее время проверки, Ts=SLxTe. На практике наиболее важно среднее время поиска. Наиболее простой и быстрый способ построения таблицы состоит в размещении в ней элементов в том порядке, в котором они накапливаются. Ключи и связанная информация (или соответствующие указатели) размещаются в последовательных ячейках таблицы, начиная с ее начала. Если таблица строится таким способом, очень маловероятно, что элементы ее упорядочены в соответствии с их ключами, и, для того чтобы найти элемент с заданным ключом, необходимо просмотреть всю таблицу.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Обработка таблицы Основная проблема при обработке таблиц заключается в минимизации времени доступа, т. е. подходящим образом взвешенного среднего времени, затрачиваемого на размещение нового элемента в таблице или на нахождение в ней существующего (или на доказательство отсутствия элемента с заданным ключом). Весовые множители, зависят от того, насколько часто таблица пополняется новыми элементами и насколько часто она используется только для поиска существующей информации. При обработке таблиц нас главным образом интересуют среднее время проверки (Ге), средняя длина поиска (SL) и среднее время поиска (Ts). Те — среднее время, требующееся для того, чтобы извлечь элемент из таблицы и сравнить его ключ с заданным. SL — среднее число элементов таблицы, проверенных до обнаружения совпадения ключей. Ts — среднее время, требующееся для того, чтобы найти элемент с заданным ключом.. В качестве грубой аппроксимации можно принять его равным средней длине поиска, умноженной на среднее время проверки, Ts=SLxTe. На практике наиболее важно среднее время поиска. Наиболее простой и быстрый способ построения таблицы состоит в размещении в ней элементов в том порядке, в котором они накапливаются. Ключи и связанная информация (или соответствующие указатели) размещаются в последовательных ячейках таблицы, начиная с ее начала. Если таблица строится таким способом, очень маловероятно, что элементы ее упорядочены в соответствии с их ключами, и, для того чтобы найти элемент с заданным ключом, необходимо просмотреть всю таблицу.