Способы поиска адреса числ

Рассмотрим некоторые способы поиска адреса числа X по заданному значению этого числа, полагая при этом, что функциональная зависимость (5.2) не может быть представлена достаточно простым аналитическим выражением. [c.73]

Этот способ поиска известен также под названием способа скользящего начала [69]. При поиске по способу скользящего начала искомые числа предварительно упорядочиваются по возрастанию их величины. Первое число ищется последовательным просмотром списка чисел, хранящихся в машине, а поиск каждого нового числа производится на участке, левой границей которого является адрес последнего найденного числа. Правая граница списка чисел остается неизменной. Такой порядок поиска монотонно возрастающих чисел приводит 1К постепенному сужению области поиска. [c.79]

Словосочетания могут упорядочиваться по различным признакам по длине кодов, по численным значениям кодов, по длине и по численным значениям кодов одновременно и т. д. Для поиска в словаре могут применяться способы, рассмотренные в гл. 5 (способ деления пополам, способ разделителей и др.). Если состав словаря часто изменяется, то наиболее удобным оказывается узловой способ поиска. По этому способу словосочетания, содержащие одинаковые коды слов, объединяются в ассоциативные цепочки. Каждое словосочетание может входить одновременно в несколько ассоциативных цепочек (по числу слов, входящих в его состав), а общее число цепочек определяется количеством разных слов, встречающихся в словаре словосочетаний. В адресной части словаря (см. рис. 5.2) для каждого кода слова указывается адрес его первого вхождения в словосочетание. Обращение к адресной части производится по сверткам кодов слов. В качестве сверток могут быть выбраны, например, п младших разрядов кода слова. [c.94]

Особенно просто определяется адрес числа по его величине, когда функциональная зависимость (5.2) линейна (например, при равноотстоящих значениях чисел х). Однако в информационно-поисковых системах она обычно, нелинейна,, и здесь приходится применять другие способы поиска адреса числа х. [c.73]

Время поиска адреса числа. х способом деления на части зависит от количества / чисел в списке, от величины делителя п, от типа электронной машины, с помощью которой производится поиск, и, наконец, от конкретной программной реализации алгоритма поиска. Его можно приближенпэ оценить количеством циклов по-поиска, причем под ц ii к л о м поиска понимается совокупность арифметическн.ч и логических операций, связанных с проверкой одного из неравенств (5.3). Максимальное количество циклов поиска прн заданных I и п определяется приближенной формулой [c.75]

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

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

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

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