Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

В книге подробно рассматриваются базовые понятия алгоритмов и основополагающие структуры данных, алгоритмы сортировки, поиска, хеширования, синтаксического разбора, сжатия данных, а также многие другие темы, тесно связанные с прикладным программированием. Изобилие тщательно проверенных примеров кода существенно ускоряет не только освоение фундаментальных алгоритмов, но также и способствует более квалифицированному подходу к повседневному программированию.

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

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

Длинные строки

Дискуссию о быстродействии алгоритмов нельзя считать законченной без краткого рассмотрения длинных строк. С ними связан целый ряд проблем, касающихся эффективности. Длинные строки появились в Delphi 2 и присутствовали во всех последующих компиляторах Delphi и Kylix (программисты, работающие в Delphi1, могут не беспокоиться о длинных строках и без последствий пропустить этот раздел).

Длинная строковая переменная string - это всего лишь указатель на специальным образом отформатированный блок памяти. Другими словами, sizeof(stringvar) - sizeof(pointer). Если указатель содержит nil, строка считается пустой. В противном случае указатель указывает непосредственно на последовательность символов, составляющих строку. Функции для работы с длинными строками в библиотеке времени выполнения гарантируют, что строка всегда завершается нулем (null-символом). Благодаря этому, строковую переменную всегда можно легко привести к типу PChar, используемому при вызове API-функций системы. Но, наверное, не все знают, что блок памяти, на который указывает указатель, содержит и некоторую дополнительную информацию. Четыре байта, расположенные до последовательности символов, представляют собой целочисленное значение - длину строки (за исключением завершающего нуля). Предшествующие четыре байта содержат целочисленное значение, представляющее собой счетчик ссылок (для постоянных строк это значение равно -1). Если память для строки выделена из кучи, то предшествующие четыре байта содержат целочисленное значение, представляющее собой полный объем используемого строкой блока памяти, включая все скрытые целочисленные поля, последовательность символов, составляющих строку, и скрытый завершающий null-символ, округленные до ближайших четырех байтов.

Счетчик ссылок присутствует в блоке памяти, поэтому операция

MyOtherString := MyString выполняется очень быстро. Компилятор преобразует это присвоение за два шага: сначала он увеличивает на 1 счетчик ссылок для строки, на которую указывает MyString, а затем устанавливает указатель MyOtherString равным указателю MyString.

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

Использование ключевого слова const

Если функции передать строку, которая в процессе выполнения функции не будет изменяться, объявляйте ее как const. В большинстве случаев это исключает скрытое добавление блока try..finally. Если не использовать ключевое слово const, компилятор будет считать, что значение, возможно, будет изменяться, и поэтому вводит скрытую локальную переменную для хранения строки. В начале выполнения функции счетчик ссылок будет увеличен на 1, а в конце - уменьшен на 1. Чтобы гарантировать, что значение счетчика всегда будет уменьшаться, компилятор вставляет скрытый блок try..finally.

В листинге 1.5 приведена функция определения количества гласных в строке.

Листинг 1.5. Подсчет количества гласных в строке

function CountVowels(const S : string): integer;

var

i : integer;

begin

Result := 0;

for i := 1 to length (S) do

if upcase(S[i]) in ['A', 'E', 'I', 'O', 'U'] then

inc(Result);

end;

Если из строки объявления функции убрать ключевое слово const, ее быстродействие снизится приблизительно на 12% - это и есть влияние скрытого блока try..finally.

Осторожность в отношении автоматического преобразования типов

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

PosOfCh := Pos(SomeChar, MyString);

нужно помнить, что компилятор автоматически преобразует символ в длинную строку. Он выделит память для строки из кучи, установит длину равной 1 и скопирует в строку символ. Затем вызывается функция Pos. Поскольку фактически будет использоваться скрытая длинная строка, для уменьшения значения счетчика ссылок в функцию будет автоматически добавлен блок try..finally. Функция, приведенная в листинге 1.6, в пять (да-да, в пять!) раз быстрее, несмотря на то, что она была написана на языке Pascal, а не на ассемблере.

Листинг 1.6. Определение позиции символа в строке

function TDPosCh(aCh : AnsiChar;

const S : string): integer;

var

i : integer;

begin

Result := 0;

for i := 1 to length(S) do

if (S[i] = aCh) then begin

Result := i;

Exit;

end;

end;

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

И еще одна небольшая рекомендация. Операция конкатенации, +, тоже работает только со строками. Если конкатенация символа со строкой выполняется в цикле, попытайтесь найти для этого другой способ (например, предварительно задать длину строки, а затем присвоить значения отдельными символам строки), поскольку компилятору придется автоматически преобразовывать все символы в строки.

Тестирование и отладка

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

Независимо от того, как мы пишем код, в какой-то момент потребуется провести тестирование [31], дабы убедиться в том, что код работает, как задумывалось. Дает ли код правильные результаты для определенного набора входных значений? Записываются ли данные в базу данных при нажатии на кнопку ОК? Естественно, если тестирование проходит неудачно, необходимо найти ошибку и устранить ее. Этот процесс известен как отладка - тестирование показало наличие ошибки и нужно найти ее и устранить. Таким образом, тестирование и отладка неразрывно связаны между собой - по сути, это две стороны одной медали.

Поскольку мы никак не можем обойтись без тестирования (хотелось бы думать, что мы безупречны, а наш код не содержит ошибок, но, к сожалению, это не так), каким образом можно упростить этот процесс?

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

----

Правило № 1. Код всегда содержит ошибки.

----

И хотя выше было сказано, что нечего смущаться при обнаружении кода с ошибками, есть все же одна ситуация, когда это выставляет вас в плохом свете - когда вы не протестировали код в достаточном объеме.

Утверждения

Поскольку первое правило гласит, что отладку нужно проводить всегда, а вывод подразумевает, что не хотелось бы краснеть за недостаточный объем тестирования кода, необходимо научиться создавать защищенные программы. И первым средством из защитного арсенала является утверждение.

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

Джон Роббинс (John Robbins) [19] установил второе правило: "Утверждения, утверждения и еще раз утверждения". В соответствии с его книгой, он считает количество утверждений достаточным, если коллеги начинают жаловаться, что при вызове его кода они постоянно получают сообщения о проверках утверждений.

Таким образом, второе правило можно выразить так: используйте утверждения много и часто. Вставляйте утверждения при каждом удобном случае.

----

Правило № 2. Используйте утверждения много и часто.

----

К сожалению, некоторые программисты при использовании утверждений столкнутся с проблемами. Дело в том, что поддерживаемые компилятором утверждения появились только в версии Delphi 3. С тех пор утверждения можно применять безнаказанно. Компилятор позволяет указывать, вносить ли проверки в выполняемый файл или же игнорировать их. При тестировании и отладке компиляция выполняется с утверждениями. При создании окончательного выполняемого файла утверждения игнорируются.