Предмет, основные понятия

Repeat

Begin

Begin

Begin

Begin

Begin

Лекция 19. Перемешанные таблицы

Begin

notfound:=true;

p:=T;

while (p<>nil) and (notfound) do begin

if p^.key=k then notfound:=false;

p:=p^.next;

end;

end;

Параметр T в этом случае не нужно делать параметром-переменной, поскольку он является только указателем на начало таблицы, а сама таблица лежит в динамической памяти. Вместо номера найденного элемента будем возвращать пользователю нашей процедуры указатель на него (если поиск был удачным) или nil, если поиск неудачен.

Сокращать число проверок в цикле с помощью барьера было бы неразумно: каждый раз барьер придётся ставить в «хвост» списка, а для этого нужно сначала обойти весь список, начиная с головы, затрачивая при этом много времени.

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

Позволим данным располагаться в любых элементах массива, а не только в первых n. Чтобы отличать пустые элементы от занятых нам понадобится специальное значение ключа, которое мы будем заносить в ключевое поле всех пустых ячеек. Если ключ — число, а все полезные ключи положительны, то можно в качестве ключа пустой ячейки использовать 0, если ключи — строки, содержащие фамилии, то ключом пустой ячейки можно сделать пустую строку и т. п. Пусть в ключами являются строки, тогда для таблицы потребуются такие объявления:

const empty = '';

nmax = 1000;

type tKey = string;

tData = .....;

tItem = record

key: tKey;

data: tData;

end;

tTable = array[0..nmax-1] of tItem;

Перед тем как помещать данные в массив заполним ключевые поля всех его элементов «пустыми» значениями. Заносить в таблицу будем не все данные сразу, а один за другим, по очереди. Для того, чтобы определить номер ячейки массива, в которую нужно поместить добавляемый элемент данных, напишем функцию, значение которой зависит только от ключа добавляемого элемента. В такой ситуации поиск можно будет осуществлять довольно просто: находим значение функции на искомом ключе, и смотрим на элемент массива с полученным номером. Если ключ элемента равен искомому ключу, мы нашли то, что искали, иначе — поиск оказался неудачным.

Реализованная описанным способом таблица называется перемешанной (или hash-таблицей), а функция — функцией расстановки ключей (hash-функцией). Такие названия связаны с тем, что данные беспорядочно разбросаны по массиву.

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

function hash(key: tKey): integer;

var i: integer;

sum:=0;

for i:=1 to length(key) do sum:=sum+ord(key[i]);

hash := sum mod nmax;

end;

Процедура добавления элемента в таблицу в предварительном варианте будет выглядеть так:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

h:=hash(item.key);

t[h]:=item.key;

end;

У написанной процедуры есть один существенный недостаток: если элемент, номер которого указала нам хэш-функция был занят, то новые данные будут записаны на место старых, а старые бесследно исчезнут. Чтобы решить эту проблему будем пытаться найти какой-либо другой свободный элемент для добавляемых данных. Здесь понадобится ещё одна функция (вторичная хэш-функция), которая по номеру занятого элемента и по значению ключа добавляемых данных укажет номер другой ячейки, если и там будет занято, вызовем вторичную функцию ещё раз, и т. д. до тех пор пока свободная ячейка не найдется.

Наиболее простая хэш-функция будет добавлять к номеру занятой ячейки какое-нибудь постоянное число:

const HC = 7;

function hash2(n: integer, key: tKey): integer;

hash2 := (n + HC) mod nmax;

end;

Остаток от деления на nmax понадобилось вычислять по той же причине, что и в первичной хэш-функции.

Сейчас можно написать окончательный вариант процедуры добавления элемента данных в таблицу:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

h:=hash(item.key);

while t[h].key<>empty do h:=hash2(h,item.key);

t[h].key:=item.key;

t[h].data:=item.data;

end;

Пусть в хэш-таблицу занесены все необходимые данные и требуется отыскать данные с некоторым ключом. Для этого будем действовать по такой схеме: вычисляем значение хэш-функции на данном ключе, если ячейка с полученным номером свободна, то элемент не найден, если занята, то сравниваем её ключ с искомым. В случае совпадения мы нашли нужный элемент, иначе — находим значение вторичной функции и смотрим на ключ в ячейке с полученным номером. Если он равен «пустому» значению, то поиск неудачен, если равен искомому ключу — то удачен, иначе — вновь находим значение вторичной хэш функции и т. д. На Паскале всё это выглядит так:

constnotfound = -1;

continue = -2;

procedure Search(var t: tTable; key: tKey; var index: integer);

var h: integer;

h:=hash(key);

index:=continue;

if t[h].key = key then index:=h

else if t[h].key = empty then index:= notfound

else h:=hash2(h,key);

until index<>сontinue;

end;

Процедура выдаёт ответ о результатах поиска через параметр-переменную index. При удачном поиске там будет лежать номер найденного элемента, при неудачном — константа notfound. Константа continue означает «пока не найден» и используется только внутри процедуры. При поиске сначала вычисляется значение первичной хэш-функции, а в index заносится значение continue Затем выполняется проверка на равенство ключей, если оно выполняется, то ячейка массива найдена, и мы записываем её номер в index, иначе, если ячейка пуста, то элемент не найден (в index записываем notfound), в третьем случае находим значение вторичной функции. Эти действия продолжаются до тех пор, пока index не перестанет быть равным continue.

