Ключ преобразования адреса

Сортировка и поиск [96, 97] —две, по-видимому, наиболее распространенные операции обработки нечисловых данных наряду с сохранением записей и составлением отчетов. Цель операции сортировки состоит в подборе подлежащих хранению в памяти элементов с тем, чтобы в определенном порядке (восходящем или нисходящем) облегчить некоторые из последующих стадий обработки, например корректировку хранящейся в памяти совокупности данных или выборку их при помощи определенного метода поиска данных. В качестве примера рассмотрим простую встроенную в микрокомпьютер систему поиска данных, содержащую физические характеристики лабораторных реактивов. Аналитику необходимо, чтобы компьютер отыскал данные о растворимости соединения X при О °С. Предположим, что база данных содержит соответствующие сведения о N соединениях, что элементы данных не упорядочены каким-либо способом. Если в данном случае будет осуществляться последовательный поиск, т. е. элементы данных будут проверяться строго в том порядке, в каком они записывались в базу данных, то при каждом запросе об информационном поиске потребуется проверка в среднем (N+l)/2 элементов. Если, однако, элементы данных рассортированы в каком-либо порядке, например по названиям соединений, то возможен более эффективный метод поиска, основанный на дихотомическом поиске [17], который потребует проверки в среднем только FLOOR (log2N) — 1 элементов (FLOOR — наибольщее целое). В принципе если сформулировать подходящий ключ для алгоритма преобразования адреса, то возможно и дальнейщее уменьщение числа искомых элементов данных, что может позволить отыскивать данные прямым путем [96, 17, 18]. [c.386]

Справочник химика 21

Химия и химическая технология