The Role of Dynamic Programming & Control Structures in Performance

[This article originally appeared as a tutorial in the ACM SIGAPL APL95 Conference Proceedings.]

Dynamic programming is used infrequently by APL programmers, in spite of its ability to reduce the computational effort required to solve many problems. This paper uses the {\em String Shuffle} problem as the basis for a comparison of brute force, recursive, and dynamic programming algorithms. Simple algorithms for each of these approaches are designed and evaluated, then individually optimized and re-evaluated, to show the benefits of dynamic programming. The dynamic programming algorithm is then recast to use flow control structures recently introduced into ISI J and APL*PLUS~III. Use of control structures in conjunction with dynamic programming results in orders of magnitude performance improvement over brute force and naive recursive algorithms. APL*PLUS~III control structures are shown to provide a performance improvement of up to 30\% over GOTO-based loops. ~ ~

The profiling article is available in PDF (141k) format and in PostScript (365k) format.