A Better Solution

While despritately trying to save his thesis, the student encountered another student who was fluent in a different programming language. The language the second student used was APL, a language unfortunately not widely used any more. However, the arguments comparing APL and FORTRAN given then mirror in a curious fashion the arguments still heard in comparing Java and C++. APL was an interpreted language, while FORTRAN was compiled. For simple tasks APL had much slower execution, although development time was often much faster. Thus, APL was often dismissed as a toy language, while FORTRAN was the language of choice for ``serious'' programmers.

Nevertheless, the APL programmer decided to try her hand at the problem. However, she approprached it from an entirely different persepective. Rather than thinking about the data as a single one-dimensional vector, she restructured the data into a two-dimensional matrix. Each row of this matrix would have M elements. The first row would have the first M values, the second would begin the M values that started at position 2 (note the overlap), and so on.

After constructing this matrix, the APL programmer then sorted the matrix by rows. If any sequence was repeated, it would appear as two adjacent rows with the same values. This was quite easy to detect.

The biggest surprize, however, lay in execution time. The new program, even though it was interpreted, ran in a fraction of the time required by the FORTRAN program. The thesis was saved, and the first student was thrilled.

[audio] [real] Text to accompany slide07, in Chapter 1 of An Introduction to Object-Oriented Programming