Идея использования программного управления для построения устройства, автоматически выполняющего арифметические вычисления, была впервые высказана английским математиком Ч.Бэббиджем еще в 1833г. Однако его попытки построить механическое вычислительное устройство с программным управлением не увенчались успехом.

Первой работающей универсальной автоматически управляемой ВМ считается расчетно-механическая машина "Марк - 1" ( США, 1944г. ). Простои машины составляли большую часть времени. Столь же низкая производительность оказалась и у машины "Марк - 2", построенной на реле улучшенной конструкции.

Проект первой ЭВМ ЭНИАК был разработан Дж.Моучли (США, 1942г.); в 1946г машина вступила в строй. В этой машине 18.000 электрических ламп, 1500 электромеханических реле. Применение ламп повысило скорость выполнения операций в 1000 раз по сравнению с устройством "Марк - 1".

За точку отсчета эры ЭВМ принимают сеансы опытной эксплуатации машины ЭНИАК, которые начались в Пенсильванском университете в 1946г.

Приведем еще некоторые технические характеристики этой ЭВМ : общий вес – 30т, производительность - 5000 операций в секунду. Спустя 40 лет после пуска первой ЭВМ ежегодное производство компонентов ВТ оценивалось к 1985г. в 10¹⁴ активных логических элементов ( active elements groups ), что эквивалентно 1 ЭНИАК на каждого жителя земли. Для сравнения: за 500 лет развития книгопечатания к 1962г. общий тираж всех изданий достиг уровня 2 книги на каждого жителя Земли.

Электронные лампы стали элементной базой ВМ первого поколения. Основная схема – симметричный триггер был создан в 1918г. советским ученым Бонч-Бруевичем М.А. В 1919г. аналогичная схема была разработана также американскими учеными Икклзом и Джорданом.

Первые проекты отечественных ЭВМ были предложены С.А. Лебедевым, Б.И. Рамеевым в 1948г. В 1949-51гг. по проекту С.А. Лебедева была построена МЭСМ ( малая электронно-счетная машина ). К ЭВМ 1-го поколения относится и БЭСМ-1 (большая электронно-счетная машина ), разработка которой под руководством С.А. Лебедева была закончена в 1952г., она содержала 5 тыс. ламп, работала без сбоев в течение 10 часов. Быстродействие достигало 10 тыс. операций в секунду. Почти одновременно проектировалась ЭВМ "Стрела" под руководством Ю.Я. Базилевского, в 1953г. она была запущена в производство. Позже появилась ЭВМ "Урал - 1", положившая начало большой серии машин "Урал", разработанных и внедренных в производство под руководством Б.И. Рамеева. В 1958г. запущена в серийное производство ЭВМ первого поколения М – 20 (быстродействие до 20 тыс. операций/с ).

С появлением транзисторов в середине 50-х годов на смену первого поколения ЭВМ пришли ЭВМ 2-го поколения, построенные на полупроводниковых приборах.

В нашей стране были созданы полупроводниковые ЭВМ разных назначений: малые ЭВМ серий "Наири" и "Мир", средние ЭВМ со скоростью работы 5-30 тыс. операций/с – "Минск - 22" и "Минск – 32, "Раздан – 2", "Раздан – 3", БЭСМ – 4, М – 220 и лучшая из машин второго поколения – БЭСМ – 6 со скоростью работы до 1 млн. опер/с.

В начале 60-х годов возникло новое направление в электронике – интегральная электроника. Использование интегральных схем для построения ЭВМ стало революцией в ВТ и способствовало появлению машин 3-го поколения.

С 1972г. начался выпуск моделей первой очереди ЕС ЭВМ (совместно с социалистическими странами ). Ряд – 1 : ЕС – 1010, 1020, 1022, 1030, 1033, 1040, 1050, 1052. Вторая очередь ( Ряд - 2 ) : ЕС – 1015, 1025, 1035, 1045, 1055, 1060, 1065 имела более современную схемотехническую, конструкторско-технологическую базу, за счет чего у них увеличилась производительность, и расширились функциональные возможности.

Одна из характерных особенностей ЭВМ 4-го поколения - переход от интегральных функциональных схем к интегральным подсистемам ЭВМ. Подсчитано, что внедрение БИС увеличивает надежность не менее чем в 10 раз. Из отечественных ЭВМ к машинам 4-го поколения, прежде всего, относятся машины семейства "Эльбрус".

Таблица 1.1 показывает связь между основными параметрами схемотехники и поколениями ЭВМ. Быстродействие характеризуется задержкой распространения сигнала, вносимой одним элементарным элементом (конъюнктором, дизъюнктором и т. д.). Важный показатель – плотность упаковки, количество единиц элементов, приходящихся на 1см³.

Спустя 30 лет индустрия ЭВМ проходит, как видно из рис. 1.1 стомиллиардный по общему финансовому весу, рубеж и все еще сохраняет наиболее высокие темпы роста объема продаж среди всех отраслей обрабатывающей промышленности США.