Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

ПРОЦЕССОР i8086

Самый простой способ поиска – последовательный. Он может применяться к неупорядоченным файлам. Этот способ можно использовать для данных, размещённых как в массиве, так и в списке. Пусть 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 раз хуже, чем число сравнений при оптимальном расположении записей.

Рассмотренный способ уменьшает вычислительную сложность удачного поиска, но никак не влияет на сложность неудачного поиска. Способ, уменьшающий сложность неудачного поиска, состоит в следующем. Отсортируем все записи файла по возрастанию (или убыванию) значений. В этом случае неудачный поиск прекратится, как только встретится запись с ключом, большим (или меньшим) искомого. Средняя вычислительная сложность поиска равна

Очевидно, что она меньше, чем для неупорядоченного файла. Заметим, что сложность удачного поиска остается такой же, как и для неупорядоченного, причём её нельзя сократить, так как не удаётся использовать идею самоорганизующегося файла.

ПРОЦЕССОР i8086

В 1976 году фирма Intel начала усиленно работать над микропроцессором i8086. Размер его регистров был увеличен в два раза, что дало возможность увеличить производительность в 10 раз по сравнению с 8080. Кроме того, размер информационных шин был увеличен до 16 разрядов, что дало возможность увеличить скорость передачи информации на микропроцессор и с него в два раза. Размер его адресной шины также был существенно увеличен - до 20 бит. Это позволило 86-му прямо контролировать 1М оперативной памяти. Как прямой потомок i8080, i8086 унаследовал большую часть множества его команд. Регистры этого процессора были разработаны таким образом, что они могли обрабатывать как 16-ти битные значения, так и 8-ми битные - также как это делал i8080. Память i8086 была также доработана специальным образом. Весь мегабайт оперативной памяти не представлялся единым полем, а был разделен на 16 сегментов величиной по 64К. Таким образом, память 8086 можно было представить, как объединенную вместе память нескольких i8080. i8086 работал с каждым сегментом по отдельности, не позволяя большим информационным структурам переходить через границы сегментов. В некотором смысле i8086 опередил свое время. Малые компьютеры основывались на 8-ми битной архитектуре, память была очень дорога, требовались дополнительные 16-ти битные микросхемы. Использование этого процессора предполагалось в 16-ти битных устройствах, которые не оправдывали свою цену в то время.