Устройство двоичного поиска в асинхронной памяти

Полезная модель относится к области кодирования, декодирования или преобразования кода и может применяться для быстрого поиска искомого числа в одномерном массиве чисел, упорядоченном по возрастанию (либо по убыванию) и размещенном в асинхронном запоминающем устройстве. Технический результат полезной модели - ускорение процедуры поиска значений в одномерных массивах большого объема, упорядоченных по возрастанию (либо по убыванию) и размещенных в асинхронной памяти. Достигается следующим образом. Асинхронная память 1 имеет вход адреса, с которым соединен выход сумматора с делением пополам 6, и выход данных, который соединен с входным сигналом «В» компаратора 3. С входным сигналом «А» компаратора 3 соединен выход регистра фиксации искомого слова 2, предназначенного для хранения искомого слова, запоминаемого с входной шины искомого слова 9 по входному сигналу запуска поиска 10. Устройство имеет два регистра 4 и 5, предназначенных для хранения адресов соответственно нижней и верхней границы текущего диапазона поиска. Выходы этих регистров соединены с входами сумматора с делением пополам 6, предназначенного для вычисления адреса, подаваемого на асинхронную память 1, по значениям этих регистров. Ко входам регистров 4 и 5 подключены соответственно выход сумматора с константой плюс один 8 и выход сумматора с константой минус один 7. С входами разрешения записи регистров 4 и 5 соединены соответственно выходные сигналы «А>В» и «А<В» компаратора 3. Выходами устройства двоичного поиска в асинхронной памяти являются выходная шина адреса 12, предназначенная для выдачи адреса найденного искомого слова в асинхронной памяти 1, и выходной сигнал результативности поиска 13, предназначенный для выдачи сообщения о том, было ли искомое слово найдено в асинхронной памяти 1.

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

При поиске числа в произвольном одномерном массиве, как правило, используется алгоритм последовательного (линейного) поиска, сводящийся к перебору всех элементов массива, осуществляемому до тех пор, пока либо не будет найдено искомое число, либо не будут исчерпаны все элементы массива. Основным недостатком такого метода при всей его простоте является необходимость затрачивать на поиск значительное время, поскольку требуется перебор всех элементов массива. Это особенно ощутимо, если размер такого массива достаточно велик.

В случае, когда исходный одномерный массив чисел упорядочен по возрастанию (либо по убыванию), допустимо использовать алгоритм двоичного поиска (бинарный поиск; поиск с делением пополам), заключающийся в следующем [1]. Массив делится на две части, после чего выясняется, в какой части находится искомое число (так как массив данных отсортирован, то всегда можно сказать, по какую сторону находится искомый элемент по отношению к любому другому). При этом осуществлять поиск в противоположной половине больше не будет необходимости. Часть массива, где находится искомое число, опять делится на две части, снова выясняется, в какой из них находится искомое число, и так далее до тех пор, пока либо искомое число не будет найдено, либо не будет установлено, что оно отсутствует в исходном массиве.

Максимальное время двоичного поиска зависит от числа элементов массива следующим образом:

где N - число элементов массива, [x] - функция «целая часть x», a T_N - число циклов поиска в массиве из N элементов. Например, при двоичном поиске в массиве из 32767 элементов требуется не более 15 циклов поиска, тогда как при последовательном поиске на это может потребоваться до 32767 циклов.

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

Поставленная задача решается следующим образом.

Устройство двоичного поиска в асинхронной памяти содержит асинхронную память объемом N слов, упорядоченных по возрастанию, регистр фиксации искомого слова, компаратор, первый регистр адреса, второй регистр адреса, сумматор с делением пополам, сумматор с константой минус один, сумматор с константой плюс один, входную шину искомого слова, входной сигнал запуска поиска, входной тактовый сигнал, выходную шину адреса и выходной сигнал результативности поиска, при этом входная шина искомого слова соединена с входом данных регистра фиксации искомого слова, первый вход компаратора соединен с выходом регистра фиксации искомого слова, а второй вход - с выходом данных асинхронной памяти, выход компаратора «А=В» соединен с выходным сигналом результативности поиска, выход компаратора «А<В» соединен с входом разрешения записи второго регистра адреса, выход компаратора «А>В» соединен с входом разрешения записи первого регистра адреса, входной сигнал запуска поиска соединен с входом разрешения записи регистра фиксации искомого слова, входным сигналом сброса в 0 первого регистра адреса и входным сигналом сброса в N-1 второго регистра адреса, входной тактовый сигнал соединен с тактовым входом регистра фиксации искомого слова, тактовым входом первого регистра адреса и тактовым входом второго регистра адреса, выход первого регистра адреса соединен с первым входом сумматора с делением пополам, выход второго регистра

адреса соединен с вторым входом сумматора с делением пополам, выход сумматора с делением пополам соединен с входами сумматора с константой минус один и сумматора с константой плюс один, с входом адреса асинхронной памяти и выходной шиной адреса устройства, выход сумматора с константой минус один соединен с входом данных второго регистра адреса, а выход сумматора с константой плюс один соединен с входом данных первого регистра адреса.

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

