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

-----------------------

Итак, почему Delphi? На самом деле, на то имеются две причины: язык Object Pascal и операционная система. Язык, встроенный в среду Delphi, имеет множество конструкций, которые не доступны в других языках, конструкций, которые существенно упрощают инкапсуляцию эффективных алгоритмов и структур данных и делают ее более естественной. Примером могут послужить такие вещи, как свойства. Или, скажем, механизм исключений, генерируемых в случае возникновения непредвиденных ситуаций и ошибок. Несмотря на то что стандартные алгоритмы можно кодировать на Delphi и без применения таких специфических языковых конструкций, я довольно-таки твердо убежден, что в этом случае мы безвозвратно теряем и красоту, и эффективность реализаций, предпосылками которых является язык. Мы лишаем себя возможности исследовать все "закоулки" этого замечательного языка программирования. В этой книге мы собираемся повсеместно использовать всю мощь, присущую языку Object Pascal в среде Delphi. Я не думаю, что у программистов на Java будут возникать какие-то сложности с интерпретацией и переводом кода на свой язык. Однако раз уж я выбрал Delphi, то Delphi и буду придерживаться.

Следует принять во внимание еще одну вещь. Как традиционно предполагается, алгоритмы являются общими, по крайней мере, на одном и том же центральном процессоре и в среде одной и той же операционной системы. Конечно, алгоритмы можно оптимизировать под среду Windows или Linux. Можно добиться большей эффективности при их выполнении на семействе процессоров Pentium, в случае использования различных типов кэш-памяти или подсистем виртуальной памяти в средах разных операционных систем. Подобным возможностям оптимизации в книге уделяется отдельное внимание. Тем не менее, мы не будем доходить в своей погоне за эффективностью до кодирования на языке ассемблера, оптимизированного под конвейерную архитектуру новых процессоров, - я должен был хоть где-нибудь это сказать!

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

В этой книге отнюдь не предпринимается попытка обучить кого-либо программированию на Delphi. Необходимо знать основы разработки приложений на Delphi: создание новых проектов, написание кода, компиляцию, отладку и так далее. Я вынужден предупредить, что в книге не используются компоненты. Вы должны четко представлять, что такое классы, процедуры и методы, а также ссылки на них, владеть механизмом нетипизированных указателей, уметь использовать тип TList и потоки, инкапсулированные в семейство TStream. Очень важно владеть основами объектно-ориентированной методологии, в частности, представлять, что такое инкапсуляция, наследование, полиморфизм и делегирование. Вас не должна пугать объектная модель, реализованная в рамках Delphi!

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

Итак, на данный момент можно с уверенностью заявить, что вы должны обладать определенным опытом программирования на Delphi. То и дело придется сталкиваться со структурами данных, лежащими в основе TList и иже с ними, посему следует четко представлять себе, какие структуры данных доступны, и как их использовать. Может статься, что вам необходимо разработать простую подпрограмму сортировки, однако все, что содержит доступный вам источник - так это написанный кем-то код на языке С++, а ни времени, ни желания переводить этот код на Delphi нету. А, может, вас интересует книга по алгоритмам, в которой вопросы увеличения производительности и эффективности описываются столь же хорошо, как и сами алгоритмы? Такая книга перед вами.

Готовы ли вы к тому, что я сейчас скажу? Любая версия. За исключением раздела, посвященного использованию динамических массивов в Delphi 4 и тех же массивов в Kylix в главе 2, части материала в главе 12 и небольших фрагментов кода тут и там, приведенный в книге код будет компилироваться и выполняться под управлением любой версии Delphi. Не считая небольших порций кода, специфических для конкретной версии, о который только что было упомянуто, я протестировал весь код, приведенный в книге, во всех версиях Delphi и Kylix.

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

Книга состоит из двенадцати глав и списка использованной литературы.

В главе 1 вводятся несколько основных правил. Глава начинается с обсуждения проблемы производительности. Мы ознакомимся с вопросами измерения эффективности алгоритмов, начав с изучения О-нотации. Затем мы рассмотрим методику измерения времени выполнения алгоритмов и завершим исследованиями способов применения профилировщика. Мы обсудим эффективность представления данных в контексте современных процессоров и операционных систем, акцентируя особое внимание на кэш-памяти, механизмах подкачки и подсистемах виртуальной памяти. В конце главы приводятся рассуждения по поводу тестирования и отладки, которые можно встретить во множестве других книг, однако, по причине их чрезвычайной важности, непростительно было бы упустить эту тему из виду.

Глава 2 покрывает практически все основные вопросы, связанные с массивами. Мы посмотрим на стандартную языковую поддержку массивов, в том числе и динамических массивов, обсудим достоинства, недостатки и методику применения класса TList, а затем разработаем класс, инкапсулирующий в себе массив записей. Ввиду того, что строка, как структура данных, также представляет собой массив, мы кратко коснемся и ее.