Техники визуализации при разработке алгоритмов

Постановка задачи

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

Эксперименты позволяют измерять величину практических индикаторов, таких как константные множители конкретной реализации, узкие места при практическом применении, локальность ссылок, поведение кэша и коммуникационная сложность, которые может оказаться очень сложно предсказать теоретически. К сожалению, как и в любых других эмпирических науках, порой бывает сложно на основе экспериментов сформировать заключения общего характера по поводу алгоритмов. С этой целью некоторые исследователи предложили точные и исчерпывающие рекомендации по различным аспектам эмпирической оценки алгоритмов, сложившиеся на основе их собственного опыта работы в этой сфере (см., например, [1, 15, 16, 20]). В работе [ ] можно найти аннотированную библиографию источников по теме экспериментальной алгоритмики, охватывающую вопросы методологии, инструментов и техник.

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

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

Основные результаты

Системы визуализации алгоритмов прошли долгий путь с момента появления современных интерфейсов компьютерной графики; за последние два десятилетия были разработаны десятки систем визуализации алгоритмов [2, 3, 4, 5, 6, 8, 9, 10, 13, 17, 25, 26, 29]. Комплексный обзор таких систем можно найти в работах [11, 27] и содержащихся в них ссылках. Далее будут рассмотрены функции систем визуализации алгоритмов, представляющиеся наиболее привлекательными для их внедрения в процессах разработки алгоритмов.

Важнейшие проблемы

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

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

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

Инструменты визуализации программного обеспечения должны быть способны анимировать не только «игрушечные» программы, но и весьма сложные алгоритмические коды, и тестировать их поведение на больших наборах данных. К сожалению, даже системам, предназначенным для больших информационных пространств, нередко недостает продуманных механизмов навигации и методов устранения узких мест процесса отображения. Задача устранения этого типа ограничений пока остается нерешенной.

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

Техника

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

Визуализация на основе событий

Естественный подход к анимации алгоритмов заключается в аннотировании алгоритмического кода вызовами подпрограмм визуализации. Первый этап заключается в определении конкретных действий, выполняемых алгоритмом и представляющих интерес с точки зрения визуализации. Такие действия обычно называются интересующими событиями. К примеру, в алгоритме сортировки перестановка двух элементов может считаться интересующим событием. Второй этап заключается в соединении интересующего события с модификацией графического изображения. Сцены анимации можно определить путем настройки подходящих процедур визуализации, управляющих состоянием графической системы в соответствии с актуальными параметрами, генерируемыми конкретным событием. Либо эти процедуры визуализации могут просто записывать журнал событий в файл для их визуализации по окончании выполнения программы. Вызовы подпрограмм визуализации обычно выполняются посредством аннотирования исходного алгоритмического кода в точках, в которых происходят интересующие события. Это можно выполнить вручную либо при помощи специализированных редакторов. Примерами наборов инструментов для реализации подхода на основе событий могут служить Polka [ ] и GeoWin, тип данных C++, способный легко связываться с важнейшими алгоритмическими библиотеками программных модулей – такими как CGAL [ ] и LED A [19].

Визуализация на основе отображения состояний