На чертеже изображена структурная схема устройства двоичного поиска в асинхронной памяти. Символом «+1» обозначен сумматор с константой плюс один; символом «-1» обозначен сумматор с константой минус один без перехода через ноль (то есть в случае, если результат суммирования отрицательный, сумматор возвращает ноль); символом «/2» обозначен сумматор с делением пополам, осуществляющий вычисление по формуле:

где А, В - исходные суммируемые числа, [x] - функция «целая часть x», а С - результат.

На чертеже приняты следующие обозначения:

1 - асинхронная память объемом N слов, упорядоченных по возрастанию;

2 - регистр фиксации искомого слова, предназначенный для хранения искомого слова на протяжении всей процедуры поиска;

3 - компаратор, сравнивающий два входных сигнала «А» и «В» и возвращающий три выходных сигнала: «А<В», «А>В» и «А=В»;

4 - первый регистр адреса, предназначенный для хранения нижней границы текущего диапазона поиска;

5 - второй регистр адреса, предназначенный для хранения верхней границы

текущего диапазона поиска;

6 - сумматор с делением пополам, предназначенный для вычисления адреса середины текущего диапазона поиска;

7 - сумматор с константой минус один без перехода через ноль, предназначенный для вычисления адреса верхней границы нового диапазона поиска;

8 - сумматор с константой плюс один, предназначенный для вычисления адреса нижней границы нового диапазона поиска;

9 - входная шина искомого слова;

10 - входной сигнал запуска поиска;

11 - входной тактовый сигнал;

12 - выходная шина адреса, предназначенная для выдачи адреса найденного искомого слова в асинхронной памяти 1;

13 - выходной сигнал результативности поиска, предназначенный для выдачи сообщения о том, было ли искомое слово найдено в асинхронной памяти 1.

Асинхронная память 1 имеет вход адреса, с которым соединен выход сумматора с делением пополам 6, и выход данных, который соединен с входным сигналом «В» компаратора 3. С входным сигналом «А» компаратора 3 соединен выход регистра фиксации искомого слова 2, предназначенного для хранения искомого слова, запоминаемого с входной шины искомого слова 9 по входному сигналу запуска поиска 10.

Устройство имеет два регистра 4 и 5, предназначенных для хранения адресов соответственно нижней и верхней границы текущего диапазона поиска. Выходы этих регистров соединены с входами сумматора с делением пополам 6, предназначенного для вычисления адреса, подаваемого на асинхронную память 1, по значениям этих регистров. Ко входам регистров 4 и 5 подключены соответственно выход сумматора с константой плюс один 8 и выход сумматора с константой минус один 7. С входами разрешения записи регистров

4 и 5 соединены соответственно выходные сигналы «А>В» и «А<В» компаратора 3.

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

Работа устройства происходит следующим образом.

Инициализация нового поиска осуществляется положительным фронтом входного тактового сигнала 11 при высоком уровне входного сигнала запуска поиска 10. При этом в первый регистр адреса 4 записывается значение 0, во второй регистр адреса 5 записывается значение N-1, а значение искомого слова с входной шины искомого слова 9 сохраняется в регистр фиксации искомого слова 2. Таким образом, после этого на выходе сумматора с делением пополам 6 появляется значение N/2, соответствующее середине текущего диапазона поиска.

Дальнейшая работа устройства должна происходить при низком уровне входного сигнала запуска поиска 10. При этом каждый положительный фронт входного тактового сигнала 11 соответствует одному циклу поиска.

После любого изменения хотя бы одного из регистров 4 и 5 на выходе данных асинхронной памяти 1 выставляется новое значение, хранящееся по адресу, предварительному выставленному на входе адреса с помощью сумматора с делением пополам 6. Полученное значение с помощью компаратора 3 сравнивается со значением искомого слова, хранящимся в регистре фиксации искомого слова 2. По результатам сравнения компаратор 3 генерирует три выходных сигнала: «А<В» (в случае, если искомое слово меньше текущего, то есть полученного с выхода данных асинхронной памяти 1), «А>В» (в случае, если искомое слово больше текущего) и «А=В» (в случае, если искомое слово совпадает с текущим). Таким образом, высокий уровень в каждый момент

времени может иметь только один из выходных сигналов компаратора 3.

Сигнал «А=В» подается на выход 13 устройства и не участвует непосредственно в его работе.

