Сборник по задачам и примерам Assembler


Поиск в таблице - часть 10


mov Ы , buf .bufjn sub Ы. 97 inc [bx] loop ml

:выводим результат подсчета на экран push ds popes

xor al ,al

lea di ,buf

mov ex.type bufjah rep stosb ; чистим буфер buf

mov ex.26 :синвол в buf.buf_1n

lea dx.buf

mcv Ы,97 m2: push bx

mov buf .bufjn.bi :опять вычисляем хэш-функцию:

А»С*1-97 и преобразуем "количество" в символьный вид

sub Ы. 97

mov al .[bx]

aam

or ax,03030h ;в ах длина в символьном виде

mov buf.len in.al —

mov buf.len_buf.ah ;теперь выводим:

mov ah, 09h

int 21h pop bx

inc Ы

loop m2

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

Перечислим области, где методы хэширования оказываются особенно эффективными.

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



  • Начало  Назад  Вперед



    Книжный магазин