Поиск и сортировка

Ассоциативная память – это средство для поиска информации по связанному с ними числовому значению ключа. Для поддержки ассоциативной памяти в вычислительных системах назначается регистр MAR.

Регистр MAR – поддерживается на уровне ОС, является некоторой ячейкой ОП. Кроме того некоторые процессоры имеют аппаратную поддержку либо встроенный MAR.

Различия ассоциативной памяти связаны с алгоритмом поиска.

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

Используется 2 простых алгоритма поиска, а также методики освоенные на них:

1. Линейный поиск. Для него требуется таблица, в которой ведется поиск с ассоциированными парами ключ значение.

2. Ключ поиска и данные о количестве записи в таблице.

Алгоритм поиска следующий:

1) Берется ключ к первой записи таблицы и сравнивается с ключом поиска.

2) Если ключи совпали, считывается ассоциированное с ним значение или запись. Поиск окончен.

3) Если ключи не совпали, считывается ключ следующей записи и действия повторяются до тех пор, пока не совпадут ключи или не будет достигнут конец таблицы.

Преимущества: простота алгоритма, нет необходимости в предварительной сортировке данных.

Недостатки: большое время выполнения.

Двоичный поиск.

Для реализации двоичного поиска необходимы упорядоченные, сортированные таблицы данных. Упорядочивание должно производится либо по ключу, если он имеет числовое выражение, либо по индексу записи.

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

Алгоритм двоичного поиска:

1) Оценивается диапазон поля поиска, который на первом шаге равен величине таблицы и считывается индекс из средины таблицы. Считанный индекс сравнивается с индексом ключа поиска.

2) Если совпал, то сравниваются ключи поиска (не обязательно) и считывается ассоциируемое значение.

3) Если считанный индекс больше индекса ключа поиска таблицы, делится пополам и в качестве поля поиска принимается половина таблицы с меньшим индексом, если индекс меньше индекса ключа поиска тоже выполняется для половины таблицы с большими индексами ключей. Действия повторяются до тех пор пока не будет найдена искомая запись либо не останется чего делить.

Преимущества: более быстрый по сравнению с линейным, алгоритм поиска.

Недостаток: более сложен в реализации и требует упорядочивания таблицы.

Дата добавления: 2013-12-12