Сигнал «А<В» указывает, что искомое слово меньше текущего, и диапазон поиска необходимо сузить вдвое в сторону меньших адресов. Поэтому, если сигнал «А<В» имеет высокий уровень, то по следующему положительному фронту тактового сигнала 11 во второй регистр адреса 5 записывается адрес верхней границы нового диапазона поиска, равный адресу середины текущего диапазона поиска (вычисляется сумматором с делением пополам 6), уменьшенному на 1 (вычисляется сумматором с константой минус один 7). Адрес уменьшается на один, поскольку середину текущего диапазона поиска включать в новый диапазон нет смысла. При этом сумматор с константой минус один 7 не допускает перехода результирующего значения через ноль, поскольку адрес «-1» в дополнительном коде был бы идентичен максимальному адресу, соответствующему разрядности регистров 4 и 5, что привело бы к сбою. (В случае, когда поиск осуществляется в диапазоне адресов, начинающемся выше нулевого адреса, допускается не отслеживать переход через ноль или через начало диапазона поиска.)

Сигнал «А>В» указывает, что искомое слово больше текущего, и диапазон поиска необходимо сузить вдвое в сторону больших адресов. Поэтому, если сигнал «А>В» имеет высокий уровень, то по следующему положительному фронту тактового сигнала 11 в первый регистр адреса 4 записывается адрес нижней границы нового диапазона поиска, равный адресу середины текущего диапазона поиска (вычисляется сумматором с делением пополам 6), увеличенному на 1 (вычисляется сумматором с константой плюс один 8). Адрес увеличивается на один, поскольку середину текущего диапазона поиска включать в новый диапазон нет смысла. При этом допустимо, чтобы сумматор с константой плюс один 8 разрешал переход результирующего значения через верхнюю границу диапазона поиска. (Однако в случае, когда поиск осуществляется

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

Если в итоге искомое слово будет найдено, устройство остановит поиск, так как сигналы «А<В» и «А>В» компаратора 3 больше появляться не будут, из-за чего больше не будут изменять свои значения и регистры 4 и 5, и адрес, по которому искомое слово было найдено в асинхронной памяти 1, зафиксируется на выходной шине адреса 12. При этом выходной сигнал результативности поиска 13 останется в высоком уровне, свидетельствуя этим об успешном завершении поиска.

Если же в итоге искомое слово не будет найдено, устройство остановит поиск, так как значение второго регистра адреса 5 будет на единицу превышать значение первого регистра адреса 4, либо их значения окажутся равными друг другу. Так или иначе, значение на входе адреса асинхронной памяти 1 перестанет изменяться; как следствие, перестанут изменяться и значения выходных сигналов компаратора 3. Поэтому на выходной шине адреса 12 окажется произвольное значение, а выходной сигнал результативности поиска 13 останется в низком уровне, свидетельствуя этим о неуспешном завершении поиска.

Результат поиска на выходах 12 и 13 можно считать достоверным по истечении числа тактов сигнала 11, рассчитанного по формуле (1), не считая такта инициализации, на котором входной сигнал запуска поиска 10 имеет высокий уровень.

Для случая, когда массив данных в асинхронной памяти упорядочен не по возрастанию, а по убыванию, структура устройства отличается от вышеописанной следующим. С входом разрешения записи первого регистра адреса 4 соединяется не выход «А>В» компаратора 3, а его выход «А<В»; с входом

разрешения записи второго регистра адреса 5 соединяется, наоборот, не выход «А<В» компаратора 3, а его выход «А>В».

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

СПИСОК ИСТОЧНИКОВ

1. Энциклопедия Turbo Pascal. - http://www.cyberguru.ru/programming/pascal/turbopascal-encyclopaedia-page 19.html.

Устройство двоичного поиска в асинхронной памяти, отличающееся тем, что в него введены асинхронная память объемом N слов, упорядоченных по возрастанию, регистр фиксации искомого слова, компаратор, первый регистр адреса, второй регистр адреса, сумматор с делением пополам, сумматор с константой минус один, сумматор с константой плюс один, входная шина искомого слова, входной сигнал запуска поиска, входной тактовый сигнал, выходная шина адреса и выходной сигнал результативности поиска, при этом входная шина искомого слова соединена с входом данных регистра фиксации искомого слова, первый вход компаратора соединен с выходом регистра фиксации искомого слова, а второй вход - с выходом данных асинхронной памяти, выход компаратора «А=В» соединен с выходным сигналом результативности поиска, выход компаратора «А<В» соединен с входом разрешения записи второго регистра адреса, выход компаратора «А>В» соединен с входом разрешения записи первого регистра адреса, входной сигнал запуска поиска соединен с входом разрешения записи регистра фиксации искомого слова, входным сигналом сброса в 0 первого регистра адреса и входным сигналом сброса в N-1 второго регистра адреса, входной тактовый сигнал соединен с тактовым входом регистра фиксации искомого слова, тактовым входом первого регистра адреса и тактовым входом второго регистра адреса, выход первого регистра адреса соединен с первым входом сумматора с делением пополам, выход второго регистра адреса соединен с вторым входом сумматора с делением пополам, выход сумматора с делением пополам соединен с входами сумматора с константой минус один и сумматора с константой плюс один, с входом адреса асинхронной памяти и выходной шиной адреса устройства, выход сумматора с константой минус один соединен с входом данных второго регистра адреса, а выход сумматора с константой плюс один соединен с входом данных первого регистра адреса.