Читайте также:
|
Самый простой способ поиска – последовательный. Он может применяться к неупорядоченным файлам. Этот способ можно использовать для данных, размещённых как в массиве, так и в списке. Пусть key – аргумент поиска, то есть тот ключ, по которому ищется запись. Необходимо найти наименьшее такое i, для которого k (i) = key, если такое i существует. С этой целью просматриваются последовательно все k (i), i = 1,.., n, и сравниваются с key до первого совпадения. Для оптимизации количества операций сравнения можно использовать механизм барьера (см. раздел 3.2.1).
Оценим число сравнений, которое необходимо сделать при последовательном поиске, чтобы найти запись с указанным ключом. Предположим, что все ключи встречаются с равной вероятностью. Тогда, очевидно, среднее число сравнений при удачном поиске равно
а число сравнений при неудачном поиске всегда равно n. Таким образом, время поиска оценивается величиной O (n).
Рассмотрим два способа организации файла, позволяющих уменьшить вычислительную сложность поиска. Первый из них (он был впервые предложен У.Э.Смитом) заключается в переупорядочивании записей файла. Записи, которые ищутся чаще, должны располагаться ближе к началу файла.
Пусть
p i – вероятность того, что ищется запись k (i), i = 1, 2, …, n;
q 0 – вероятность того, что ищется запись с ключом key < k (1);
qi – вероятность того, что ищется запись с ключом k (i) < key < k (i +1), i = 1, 2, …, n –1;
qn – вероятность того, что ищется запись с ключом k (n) < key.
Тогда среднее число сравнений при поиске равно
Допустим, есть возможность размещать записи в файл в любом порядке. Тогда, чтобы минимизировать эту величину, надо наиболее часто используемые записи расположить в начале файла. То есть необходимо, чтобы p 1 ≥ p 2 ≥ … ≥ pn.
Рассмотрим, например, закон Зипфа:
Это распределение получило известность благодаря Дж.К. Зипфу. Он заметил, что i -ое наиболее употребительное в тексте на естественном английском языке слово встречается с частотой, приблизительно обратно пропорциональной i. В этом случае среднее число сравнений при удачном поиске в упорядоченном по вероятности файлу равно n/Hn, то есть O(n/ln(n)). Это примерно в ln(n)/2 раз меньше, чем для неупорядоченного файла.
К сожалению, в большинстве случаев распределение вероятностей не известно. Кроме того, вероятности выборки различных записей могут измениться с течением времени. Естественно, хотелось бы иметь алгоритм, который динамически переупорядочивал бы файл.
Существуют различные методы динамического переупорядочивания. Можно, например, в каждой записи завести счетчик числа обращений, чтобы на основании значений счетчиков переупорядочивать записи. Ясно, что после продолжительной работы записи расположатся в соответствии с истинным распределением. Однако не всегда желательно отводить память под
счетчики, так как можно использовать адаптивные методы. Эти методы перестраивают файл всякий раз, когда происходят изменения в нём.
Другой подход к динамическому переупорядочиванию приводит к так называемому "самоорганизующемуся файлу", предложенному Дж. Мак-Кейбом. Идея состоит в том, чтобы просматриваемую запись переместить в позицию, более близкую к началу файла, и представляет практический интерес, только если число операций, необходимых для продвижения элемента, невелика. В связи с этим используются лишь немногие простые методы продвижения:
запись помещается в начало файла;
запись меняется местами с записью, непосредственно предшествующей ей.
Если каждый поиск совершается независимо от предыдущих, то можно показать, что среднее число сравнений при удачном поиске в таком самоорганизующемся файле в пределе стремится к значению
Если, i = 1, 2, …, n, то самоорганизующийся файл всегда находится в случайном порядке и среднее число сравнений равно (n+1)/2, как и для неупорядоченного файла. Если же распределение подчиняется закону Зипфа, то среднее число сравнений равно (nln4/ln(n))
При достаточно больших n это лучше, чем n /2, и лишь в ln4 раз хуже, чем число сравнений при оптимальном расположении записей.
Рассмотренный способ уменьшает вычислительную сложность удачного поиска, но никак не влияет на сложность неудачного поиска. Способ, уменьшающий сложность неудачного поиска, состоит в следующем. Отсортируем все записи файла по возрастанию (или убыванию) значений. В этом случае неудачный поиск прекратится, как только встретится запись с ключом, большим (или меньшим) искомого. Средняя вычислительная сложность поиска равна
Очевидно, что она меньше, чем для неупорядоченного файла. Заметим, что сложность удачного поиска остается такой же, как и для неупорядоченного, причём её нельзя сократить, так как не удаётся использовать идею самоорганизующегося файла.
Дата добавления: 2014-12-20; просмотров: 30 | Поможем написать вашу работу | Нарушение авторских прав |