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

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

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

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

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

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

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

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

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

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

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

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

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

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

Техника

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

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

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

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

Системы визуализации алгоритмов на основе отображения состояний полагаются на предположение, заключающееся в том, что наблюдение изменений переменных дает ключ к действиям, выполняемым алгоритмом. Главной задачей являются захват и мониторинг модификаций данных, а не обработка интересующих событий, выдаваемых аннотированным алгоритмическим кодом. По этой причине такие системы также называются системами визуализации данных, управляемыми данными. Обычные отладчики могут рассматриваться как системы, управляемые данными, поскольку они предоставляют непосредственную обратную связь в ответ на модификацию переменных. Основным преимуществом этого подхода по сравнению с подходом на основе событий является намного большая степень допустимого игнорирования кода: для анимации программы необходимо знать только интерпретацию переменных. С другой стороны, если уделять внимание только модификации данных, это может привести к ограничению возможностей настройки и усложнению процесса создания анимаций, естественным образом отражающих интересующие события. В качестве примеров инструментов визуализации на основе отображения состояний можно привести Pavane [23, 25], ставший воплощением первого изменения парадигмы визуализации алгоритмов с момента появления понятия интересующих событий, и Leonardo [10] – интегрированную среду разработки, визуализации и выполнения программ на C.

Исчерпывающее обсуждение других техник визуализации алгоритмов можно найти в работах [7, 21, 22, 24, 27].

Применение

Техники визуализации при разработке алгоритмов находят применение в таких областях, как тестирование и отладка реализаций алгоритмов, визуальная проверка сложных структур данных, определение узких мест производительности системы и оптимизация кода. Некоторые примеры подобного использования приведены в работе [12].

Открытые вопросы

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

См. также

• Экспериментальные методы анализа алгоритмов

Литература

1. Anderson, R.J.: The Role of Experiment in the Theory of Algorithms. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 59, pp. 191-195. American Mathematical Society, Providence, RI (2002)

2. Baker, J., Cruz, I., Liotta, G., Tamassia, R.: Animating Geometric Algorithms over the Web. In: Proceedings of the 12th Annual ACM Symposium on Computational Geometry. Philadelphia, Pennsylvania, May 24-26, pp. C3-C4 (1996)

3. Baker, J., Cruz, I., Liotta, G., Tamassia, R.: The Mocha Algorithm Animation System. In: Proceedings of the 1996 ACM Work shop on Advanced Visual Interfaces. Gubbio, Italy, May 27-29, pp. 248-250(1996)

4. Baker, J., Cruz, I., Liotta, G., Tamassia, R.: A New Model for Algorithm Animation over the WWW, ACM Comput. Surv. 27, 568-572(1996)

5. Baker, R., Boilen, M., Goodrich, M., Tamassia, R., Stibel, B.: Testers and Visualizers for Teaching Data Structures. In: Proceeding of the 13th SIGCSE Technical Symposium on Computer Science Education. New Orleans, March 24-28, pp. 261-265(1999)

6. Brown, M.: Algorithm Animation. MIT Press, Cambridge, MA (1988)

7. Brown, M.: Perspectives on Algorithm Animation. In: Proceedings of the ACM SIGCHI'88 Conference on Human Factors in Computing Systems. Washington, D.C., May 15-19, pp. 33-38 (1988)

8. Brown, M.: Zeus: a System for Algorithm Animation and Multi-View Editing. In: Proceedings of the 7th IEEE Workshop on Visual Languages. Kobe, Japan, October 8-11, pp. 4-9 (1991)

9. Cattaneo, G., Ferraro, U., Italiano, G.F., Scarano, V.: Cooperative Algorithm and Data Types Animation over the Net.J.VisualLang.Comp. 13(4): 391 - (2002)

10. Crescenzi, P., Demetrescu, C., Finocchi. I., Petreschi, R.: Reversible Execution and Visualization of Programs with LEONARDO. J. Visual Lang. Comp. 11, 125-150 (2000). Leonardo is available at: http://www.dis.uniroma1.it/~demetres/Leonardo/. Accessed 15 Jan 2008

11. Demetrescu, C.: Fully Dynamic Algorithms for Path Problems on Directed Graphs, Ph.D. thesis, Department of Computer and Systems Science, University of Rome "La Sapienza" (2001)

12. Demetrescu, C., Finocchi, I., Italiano, G.F., Naher, S.: Visualization in algorithm engineering: tools and techniques. In: Experimental Algorithm Design to Robust and Effizient Software. Lecture Notes in Computer Science, vol. 2547. Springer, Berlin, pp. 24-50 (2002)

13. Demetrescu, C., Finocchi, I., Liotta, G.: Visualizing Algorithms over the Web with the Publication-driven Approach. In: Proc. of the4th Workshop on Algorithm Engineering (WAE'00), SaarbrCicken, Germany, 5-8 September (2000)

14. Fabri, A., Giezeman, G., Kettner, L., Schirra, S., Schonherr, S.: The cgal kernel: A basis for geometric computation. In: Applied Computational Geometry: Towards Geometric Engineering Proceedings (WACG'96), Philadelphia. Philadelphia, PA, May 27-28, pp. 191-202 (1996)

15. Goldberg, A.: Selecting problems for algorithm evaluation. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99). LNCS, vol. 1668. London, United Kingdom, July 19-21, pp. 1-11 (1999)

16. Johnson, D.: A theoretician's guide to the experimental analysis of algorithms. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59, 215-250. American Mathematical Society, Providence, RI (2002)>

17. Malony, A., Reed, D.: Visualizing Parallel Computer System Performance. In: Simmons, M., Koskela, R., Bucher, I. (eds.) Instrumentation for Future Parallel Computing Systems. ACM Press, New York (1989) pp. 59-90

18. McGeoch, C.: A bibliography of algorithm experimentation. In: Data Struktures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59, 251-254. American Mathematical Society, Providence, RI (2002)

19. Mehlhorn, K., Naher, S.: LEDA: A Platform of Combinatorial and Geometric Computing, ISBN 0-521-56329-1. Cambrige University Press, Cambrige (1999)

20. Moret, B.: Towards a discipline of experimental algorithmics. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59, 197-214. American Mathematical Society, Providence, RI (2002)

21. Myers, B.: Taxonomies of Visual Programming and Program Visualization.J. Visual Lang. Comp. 1,97-123 (1990)

22. Price, B., Baecker, R., Small, I.: A Principled Taxonomy of Software Visualization. J. Visual Lang. Comp. 4, 211-266 (1993)

23. Roman, G., Cox, K.: A Declarative Approach to Visualizing Concurrent Computations. Computer 22,25-36 (1989)

24. Roman, G., Cox, K.: A Taxonomy of Program Visualization Systems. Computer 26,11 -24 (1993)

25. Roman, G., Cox, K., Wilcox, C., Plun, J.: PAVANE: a System for Declarative Visualization of Concurrent Computations. J. Visual Lang. Comp.3,161-193(1992)

26. Stasko, J.: Animating Algorithms with X-TANGO. SIGACT News 23,67-71 (1992)

27. Stasko, J., Domingue, J., Brown, M., Price B.: Software Visualization: Programming as a Multimedia Experience. MIT Press, Cambridge, MA (1997)

28. Stasko, J., Kraemer, E.: A Methodology for Building Application-Specific Visualizations of Parallel Programs. J. Parall. Distrib. Comp. 18, 258-264 (1993)

29. Tal, A., Dobkin, D.: Visualization of Geometric Algorithms. IEEE Trans. Visual. Comp. Graphics 1,194-204(1995)