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

— целочисленная функция, играющая главную роль в методике обработки информации и исключающая сплошной перебор при занесении и поиске информации. Пусть имеется последовательность объектов, при этом каждому объекту соответствует некоторая информация. Для простоты предполагается, что объект и информация изображаются двоичными кодами, помещающимися вместе в одной ячейке памяти ЦВМ. Применение методики Ф. р. целесообразно, когда , где n — максимум числа разных объектов в последовательности, длина кода, изображающего объект. Задача состоит в том, чтобы создать в памяти таблицу объектов с информацией о них, вход в которую производится по коду объекта.

Для составления таблицы используется сначала пустое расстановочное поле длиной в ячеек, заполнение которого производится с помощью произвольной Ф. р. определенной на двоичных кодах длины l и принимающей значения от нуля до . При рассмотрении очередного объекта а делается попытка направить его в ячейку расстановочного поля с номером Если ячейка s пуста, она отводится для хранения объекта а и информации о нем. Если она уже оказалась занятой объектом, тождественным а, это значит, что объект встретился в последовательности повторно. Если ячейка s занята другим объектом, начинают просматриваться ячейки с адресами и т. д. (счет ведется по до тех пор, пока не будет найдена пустая ячейка или ячейка, уже содержащая объект а.

Обычный метод последовательного размещения объектов в таблице, приводящего к сплошному перебору таблицы при поиске, получается при Наиболее эффективен такой выбор Ф. р., при котором ее значения равномерно распределены в диапазоне на случайных последовательностях объектов. В этом случае число тактов, требуемое для размещения объекта, пропорционально при , а при — в среднем ограничено константой, не зависящей от n. В случае двоичной кодировки объектов N обычно берется равным и Ф. р. вычисляется по правилу: двоичный код объекта делится на куски, по длине не превышающие , которые затем складываются друг с другом по Метод Ф. р. реализован при создании алъфа-системы.

Лит.: . А. П. Ершов.