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

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

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

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

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

---

Одним из новых методов разработки программного обеспечения, который появился уже при написании этой книги, является экстремальное программирование (extreme programming)[3]. Этот метод состоит в целом наборе рекомендаций. Некоторые рекомендации достаточно спорны, но, по крайней мере, одна из них имеет смысл: пишите тест тогда, когда вы пишете метод класса. Если метод требует не одного теста, разработайте несколько тестов. Такой порядок обладает двумя преимуществами: во-первых, код вам знаком - вы только что его написали, и, во-вторых, в дальнейшем разработанный тест может быть включен в тестовый набор и применяться для тестирования приложения после внесения в него изменений. Таким образом, вы можете быть уверены, что изменения не повлекли за собой возникновение ошибок.

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

Тестирование модулей требует наличия специального средства, которое помогало бы собирать тесты, поддерживать их актуальность и периодически, в автоматическом режиме, запускать их с целью проверки правильности кода. К счастью, существует одна библиотека с открытым исходным кодом, которую можно использовать свободно, - Duhit. Она представляет собой порт для Delphi инструментальных средств тестирования Java-модулей, частично написанный автором книги "Extreme Programming Explained" Кентом Беком (Kent Beck). (Dunit можно использовать, только начиная с версии Delphi 3.)

Dunit представляет собой средство тестирования, или тестовый каркас, реализованный на Delphi. Используя его, программист пишет отдельные тесты, предназначенные для проверки своего кода. Тесты могут быть совсем простыми (например, в тесте может создаваться объект, проверяться значения заданных по умолчанию свойств, после чего объект удаляется), но в общем случае они должны быть предназначены для выполнения всего кода класса или модуля. (Чтобы убедиться, что выполняются все строки кода, можно воспользоваться анализатором покрытия.) Сам тестовый каркас предоставляет пользовательский интерфейс, который позволяет программисту выбрать один или несколько тестов и запустить их. После выполнения теста или тестов программист может просмотреть результаты: успешное выполнение или ошибка (Dunit при выводе результатов использует различные цвета, благодаря чему результат выполнения теста можно оценить с первого взгляда.) Конечно, по истечении некоторого времени тест может оказаться неактуальным, поскольку, например, класс настолько изменился, что выполнение существующего теста не позволяет определить правильность кода. В таком случае тест потребуется написать заново.

----

Правило № 6. Для организации набора тестов для проверки модулей воспользуйтесь тестовым каркасом. При изменении кода выполните тесты повторно.

----

Если у вас есть Dunit для определенного класса или модуля, его можно использовать для регрессионного тестирования (regression testing). Регрессионное тестирование представляет собой тестирование всего класса или модуля после внесения изменений в этот класс или модуль. Часто поиск и устранение одной ошибки приводит к возникновению другой ошибки.

Рассмотрим пример. В библиотеке TurboPower Internet Professional (библиотека Delphi для реализации таких протоколов Internet, как FTP, HTTP и т.д.) имеется функция, которая разбивает URL на различные части. URL-адрес может указывать на Web-сайт или на FTP- сайт, это может быть относительный путь (например, путь к графическому изображению на Web-странице, может указываться относительно папки, в которой находится основная Web-страница), или MAILTO-адрес, или просто файл на жестком диске. Формат URL-адреса достаточно сложен. Его можно видеть в адресной сроке Web-браузера. Синтаксический разбор URL-адреса представляет собой весьма сложную задачу, которая, к сожалению, не достаточно четко определена.

Примером может служить URL-адрес перечня опечаток для настоящей книги - http://www.boyet.com/dads. Он состоит из трех частей. Первая, "http://" определяет протокол, вторая, "www.boyet.com", указывает имя сервера, а третья, "/dads" - имя папки на сервере.

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

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

Тестовый каркас Dunit можно найти в Internet по адресу http://dunit.sourceforge.net. Все коды, приведенные в книге, были протестированы с помощью тестов, написанных с использованием Dunit. Некоторые тесты включены в материалы, сопровождающие книгу, которые доступны на Web-сайте издательства.

Отладка

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

----

Правило отладки № 1. Выбирайте воспроизводимый случай тестирования.

----

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

Второе правило отладки намного сложнее.

----

Правило отладки № 2. Исходите из того, что ошибка внесена вами.

----

Может быть, вы неправильно используете API-интерфейс операционной системы или библиотека компонентов требует определенной последовательности операций. Или, в конце концов, может быть, вызываемая вами функция не может принимать nil в каком-либо входном параметре. Маловероятно, чтобы ошибка была вызвана неправильной работой API-интерфейса или компилятора. Более вероятно, что ошибка присутствует в библиотеке компонентов, тем не менее, попытайтесь выделить проблему (см. правило отладки 1), что позволит с уверенностью сказать, что ошибка находится не в вашем коде. Конечно, если ошибка находится не в вашем коде, ваша задача только усложняется, поскольку придется положиться на разработчиков операционной системы, компилятора или библиотеки компонентов, что они достаточно быстро устранят имеющуюся проблему.

Следующее правило вытекает из уже рассмотренного нами материала.

----

Правило отладки № 3. Для проверки того, что код работает, как того ожидалось, используйте утверждения.

----

Кроме того, можно применять и протоколирование, которое позволит отслеживать состояние различных объектов.

А теперь перейдем собственно к отладке.

----

Правило отладки № 4. Используйте автоматизированные инструментальные средства отладки.

----

Возможно, ваша ошибка вызвана перезаписью какой-то области памяти или получением доступа к памяти после того, как она была освобождена, либо, скажем, при вызове API-функции не проверяется код возвращаемой ошибки. Все описанные типы проблем можно обнаружить в таком автоматизированном средстве отладки, как TurboPower Sleuth QA Suite. Приобретите средство отладки и используйте его не только в процессе тестирования, но и в процессе обнаружения ошибок.

Естественно, после этого следует сама отладка, которая может выполняться даже с помощью отладчика. Именно здесь наука программирования превращается в настоящее искусство. Отладку нельзя назвать алгоритмом, скорее, это соревнование. Единственным советом в этом соревновании может быть "не делайте никаких допущений". Если вы считаете, что некоторая переменная должна содержать определенное значение, проверьте это. Пользуйтесь средством визуализации значений отладчика. Для наблюдения за блоком памяти можно воспользоваться окном процессора. Попытайтесь предсказать значения переменных, а затем проверить свои предположения и при необходимости устраните ошибки. Без боязни добавляйте в код новые утверждения с целью проверки своих предположений.