Методы представления данных в памяти ЭВМ при программировании по Р-технологии

• Автор: Нетесин, Игорь Евгеньевич
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 102 c. : ил

ГЛАВА I. ВОПРОСЫ ЭФФЕКТИВНОГО ПРЕДСТАВЛЕНИЯ СТРУКТУР

ДАННЫХ

§ I. Совместное размещение в памяти ЭВМ структур

данных

§ 2. Структуры со многими функциями доступа

§ 3. Организация памяти Р-машины

Глава II. МЕТОД С0ШЕСТН0Г0 ПРЕДСТАВЛЕНИЯ СОВОКУПНОСТИ

ХЕШ-ТАБЛИЦ (ТАБЛИЧНАЯ ПАМЯТЬ)

§ I. Исследование основных характеристик - среднего

числа проб при удачном и неудачном поисках . . . . 36 § 2. Сравнение характеристик табличной памяти и

изолированно организованных таблиц

§ 3. Особенности табличной памяти
§ 4. Алгоритм динамического расширения хеш-таблиц
Глава III. РАЗВИТИЕ И ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ
ПРЕДСТАВЛЕНИЯ ДАННЫХ
§ I. Способ построения быстрой стековой таблицы
§ 2. Организация двухуровневой страничной табличной
памяти
§ 3. Опыт использования разработанных методов
в автоматизированной системе производства программ реального времени
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

В настоящее время рост производительности труда программистов неразрывно связан с использованием технологии программирования, эффективность которой во многом определяется принятой в ней организацией данных. В этом плане В.М.Глушков отмечал [30^, что новая технология программирования в отличие от техники традиционного программирования, уделявшей основное внимание собственно программам, а не данным, должна отводить организации последних очень большое, а часто решающее значение. При этом в круг ее вопросов необходимо включать разработку базовых структур данных (СД) и базовых операторов над ними, что связано с задачей стандартизации как СД, так и их машинного представления в различных типах ЭВМ [15, 33, 7б].
Одна из главных проблем, которая возникает в процессе разработки СД, их эффективных представлений и способов обработки, заключается в том, чтобы рационально использовать память для хранения данных, обеспечивая при этом высокую скорость доступа к ним. Наряду с успехами, достигнутыми с помощью последовательного и связного представлений, существенный сдвиг в разрешении этой проблемы произошел благодаря открытию хеш-адресации, большой вклад в развитие которой внесли Л.Н. Королев [55^, А.П.Ершов [44], Р. Моррис [125"], Д.Кнут [52] и ряд других авторов. Основным достоинством хеш-адресации является то, что при ее ис-

пользовании среднее время поиска нужной информации не зависит от общего ее объема. Однако, позволяя значительно ускорить процесс доступа к данным, известные методы хеш-адресации обладают недостатком, обусловленным необходимостью статического задания области, по которой ведется хеширование. В то же время для решения сложных системных и прикладных задач необходимо более гибкое управление памятью, что вызывает потребность в усовершенствовании этих методов.
Названные проблемы определяют важность и актуальность исследований, проводимых в тесной связи с достижениями передовых технологий программирования и направленных на развитие методов организации данных и в первую очередь методов, использующих хеш-адресацию. Поэтому предмет диссертационной работы составляет разработка и анализ новых методов представления СД, в большей своей части основанных на технике хеширования. Прообразом исследуемых СД послужили структуры, являющиеся базовыми в Р-технологии программирования [зз], разработанной под руководством В.М.Глушкова и И.В.Вельбицкого и получившей широкое распространение в нашей стране.
Задачами работы является усовершенствование известных и создание новых методов представления СД переменной длины в целях обеспечения высокой скорости доступа к их содержимому при одновременном рациональном использовании памяти машины.
Методологическую основу работы составляет обобщение опыта практических разработок автора и их анализа, который проводится с привлечением математического аппарата теории функций и теории вероятностей и опирается на достижения в области хеш-адресации и Р-технологии программирования.

чества и порядка их заполнения. Чтобы убедиться в этом,достаточно вновь представить ситуацию с числом небольших таблиц, значительно превышающем число больших. Когда небольшие таблицы заносились в ТП после больших (даже при выполнении условия ос<ос*) изолированная организация лучше, так как Ст будет приближаться к — , при обратной очередности предпочтительнее ТП ( Ст будет стремиться к единице)
В общем случае можно определить вероятности рI обращения к таблицам и рассмотреть величины С*-И /э. с/ и аналогично Ср} £_р. Очевидно, что если в основном обращаться к таблицам Т- , в которых ссг- малы, то изолированная организация эффективнее по скорости при условии, что ТП заполнялась в произвольном порядке. Однако если удается так построить алгоритм, чтобы такие таблицы заносить в ТП вначале, то Ср <&р.
§ 3. Особенности табличной памяти
Совместное размещение хеш-таблиц приводит к качественным изменениям и в связи с этим к новым важным свойствам, принципиально отсутствующим у изолированного представления таблиц.
Эти свойства обусловлены принятой в ТП организацией указателей, при которой все указатели располагаются в общем поле и в каждом из них помимо ссылки на запись присутствует номер таблицы.
Первое. Пробы при поиске не всегда завершаются сравнением ключей. Предварительно проверяются на равенство номер таблицы и номер в указателе и если они не совпадают, то ключи сравнивать уже нет надобности. Оценим долю сравнений при поиске в Г+, когда номер таблицы и номер в указателе совпадают.
Пусть £>1 - случайная величина, принимающая значение числа