Конструированием словаря управляют четыре параметра: размер словаря, порог укрупнения гнезд, начальное значение счетчика укрупненных гнезд и порог исключения гнезд. Выбор, который мы сделали, может показаться несколько странным. Размер словаря определяет макро DICTIONARY.SIZE и задается в нашем случае равным 100 (не забудьте, что массивы в XPL начинаются с нулевого индекса), а начальное значение счетчика в гнезде — посредством функции FIRST.COUNT. (начальный счетчик)— устанавливается равным единице. Укрупнение гнезд производится в случае, когда каждое из них имеет частоту не меньше, чем DICTIONARY.SIZE/(DICTIONARY.SIZE — DICTIONARY.TOP + 1) + 1, т. е. когда частоты обоих гнезд больше величины, обратно пропорциональной свободному пространству словаря. При этом мы исходили из представления (которое не слишком-то хорошо себя оправдало), что, когда словарь почти заполнен, записать новое гнездо должно быть труднее. Исходя из вида приведенного выражения, мы называем порог укрупнения гнезд завышенным порогом укрупнения. Исключение гнезд осуществляется в случае, если их частоты по крайней мере не больше средней частоты,— предполагается, что она является приближенным значением медианы. Чтобы установить, в какой степени такой выбор параметров действительно необоснован, изменим каждый из них, кроме размера словаря, и положим их значение равным пяти.
Таблица 30.2. Небольшое исследование влияния параметров
В табл. 30.2 отражены результаты обработки обоих файлов. Из таблицы видно, что как порог укрупнения, так и порог исключения оказались неудачными. Вполне возможно, что завышенный порог укрупнения не позволяет объединить и поместить в таблицу достаточное число укрупненных гнезд и, кроме того, быть может, средняя частота, взятая в качестве порога исключения, является плохим приближением медианы, что приводит к ликвидации слишком большого числа гнезд. Все это — лишь очень поверхностное исследование, и надо бы собрать еще дополнительный материал. Однако нас заест тоска раньше, чем программа станет более эффективной.
Заключительные замечания
Должно быть, эта глава совершенно не похожа на проект, выполненный на пять с плюсом. Над самой программой можно бы было потрудиться и побольше, особенно над комментариями. Немало среди них путаных и бесполезных. В результате напечатанная программа еще на полпути к завершению, и вы можете полюбоваться, на что похожи ваши собственные недоделанные программы. Вернитесь назад и еще раз разберите программу, задаваясь при этом мысленным вопросом: «А как бы можно было вылизать данную строку (комментарий, процедуру), чтобы достичь кристальной ясности?» И после того, как вы, ехидничая по поводу чужих способностей, закончите, посмотрите, положа руку на сердце, нельзя ли ваши рекомендации применить к вашим собственным программам. Желательно, чтобы законченный проект включал в себя также наглядное доказательство правильности алгоритмов, дополнительную печать и хотя бы несколько рекомендаций по повышению эффективности словаря. Составление программы заняло около восьми часов, а отладка — около четырех. Причем из четырех часов отладки два ушло на устранение обычных описок и на наведение красоты печати. Остальные два часа отладки были посвящены тому, чтобы добавить «+1» в 91-ю строку измененного файла. Одна эта маленькая коварная ошибка вызвала массу трудностей и полностью нарушила режим работы программы поиска в упорядоченном словаре. В конце концов, ошибка была обнаружена после того, как мы объяснили всю программу другому программисту. Придерживаясь принципа беспристрастности, он не разделял нашего превратного толкования программы и моментально обнаружил «ляп». Кроме того, около часа было затрачено на вставку и отладку временных переменных (средства подсчета времени в эксплуатирующейся у нас системе развиты в недостаточной степени) и порядка четырех часов на жонглирование параметрами.