ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Эффективность двойных структур данных

Алгоритмы структуры данных

Эффективность двойных структур данных

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

Предположим, что мы хотим создать "теннисную лестницу" (т.е. квалификационную таблицу), где каждый игрок располагается на своей "ступеньке" (рейтинге). Новые игроки добавляются в самый низ, т.е. на ступеньку с самым большим номером. Игрок может вызвать на поединок игрока, стоящего на более высокой ступени, и если он выиграет матч, то они меняются ступенями. Эту "лестницу" можно рассматривать как абстрактный тип данных, где базовой моделью будет отображение из множества имен игроков (строки символов) в множество номеров ступеней (целые числа 1, 2, ...). Необходимы также три оператора, выполняемые над этим АТД.

1.    АDD(имя) добавляет новое имя в квалификационную лестницу на свободную ступеньку с наибольшим номером, т.е. в самый низ лестницы.

2.    CHALLENGE(имя) возвращает имя игрока, стоящего на ступени і - 1, если игрок имя стоит на ступени і, і > 1.

3.    EXCHANGE(t) меняет местами игроков, стоящих на ступенях і и і - 1, і > 1.

Для реализации описанных данных и их операторов можно использовать массив LADDER (Лестница), где LADDER[i] — имя игрока, стоящего на ступени і. Вместе с именем игрока можно хранить и его номер (т.е. номер ступени, на которой он стоит). В этом случае нового игрока можно просто добавить за малое фиксированное время в свободную ячейку массива.

Оператор EXCHANGE реализуется легко — меняются местами два элемента массива. Но выполнение функции CHALLENGE в процессе поиска заданного имени требует времени порядка О(п) для просмотра всего массива (здесь и далее п — общее число игроков).

С другой стороны, мы можем применить хеш-таблицу для задания отображения из множества имен в множество номеров ступеней. Количество сегментов в хеш-таблице примерно равно количеству игроков. Оператор ADD выполняется в среднем за время О(1). Функция CHALLENGE тратит в среднем О(1) времени на поиск заданного имени, но требует О(п) времени для поиска имени соперника, стоящего на более высокой ступени, поскольку в этом случае надо просмотреть всю хеш-таблицу. Оператор EXCHANGE требует О(п) времени для поиска имен игроков, стоящих на ступенях і и і - 1.

Теперь рассмотрим применение комбинации двух структур. Пусть ячейки хеш-таблицы содержат имя игрока и его номер ступени, а в массиве LADDER элемент LADDER[i] будет указателем на ячейку игрока в хеш-таблице, стоящего на і-й ступени, как показано на рис. 4.10.

 

.

При такой организации данных добавление нового игрока требует в среднем О(1) времени для записи его атрибутов в хеш-таблицу, а также создания указателя на его ячейку в хеш-таблице из ячейки массива LADDER, которая помечена курсором nextrung (следующая ступень) (см. рис. 4.10). При выполнении функции CHALLENGE надо сначала найти заданное имя в хеш-таблице (на это требуется в среднем О(1) времени), получить его номер ступени і и далее, следуя за указателем из ячейки LADDER[i - 1] в ячейку хеш-таблицы, получить имя игрока-соперника. Все последние описанные действия в среднем требуют не более О(1) времени, поэтому все время выполнения функции CHALLENGE имеет в среднем порядок О(1).

Оператор EXCHANGE(i) требует времени порядка О(1) для нахождения имен игроков с рангами і и і - 1, для обмена содержимым двух ячеек хеш-таблицы и обмена указателями в двух ячейках массива LADDER. Таким образом, даже в самом худшем случае время выполнения оператора EXCHANGE не будет превышать некоторой фиксированной величины.

 

 

 

 

66