В статье дается краткое описание библиотеки контейнеров и алгоритмов SDL/DeCAL. Приложение к статье - перевод руководства по библиотеке на русский язык.
Библиотека SDL была разработана в 1998 году как коммерческий продукт. В 2000 году, автор, Росс Джадсон, опубликовал ее в категории open source public domain на сайте http://sourceforge.net/projects/decal/. При этом библиотека получила другое имя - DeCAL. Вот что пишет об этом сам Росс.
Это предварительный выпуск библиотеки DeCAL. DeCAL наследует и заменяет библиотеку SDL, прежнее коммерческое изделие от Soletta. DeCAL предоставляет твердую теоретическую основу для структур данных и нетривиальных приложений, написанных на Delphi. Хотя это предварительный выпуск, он предварителен только в смысле тонкостей продуктов с открытым кодом (open source). DeCAL/SDL - часть многих коммерческих Delphi-приложений. Документация, поставляемая с DeCAL (Guide.pdf) - это документация для SDL. Только подразумевайте каждый раз DeCAL вместо SDL. Вскоре документация будет обновлена, чтобы отразить новое название.
К сожалению, обещанного обновления документации и официального stable-выпуска библиотеки так и не случилось, хотя с момента публикации DeCAL прошло почти 4 года. Возможно, Росс потерял интерес к библиотеке. Есть еще один повод для сожаления - столь замечательная разработка осталась практически неизвестной среди Delphi-программистов, хотя ни в одной другой подобной работе (ни до нее, ни после) я не встречал реализации, столь близкой по духу к библиотеке STL.
Все известные мне библиотеки контейнеров можно разделить по принципу реализации на три больших группы.
Библиотеки первой группы, такие как FUNDAMENTALS (Дэвида Батлера), Vectors (Алексея Чернобаева), характеризуются тем, что содержат огромное количество модулей и классов, для каждого контейнера дается его реализация применительно к каждому из примитивных (Integer, Double и т.д.) типов Delphi. Каждый раз, когда мне попадалась такая библиотека, я прочитывал руководство к ней и, уважая труд автора, ложил ее в архив, надеясь использовать ее при удобном случае. Хотя такие библиотеки и обеспечивали, вероятно, максимальную эффективность, но как-то душа не лежала использовать их как основной инструмент. И практика показывала, что каждый раз, когда возникала подобная задача, требующая эффективного решения, мне было удобнее реализовывать ее самому.
Вторая группа контейнерных библиотек, таких как EZDSL (Джулиана Макнолла), ориентирована на хранение бестиповых указателей или ссылок на TObject, поэтому такие библиотеки весьма компактны и содержат относительно небольшое число модулей и классов. Большой минус таких библиотек в том, что в них неудобно работать с примитивными типами.
Библиотеки третьей группы, такие как Delphi Collections (Мэттью Грита), XDContainers (Николая Мазуркина), основаны на чистом объектно-ориентированном подходе и используют наследование интерфейсов. Это очень чистое и красивое решение, достаточно сказать, что библиотека классов фирмы Microsoft, .Net Framework, использует именно этот принцип. Трудностей при использовании такого решения тоже хватает. Во-первых, неудобно работать с примитивными типами (не классами) - приходится размещать их в классах. Здесь уместно отметить, что разработчики .Net Framework и C# учли это, и предусмотрели автоматическую упаковку и распаковку (boxing-unboxing) примитивных типов. Вторая трудность в том, что эту технику удобно применять как основу проекта, но трудно интегрировать ее в уже имеющийся код при сопровождении проекта.
Но самый важный фактор, на мой взгляд, состоит в том, что библиотеки контейнеров служат лишь вспомогательным средством, лишь экономящим, в ряде случаев, время программиста на рутинных задачах. Они очень редко помогают в формировании архитектуры проекта и слабо стимулируют программиста в том, чтобы искать более оптимальные архитектурные решения, хотя и увеличивают эффективность реализации. Говоря это, я вспоминаю слова одного из классиков программирования (не помню точно, кажется, Гради Буча), что повышенная забота об эффективной реализации на ранних фазах проекта может привести к его провалу в архитектурном смысле. Здесь уместно вспомнить о паттернах проектирования (Эрих Гамма и др.), которые нацелены именно на оптимизацию архитектурных решений программистского проекта.
Эти экскурсы по другим контейнерным библиотекам мне были нужны, что показать весьма существенные отличия библиотеки SDL/DeCAL и ее некоторую обособленность. Здесь можно было бы к ней и перейти, но мне подумалось, что будет интересным обрисовать также другие факторы, более психологического, чем прагматического, свойства. Вероятно, это покажется странным, но эти факторы тесно связаны с тем, почему я работаю сейчас в основном на Delphi, хотя весь мой предыдущий программистский опыт был связан с языком C++.
В тот год, когда фирма Borland объявила о прекращении поддержки Borland C++ и библиотеки OWL, я встал перед проблемой выбора новой среды программирования, учитывая то, что мне волей-неволей придется сопровождать долгоживущие проекты на C++, в которых я принимал участие. Ранее, беззаботно используя эти прекрасные инструменты, я свысока посматривал на Visual C++ Studio и библиотеку MFC. Один раз, когда выдался относительно свободный месяц, я решил честно поработать на Visual C++ и MFC, сделав небольшой проект. Нужно же узнать, есть ли что слаще меда. Результаты были обескураживающими - после элегантной OWL, библиотека MFC показалась мне каким-то уродцем; среда программирования, хотя и похожей, но страшно неудобной, причем было неудобно почти все. За этот месяц я так и не смог преодолеть к ним неприязни, хотя программировать вполне можно. И вот теперь проблема выбора новой среды встала как неотвратимая реальность. Но переходить на Visual C++ и MFC для меня было бы слишком тяжело психологически. Конечно, я уже слышал о Delphi, но относился к ней как к забавной зверушке. Поскольку работать с инструментами от Microsoft мне было невмоготу, то я решил попробовать Delphi. Надо сказать, что процесс освоения нового языка и новой среды оказался чрезвычайно легким и гладким, так что я изредка говорил про себя - аx, Borland, Borland! Уже после короткого времени работы с новой средой я был настолько очарован легкостью и элегантностью разработки визуальной части программ, что не заметил, как … попал в ловушку.
Сидя на дне этой ловушки, я начал размышлять, что произошло. А произошло вот что - я практически перестал заниматься архитектурной частью проектов. Легкость, с которой в Delphi можно собрать прототип проекта и превратить его в работающий проект, сыграла со мной злую шутку. Работая на C++, я детально продумывал структуры данных, разделение программы на Документ и Вид, организацию удобной для сопровождения иерархии классов, алгоритмы работы с данными. Большую часть средств для этого предоставляла библиотека STL (Standard Template Library), без учета ее алгоритмов и контейнеров я и не представлял разработку проекта. Относительная трудоемкость реализации визуальной части программы прямо таки заставляла больше времени уделять сути программы, как более интересной и творческой. Но все смешалось в доме Облонских, когда визуальную часть стало разрабатывать не просто интересно, а очень интересно, таская по форме разные красивые компоненты. Причем это перешло даже в патологию - мне уже не казалось дикостью использование TTreeView в качестве контейнера, когда в программе требовалась структура данных в виде дерева. Кстати сказать, именно в этот период моей жизни я начал проявлять интерес к разным игрушкам, вроде Героев Меча и Магии. Неслучайное совпадение.
Осознав этот факт, я дал задний ход, стал очень аскетично относиться к внешнему виду программ и начал более серьезно относиться к своему инструментарию, разрабатывая, по ходу реализуемых проектов, разные модули, вроде модуля поддержка модели "документ-вид", реализации шаблона "Компоновщик", библиотеки параллельного программирования, поддержки технологии многозвенного программирования, модулей взаимодействия с DLL и так далее. Единственный компонент, который мне безоговорочно потребовалось разработать за последние два года - инспектор объектов. Для всего остального вполне хватало стандартных компонентов VCL. И это дало свои результаты - стало приятно не только самому смотреть на свой код, но и не стыдно было показать этот код другим людям.
Но нужен был еще один важный инструмент, которого критически недоставало - библиотека контейнеров и алгоритмов. Каждый раз я с тоской вспоминал C++ и STL, но решиться на столь серьезную работу, как портирование STL на почву Delphi, не давали многие факторы. Самым важным среди них был такой - принципиальное отсутствие в Delphi механизма родовых типов (шаблонов). Я не видел способа преодолеть это ограничение. Библиотеки контейнеров, которые мне попадались, предлагали только частные решения. И вот однажды, просматривая sourceforge.net, мне попалась на глаза библиотека DeCAL - было просто удивительно, как я мог пропустить ее раньше, а ведь выпущена она была несколько лет назад. Начав читать документацию, я понял, что это - то самое, недостающее звено. Во всем чувствовался дух STL, и даже реализована библиотека была очень нестандартно, не по-дельфийски.
Уместно спросить - а как же C++ Builder? Конечно, когда появилось сообщение о выпуске этого продукта, я вначале обрадовался, но поработав немного с ним, огорчился. У Buildera совсем не было той элегантности, которая была у Delphi, казалось, что Builder состоит из плохо соответствующих друг другу, каких-то неродных частей. Возможно, это очень субъективное, эмоциональное суждение. Кроме того, мне сразу показалось, что время жизни у Builder'a не будет большим и ориентироваться на него в долгосрочной перспективе не стоит. Последние события, связанные с .Net и C#, подтвердили правильность моих прогнозов, касающихся C++ Builder'a, но, к сожалению, затрагивающих и Delphi. Трудно оценивать эту ситуацию, но, вероятно, программистам просто придется принять это как факт. В этом смысле, является реальностью необходимость перехода на .Net уже в ближайшее время (по крайней мере, ее изучения). Утешает тот факт, что одним из архитекторов C# является Андерс Хейлсберг, разработавший Delphi. Мне хочется думать, что C# станет для .Net тем же, чем был Delphi для Windows.
Тем не менее, до выхода новой версии Windows еще два года, а кроме того, потребность в Windows98-приложениях будет ощущаться еще дольше. Так что расставаться с Delphi пока рановато.
Вот что пишет Росс Джадсон в разделе "Введение" руководства к библиотеке SDL.
Стандартная библиотека Delphi (SDL) от Soletta - мощная библиотека контейнерных повторноиспользуемых классов, обобщенных алгоритмов и удобного механизма обеспечения персистентности. SDL разработана для продвинутых Delphi-программистов, использующих сложные структуры данных или желающих воспользоваться достоинствами большой библиотеки обобщенных алгоритмов. SDL будет прекрасным подспорьем программистам, знакомым с C++ STL (Standard Template Library) или ObjectSpace's JGL (Java Generic Library). SDL - это адаптация идей Степанова и Ли применительно к Delphi.
SDL предлагает множество особенностей, отсутствующих в любой другой библиотеке классов Delphi:
Если вы знакомы с STL или JGL, чтение SDL-документации будет для вас легким. SDL использует те же самые термины, те же самые слова и те же самые идеи. Вы найдете, что она является эффективной адаптацией STL-методологии применительно к Delphi. Вы также найдете, что она делает переход C++ программистов (имеющих опыт работы с STL) к Delphi, более легким.
SDL раздвигает границы Delphi. Завораживает, когда на язык можно воздействовать, чтобы эффективно решать задачи, для которых он не был непосредственно спроектирован. Это - признак зрелого языка и среды проектирования.
Естественно, что мне захотелось поделиться этой находкой с другими программистами, и я решил сделать перевод TUTORIAL AND REFERENCE GUIDE на русский язык, который включается как приложение к этой статье.
В переводе я не стал заменять SDL на DeCAL, на мой взгляд это было бы неэтично. Перевод терминов был согласован с третьим изданием книги "Язык программирования С++" Бьерна Страуструпа (BINOM Publishers, Москва).
Обнаружив, что реализация родовых, обобщенных, свойств библиотеки основана во многом на использовании TVarRec, я несколько засомневался в эффективности DeCAL-контейнеров и для проверки сделал небольшую программу, оценивающую эффективность различных подходов к реализации, примерно соответствующих трем группам библиотек, о которых я говорил в разделе "Контейнерные библиотеки". На испытательном стенде использовались контейнеры:
Вот результаты теста при помещении в контейнер 1.000.000 значений разных типов.
Time TotalAddrSpace TotalAllocated Overhead Integer 1 65 5373952 4376828 12 2 588 21692416 12379980 4000108 3 1088 27983872 24382536 4000016 4 959 14745600 8143120 12 Double 1 425 21692416 12379980 4000108 2 629 24838144 20381736 4000016 3 1154 36372480 32376964 4000012 4 1241 40828928 20143396 4000120 String 1 1686 43581440 24754584 4000112 2 1814 36372480 28373236 8000012 3 2333 47906816 40376720 8000012 4 2986 40828928 24144024 4000124 TObject0 1 591 21692416 12379980 4000108 2 933 27983872 20382956 8000016 3 1537 39518208 32385780 8000012 4 1389 40828928 16146224 4000108 // As Array 5 938 35651584 28008868 8000008 // As List TObject0 (with Pool) 1 351 15597568 12765588 108 2 880 30277632 20768712 4000176 3 1425 36569088 32771252 4000084 4 1265 26542080 16531880 100
Некоторые пояснения к таблице
TObject0 = class public I: Integer; constructor Create(aI: Integer); {$IFDEF TTUSEPOOL} class function NewInstance : TObject; override; procedure FreeInstance; override; {$ENDIF} end;
В целом, результаты оказались достаточно хорошими, существенной неэффективности библиотека DeCAL не продемонстрировала и, в некоторых случаях, она была даже эффективнее интерфейсной реализации. Опять же, повторю, что заботиться об эффективности на ранних фазах проекта не следует, но при завершении проекта это может быть учтено, и то, только после профилирования программы и определения того, что узкое место именно в контейнере. Всегда важно понимать, что нужно обеспечивать эффективность на уровне архитектуры и структур данных, а уже в последнюю очередь - на уровне реализации. И DeCAL помогает в этом, так как практически полностью изолирует наши архитектурные решения от реализации. Например, в начале мы решим, что нас устраивает контейнер, реализованный как массив, потом, при анализе, окажется, что более важны вставка и удаление из любой точки контейнера, и мы можем перейти к списку. Потом, при сопровождении, окажется, что гораздо более важны операции поиска, и мы изменим нашу структуру на ассоциативный массив, реализованный как сбалансированное дерево, дающий почти на любых операциях эффективность порядка O(Log N), если нас устроят повышенные требования этой структуры к памяти. Самое главное состоит в том, что изменение структуры данных возможно (в самом простом случае) изменением только одной строки в программе, в которой указывается тип контейнера.
Хотя контейнеры и итераторы - это важная часть библиотеки DeCAL, другой, не менее важной частью, являются алгоритмы. Те, кто знаком с STL, поймут, в чем дело, а для тех, кто не знаком, поясню. Алгоритм - это функтор или функция, реализующая некоторое стандартное, повторноиспользуемое действие. Примеры алгоритмов - сортировка, подсчет, фильтрация, преобразование, ротация, поиск и так далее. Аргументы алгоритмов - это, как правило, итераторы, поэтому алгоритмы могут работать практически с любыми видами контейнеров. В некотором смысле алгоритмы напоминают паттерны проектирования. Общее между ними состоит в том, что и те и другие предлагают повторноиспользуемое решение некоторой часто встречающейся задачи. Другое общее их свойство в том, что они дают разработчику некоторый стандартный словарь, позволяя в достаточно общеупотребительных терминах выражать свое намерение. В отличие от паттернов, предлагающих крупные архитектурные решения, алгоритмы работают уже внутри этих решений, предлагая скорее тактику, чем стратегию.
Перевод документа "STANDARD DELPHI LIBRARY. TUTORIAL AND REFERENCE GUIDE" на русский язык. Оригинальный документ поставляется в формате pdf (guide.pdf). Перевод представлен как chm-справочный файл (sdl.chm), снабженный оглавлением, поисковыми индексами и кнопками последовательной навигации, которые удобно использовать при чтении документа как книги.
sdl.zip - Архив содержит файл SDL.chm и сам пакет DeCAL (312K).