Урок №1
Begin
Var
Type
pDlist = ^TDList;
TDList = record
element:TElementType;
next:pDList;
end;
Данная структура хранит в себе значение элемента и ссылку на следующий элемент. Поле element имеет тип TElementType, этот тип должен быть определен раньше, чем структура TDList, и содержать тип элементов множества. Это могут быть как целые или дробные числа, так и строки или любой другой тип. Поле next имеет тип ссылка на элемент типа TDList. Оно используется для доступа к следующему элементу списка.
Большинство операторов множеств, реализованных как списки, требуют O(N) времени, где N – количество элементов во множестве. Это объясняется необходимостью просматривать в худшем случае последовательно все элементы списка в порядке их следования.
Исключение, например, составляет оператор INSERT для неупорядоченных списков. Его сложность O(1), так как выполняется вставка элемента в начало списка, что не требует просмотра всех его элементов.
§14. Реализация АТД «Словарь». Хеширование.
Применение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы объединения и пересечения. Часто достаточно только хранить в множестве "текущие" объекты с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве.
Абстрактный тип множеств с операторами , и называется (Словарь).
Также, стоит включить оператор в набор операторов словаря — он потребуется при реализации АТД для инициализации структур данных. Рассмотрим реализации, наиболее подходящие для представления таких словарей.
Словари можно представить посредством сортированных или несортированных связанных списков, двоичных векторов или массивов фиксированной длины с указателем на последнюю заполненную ячейку этого массива. Эти реализации уже были рассмотрены в §13.
Существует еще один полезный и широко используемый метод реализации словарей, который называется хешированием. Этот метод требует фиксированного времени (в среднем) на выполнение операторов и снимает ограничение, что множества должны быть подмножествами некоторого конечного универсального множества. В самом худшем случае этот метод для выполнения операторов требует времени, пропорционального размеру множества, так же, как и в случаях реализаций, посредством массивов и списков. Но при тщательной разработке алгоритмов можно добиться, что вероятность выполнения операторов за время, большее фиксированного, будет как угодно малой.
Рассмотрим две различные формы хеширования. Одна из них называется открытым, или внешним хешированием и позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер множеств. Другая называется закрытым, или внутренним хешированием и использует ограниченное пространство для хранения данных, ограничивая, таким образом, размер множеств.
1. Открытое хеширование
На рис. 14.1 показана базовая структура данных при открытом хешировании. Основная идея заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов. Для классов, пронумерованных от до , строится хеш-функция такая, что для любого элемента х исходного множества функция принимает целочисленное значение из интервала , которое, естественно, соответствует классу, которому принадлежит элемент .
Элемент называют ключом, — хеш-значением , а "классы" — сегментами. Будем говорить, что элемент принадлежит сегменту .
Рис. 14.1 Организация данных при открытом хешировании
Массив, называемый таблицей сегментов и проиндексированный номерами сегментов , содержит заголовки для списков. Элемент -ro списка — это элемент исходного множества, для которого .
Если сегменты примерно одинаковы по размеру, то в этом случае списки всех сегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из элементов, тогда средняя длина списков будет элементов. Если можно оценить величину и выбрать как можно ближе к этой величине, то в каждом списке будет один-два элемента. Тогда время выполнения операторов словарей будет малой постоянной величиной, не зависящей от (или, что эквивалентно, от ).
Не всегда ясно, как выбрать хеш-функцию так, чтобы она примерно поровну распределяла элементы исходного множества по всем сегментам. Далее будет показан простой способ построения функции , причем будет "случайным" значением, почти независящим от .
Пример 1. Введем хеш-функцию (которая будет "хорошей", но не "отличной"), определенную на символьных строках. Идея построения этой функции заключается в том, чтобы представить символы в виде целых чисел, используя для этого машинные коды символов.
Пусть каждый ключ x является строкой, состоящей не более, чем из 10 символов. А – множество всех ключей. Тип ключа в Pascal можно определить так
type
nametype=array [1..10] of char
Встроенная функция ord(c) в языке Pascal возвращает целочисленный код символа с. Для любого х∈А зададим хеш-функцию так, что
mod B
– остаток от деления на B суммы целочисленных кодов всех символов строки x.
Например, если x=abc, то h(x)=(ord(a)+ord(b)+ord(c))mod B.
function h ( x: nametype ): 0..B-1;
i, sum: integer;
sum:= 0;
for i:= 1 to 10 do
sum:= sum + ord(x[i]);
h:= sum mod B
end;
2. Закрытое хеширование.
При закрытом хешировании в таблице сегментов хранятся непосредственно элементы словаря, а не заголовки списков. Поэтому в i-ом сегменте может храниться только один элемент словаря x, для которого h(x)=i.
Ситуация, когда при попытке поместить элемент x в сегмент с номером h(x) оказывается, что сегмент занят другим элементом y (x≠y, но h(x)=h(y)) называется коллизией.
Для разрешения коллизий при закрытом хешировании применяется методика повторного хеширования. Выбирается последовательность других номеров сегментов , , ..., куда можно поместить элемент . Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное, куда и помещаетя x. Если свободных сегментов нет, то, следовательно, таблица заполнена и элемент вставить нельзя.
При поиске элемента (например, при выполнении оператора ) необходимо просмотреть все местоположения пока не будет найден или пока не встретится пустой сегмент. Чтобы объяснить, почему можно остановить поиск при достижении пустого сегмента, предположим, что в словаре не допускается удаление элементов. И пусть, для определенности, — первый пустой сегмент. В такой ситуации невозможно нахождение элемента в сегментах и далее, так как при вставке элемент вставляется в первый пустой сегмент, следовательно, он находится где-то до сегмента .
Но если в словаре допускается удаление элементов, то при достижении пустого сегмента мы, не найдя элемента , не можем быть уверенными в том, что его вообще нет в словаре, так как сегмент может стать пустым уже после вставки элемента . Поэтому, чтобы увеличить эффективность данной реализации, необходимо в сегмент, который освободился после операции удаления элемента, поместить специальную метку, которую назовем (удаленный). Важно различать метки и — последняя равна true в сегментах, которые никогда не содержали элементов. При таком подходе (даже при возможности удаления элементов) выполнение оператора не требует просмотра всей хеш-таблицы. Кроме того, при вставке элементов сегменты, со свойством , можно трактовать как свободные, таким образом, пространство, освобожденное после удаления элементов, можно рано или поздно использовать повторно. Но если невозможно непосредственно сразу после удаления элементов пометить освободившееся сегменты, то следует предпочесть закрытому хешированию схему открытого хеширования.
Различные методики разрешения коллизий различаются принципом построения последовательности функций Рассмотрим далее два принципа повторного хеширования.
2.1. Линейное повторное хеширование. Нахождение повторных хеш-значений происходит по формуле
(1)
В частности,
***
Пример 2. Предположим, что и ключи , , и имеют хеш-значения , , и .
Мы предполагаем, что вначале вся хеш-таблица пуста, т.е. в каждом сегменте словаря, свойство Null = true, которое говорит о том, что в сегмент запись не производилась. Теперь последовательно вставим элементы , , и в пустую таблицу: элемент попадет в сегмент 3, элемент — в сегмент 0, а элемент — в сегмент 4. Для элемента , но сегмент 3 уже занят. Применяем функцию : , но сегмент 4 также занят. Далее применяем функцию : , сегмент 5 свободен, помещаем туда элемент . Результат заполнения хештаблицы показан на рис. 14.2.
Рис. 14.2. Частично заполненная хеш-таблица
Пример 3. Предположим, что надо определить, есть ли элемент в множестве, представленном на рис.14.2. Если , то надо проверить сегмент 4. Поскольку там элемента e нет, проверяем сегмент с номером 5 и затем сегмент с номером 6. Сегмент 6 пустой, в предыдущих просмотренных сегментах элемент не найден, следовательно, этого элемента в данном множестве нет.
Допустим, мы удалили элемент и поместили метку в сегмент 4. В этой ситуации для поиска элемента мы начнем с просмотра сегмент , затем просмотрим сегменты с номером и с номером 5 (где и найдем элемент ), при этом мы не останавливаемся на сегменте 4 — хотя он и пустой, но не помечен как .
2.2. «Случайные» методики повторного хеширования
Формула (1) линейного повторного хеширования имеет существенный недостаток. Как только несколько последовательных сегментов будут заполнены (образуя группу), любой новый элемент при попытке вставки в эти сегменты будет вставлен в конец этой группы, увеличивая тем самым длину группы последовательно заполненных сегментов. Другими словами, для поиска пустого сегмента в случае непрерывного расположения заполненных сегментов необходимо просмотреть больше сегментов, чем при случайном распределении заполненных сегментов. Отсюда также следует очевидный вывод, что при непрерывном расположении заполненных сегментов увеличивается время выполнения вставки нового элемента и других операторов.
Фактически любая методика повторного хеширования, где очередная проба зависит только от предыдущей (например, как зависимость от числа предыдущих "неудачных" проб, от исходного значения или от самого элемента ), обнаруживает группирующие свойства линейного хеширования.
Возможна простейшая методика, для которой проблема "группирования" не существует: для этого достаточно положить
,
где — "случайные" перестановки чисел . В частности,
***
Конечно, такой набор чисел должен использоваться при реализации всех операторов, выполняемых над словарями, а "случайное" перемешивание целых чисел должно быть сделано (выбрано) еще при разработке алгоритма хеширования.
Генерация "хороших случайных" чисел — достаточно сложная задача, но, к счастью, существуют сравнительно простые методы получения последовательности "случайных" чисел путем "перемешивания" целых чисел из заданного интервала. При наличии такого генератора случайных чисел можно воспроизводить требуемую последовательность при каждом выполнении операторов, работающих с хеш-таблицей.
.
Тема: Поширення світла. Закони відбивання і заломлення світла.
Мета: 1) познайомити учнів із історією розвитку поглядів на природу світла, сформулювати закони прямолінійного поширення світла, закони відбивання та заломлення;
2) формувати навички побудови зображень поширення світлового променя;
3) розширювати світогляд учнів, пояснюючи природні явища, що пояснюються цими законами.
Обладнання: призма, лазер.