2.1. Практикум по гл. 2
Переработать программу работы с библиотекой фигур, дополнив ее механизмом контроля исключительных ситуаций. Например, возможно выявление следующих ошибок:
— непопадание точки на экран;
— некорректные параметры при формировании фигуры;
— нехватка места на экране для размещения фигуры в одной из позиций (исходной, повернутой, отраженной, перемещенной);
— повторный поворот/отражение уже повернутой/отраженной фигуры и др.
Нужно реализовать генерацию и перехват не менее двух типов ошибок разного уровня сложности.
Если исключение генерируется в конструкторе фигуры, следует обеспечить исключение фигуры из списка для рисования или подмену ее запасной фигурой — знаком ошибки.
Перехват исключения в той же функции, в которой оно возбуждено, не применяется. В этом случае, когда ошибку можно обработать в точке обнаружения, механизм исключений избыточен.
Организовать перехват исключений следует таким образом, чтобы искажения итоговой картинки были минимальны. Протестировать исключительные ситуации, результаты эксперимента поместить в отчет.
2.2. Дополнительные требования к отчету
В отчете по теме обоснуйте набор и вид классов для фиксации особых ситуаций, место расположения операторов throw и блоков контроля с целью получения безопасного кода. Приведите результаты тестирования.
2.3. Контрольные вопросы
1. Что такое исключительная ситуация при выполнении программы?
2. Как можно выявить исключительную ситуацию?
3. Что можно предпринять при выявлении исключительной ситуации?
4. Можно ли передать в обработчик особых ситуаций какую-либо информацию о произошедшем событии?
5. Можно ли обработать неизвестную особую ситуацию?
6. Можно ли сделать обработчик ситуации пустым?
7. Что можно предпринять, если для корректной обработки ситуации в данном месте программы у обработчика недостаточно данных?
8. Если требуется несколько обработчиков особых ситуаций, в каком порядке следует их размещать в программе?
9. Можно ли перехватывать одним обработчиком несколько различных особых ситуаций?
10. Как действуют обработчики в случае, когда никакой особой ситуации не произошло?
11. Как следует размещать блоки контроля, чтобы получить безопасный программный код?
12. Можно ли продолжить выполнение программы с точки, в которой выявлена ошибка, после внесения исправлений в данные?
3. КОМБИНИРОВАННЫЕ СТРУКТУРЫ ДАННЫХ
И СТАНДАРТНАЯ БИБЛИОТЕКА ШАБЛОНОВ
В практических задачах множество часто используется как словарь. Основные операции со словарем — это поиск, добавление и удаление элементов множества (ключей). Двуместные операции со словарями выполняются сравнительно редко. При хранении множеств в форме упорядоченной последовательности операции поиска/вставки/удаления выполняются за линейное время. Если нужен только поиск, данные можно хранить в упорядоченном векторе (длиной n) с доступом к ключам за время O(logn). Для хранения словарей с возможностью пополнения применяются структуры данных, совмещающие быстрый поиск с быстрым добавлением и удалением ключей. Для небольших универсумов задачу решает вектор битов. Если же универсум велик, используются хеш-таблицы, деревья двоичного поиска и им подобные структуры данных.
3.1. Хеш-таблицы
Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U велика по отношению к мощности множеств, с которыми нужно работать. Функция отображения преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы, m ≪ |U|. Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, имеется возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии).
Количество возможных коллизий можно уменьшить, если выполнить два условия:
1) выбрать размер хеш-таблицы с запасом. Если размер таблицы превышает мощность хранимого множества более чем вдвое, вероятность коллизии становится меньше 0.5. Если мощность множества заранее неизвестна, то выбирают некоторый начальный размер, а когда его оказывается недостаточно, таблицу перестраивают с увеличением размера (обычно вдвое);
2) подобрать функцию отображения (хеш-функцию) такую, чтобы все ячейки таблицы были востребованы по возможности с равной вероятностью, независимо от того, какое распределение имеют хранящиеся в таблице ключи.
По способу разрешения коллизий различают хеш-таблицы двух типов:
1) с открытой адресацией. Конфликтующие значения ключей размещаются в свободных ячейках таблицы;
2) с цепочками переполнения. Каждая ячейка таблицы содержит указатель на список конфликтующих ключей.
Подробнее о хеш-таблицах — в [1, с. 115–128], [13, с. 529–556], [5, с. 316–338].
103 102 101 100 35 50 - 32 31 30 - 44 123 90 105 120
55 38 37 20 - - - 80 - - - 60 - 10 - 104
- 70 - - - - - - - - - - - - - 40
- - - - - - - - - - - - - - - -
Рис. 3.1. Хеш-таблица из 16 экстентов с цепочками переполнения
Таблицы второго типа применяются чаще, потому что для них не существует проблемы переполнения. Если мощность хранимого множества становится слишком большой, таблица просто начинает работать как m списков. Если же таблица правильно построена и не переполнена, проверка принадлежности элемента множеству, а также вставка и удаление элемента выполняются в ней за постоянное время, примерно такое же, как и в массиве битов (рис. 3.1).
За постоянное время (порядка размера таблицы) будут выполняться и двуместные операции над множествами: объединение, пересечение и разность: если хеш-функции для обоих множеств одинаковы, для этого пригоден такой же алгоритм попарного сравнения соответствующих ячеек, как и для массивов битов. В общем случае двуместная операция, организованная как просмотр первой таблицы, поиск каждого ключа во второй и вставка при необходимости в третью, имеет линейную сложность.
В хеш-таблице можно хранить и множество с повторениями: совпадающие значения ключей не создают никаких проблем, кроме гарантированных коллизий, которые разрешаются обычным образом.
К сожалению, всегда можно подобрать такие данные, что они все попадут в одну или несколько ячеек таблицы, образовав неупорядоченные списки (упорядочивание обычно не применяется). Это худший случай, для которого справедливы оценки временной сложности для списков: O(n) — для поиска и удаления элемента; O(n2) — для двуместной операции над множествами.
Подбор подходящей хеш-функции — в общем случае достаточно сложная задача. Но если ключи представляют собой целые числа (или сводятся к таковым), хорошие результаты можно получить с хеш-функцией вида
h(x) = (a * x + b) % m,
где m – размер таблицы, a и b — простые числа.
Обычно a выбирается близким по значению к m, а b — к 1. Так, при m = 100 можно взять a = 97, b = 11. Такой выбор обеспечивает равномерное использование всех ячеек таблицы в большинстве практических случаев. Если размер таблицы m предполагается изменять, можно взять в качестве a любое достаточно большое простое число.
3.1.1. Контрольные вопросы
1. Какой объем памяти нужно выделять под хеш-таблицу для хранения множеств со средней мощностью 50?
2. Хеш-таблица какого типа расходует больше памяти для хранения множества — с открытой адресацией или с цепочками переполнения?
3. Каким требованиям должна удовлетворять «хорошая» хеш-функция?
4. Можно ли построить хеш-таблицу, в которой не будет коллизий?
5. Каков оптимальный алгоритм выполнения двуместной операции над множествами в хеш-таблице? Какова его временная сложность?
6. Можно ли хранить в хеш-таблице множество с повторениями?
7. Какова временная сложность операций вставки и удаления элемента для хеш-таблицы?
8. Почему для операций с хеш-таблицей дают две оценки временной сложности — сложность в худшем случае и сложность в среднем?
9. Что такое вырождение хеш-таблицы и как его избежать?
10. Что нужно делать, если хеш-таблица переполнилась?
|
Скачать 0.78 Mb.