Перемешивание с цепочками переполнения

В методе открытого перемешивания записи переполнения вклю-

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

Таблица перемешивания с цепочками переполнения для примера, показанного на рис. 2.14, изображена на рис. 2.15.

В таблице со случайным перемешиванием и цепочками переполнения средняя длина поиска для случайных равномерно распределенных записей определяется по формуле

D(m,n)=1+(m-1)/2n (2.11)

где n — длина отображающего вектора, а m — длина таблицы.

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

Для рассмотренного выше примера таблицы, показанные на рис.2.15, преобразуются в таблицу, изображенную на рис. 2.16. Преимущество этого метода по сравнению с предыдущим — экономия памяти, а недостаток — меньшая гибкость и более сложный алгоритм заполнения таблицы. Средняя длина поиска здесь также определяется формулой (2.11). Этот метод можно использовать для постоянных таблиц, а также для временных таблиц, заполняемых на одном этапе трансляции, а применяемых на другом.

Для постоянных таблиц наиболее часто требующиеся записи целесообразно записывать первыми, тогда во внутренние цепочки переполнения попадут относительно редко требующиеся записи, что сократит среднюю длину поиска.

Характерно, что при использовании внутренних цепочек переполнения все позиции отображающего вектора могут быть заполнены записями, т. е. m = n, а средняя длина поиска при равномерном случайном распределении записей не превзойдет 1,5. Это непосредственно следует из формулы (2.11).

Таблицы со случайным перемешиванием заполняются относительно просто, не требуют упорядочивания записей и обеспечивают достаточно быстрый поиск, поэтому начиная с середины 50-х годов эти таблицы часто используют в трансляторах.

ФУНКЦИИ РАССТАНОВКИ

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

В литературе [16,35,57] описано несколько методов получения функции расстановки. Одним из простых методов является выделение части цифрового кода ключа. Например, пусть максимальный ожидаемый размер таблицы имен не превосходит 512. Тогда функция расстановки может иметь в качестве значения 9-разрядное двоичное число, поскольку 512 =2⁹.

Можно просто выделить первые 9 разрядов двоичного кода идентификатора или взять какие-либо 9 разрядов из середины кода. Нужно лишь обеспечить возможно большую равномерность распределения значений функции f{k) в интервале (0, 511).

Для улучшения равномерности распределения иногда применяют «складывание» кода идентификатора: первая половина кода складывается со второй и из результата выделяются какие-либо 9 разрядов. Можно также разделить код ключа на куски по 9 разрядов. а затем сложить их по модулю 2⁹.

Последняя модификация имеет некоторое теоретико-вероятностное обоснование: при предположении о статистической независимости складываемых кусков получается распределение, близкое к равномерному. В частности, именно этот вариант «складывания» использовался в Альфа-трансляторе для машины М-20 [16] при вычислении функции расстановки.

В Альфа-трансляторе таблица имен рассчитана на 512 идентификаторов. Функция расстановки вычисляется по формуле

где S— суммирование по модулю 2⁹ с переносом единицы переполнения из старшего разряда в младший, l — длина идентификатора (число букв и цифр), а_i, i=1,...,l — девятиразрядные коды букв и цифр, a a₀ — номер блока Альфа-программы, отсчитываемый от начала программы и равный количеству слов begin, открывающих блоки и предшествующих данному идентификатору. Слагаемое а₀ введено, чтобы избежать одинаковых значений функции расстановки для одинаковых идентификаторов, описанных в разных блоках.

Другой способ получения функции расстановки — деление. Для отображающего вектора длиной n код ключа, рассматриваемый как целое число, делится на величину n—1. Эксперименты показывают, что остаток от деления распределен приблизительно равномерно в интервале (0,n — 2) и может использоваться как значение функции расстановки.

Экспериментальная проверка описанных методов для таблиц с открытым перемешиванием показала, что простое «складывание» кода идентификатора с выделением средней части результата увеличивает среднюю длину поиска по сравнению с теоретической, вычисленной по формуле (2.10), в 4—5 и более раз, средняя длина поиска для метода, использованного в Альфа-трансляторе, приблизительно вдвое больше теоретической, а при делении средняя длина

поиска практически совпадает с теоретической для s £ 0,85.