Programming puzzles: processing lists!

[DavidM]

As promised, I've put together some timing data for the commands in the library I posted recently. The process of measuring and comparing their performance also helped to show where a couple of new commands would be very useful, so I added them to the mix.

For each test, the respective libraries were installed in Port 0 to minimize the impact of code relocation on the final results. The timing process included a forced garbage collection just prior to command invocation in order to "level the playing field" for all commands.

In all of the following tables, the entries in the "50-100-500-1000" columns represent the time required for a single invocation of the command with a list containing the quantity of elements in the column header. The times listed are in seconds. Most commands were tested multiple times (the count designated as "Cycles") and the reported time is an average of all of the tests.

Several of my commands are very similar to GoferList commands, and not surprisingly have similar performance characteristics:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{Repeat} & 0.0188 & 0.0245 & 0.0670 & 0.1195 & 50 \\
\textbf{LNDUP} & 0.0161 & 0.0197 & 0.0477 & 0.0816 & 50 \\
\hline
\textbf{Split} & 0.0183 & 0.0239 & 0.0705 & 0.1257 & 50 \\
\textbf{LSPLT} & 0.0179 & 0.0208 & 0.0451 & 0.0755 & 50 \\
\hline
\textbf{Chars} & 0.0530 & 0.0911 & 0.5576 & 1.1568 & 50 \\
\textbf{S→SL} & 0.0488 & 0.0831 & 0.5237 & 1.0705 & 50 \\
\hline
\textbf{Strcat} & 0.1816 & 0.3429 & 1.6582 & 3.6404 & 50 \\
\textbf{LSUM} & 0.1635 & 0.3137 & 1.5390 & 3.3770 & 50 \\
\hline
\end{array}


A couple more are functionally equivalent, but there were significant differences in performance, especially with larger lists:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{Copy} & 0.1954 & 0.6454 & 41.9425 & 528.8188 & 1 \\
\textbf{LMRPT} & 0.0274 & 0.0319 & 0.0663 & 0.1075 & 50 \\
\hline
\textbf{Nub} & 0.1848 & 0.5596 & 10.9966 & 78.4019 & 3 \\
\textbf{LDDUP} & 0.1368 & 0.4644 & 12.4826 & 135.7304 & 3 \\
\hline
\end{array}

LMRPT uses a Saturn code routine at its core to replicate the needed objects, so I wasn't surprised to see it perform well. LDDUP is simply a wrapper around a built-in ROM command (COMPRIMext). I will spend some time later in an effort to see if I can come up with a faster alternative.


I initially had created commands to convert strings to numeric lists and back (S→NL and NL→S), but saw that the GoferList library approached that concept differently (strings are converted to lists of characters instead). It seemed like both approaches had merit, so I created a similar string list command for my library (S→SL). I didn't see a need for the reverse function, as ΣLIST (which is used by LSUM) handles that job nicely. It's an easy thing to convert a list of characters to numbers by simply passing the list to the built-in NUM command, so I thought I'd see how the combination of GoferList's Chars command followed by NUM compared with S→NL:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{Chars NUM} & 0.2399 & 0.4569 & 2.7059 & 6.1926 & 50 \\
\textbf{S→NL} & 0.0551 & 0.0951 & 0.5922 & 1.2080 & 50 \\
\hline
\end{array}

The reverse of the above functions can easily be tested with another combination (CHR Strcat), and the results took a surprising turn:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{CHR Strcat} & 0.3747 & 0.7166 & 3.8709 & 9.1431 & 10 \\
\textbf{NL→S} & 0.0879 & 0.1654 & 0.9203 & 9.4550 & 10 \\
\hline
\end{array}

Notice the timing of NL→S for a list of 1000 numbers. My suspicion is that a garbage collection is getting triggered during the processing of the large list, as the other list sizes showed much better performance. I will add that command to my list of things to check later for improvement.


The next category of commands could be described as "similar but not functionally equivalent", and is essentially based on GoferList's Zip/Unzip commands. I actually came up with the idea for my similar functions (LCLLT/LDST) before I ever saw the GoferList commands, so they aren't designed to do quite the same things. It's not too difficult to compare them, though, as long as you understand the following:

Zip is designed to handle a specific instance of the type of data that LCLLT can process, and will return results even when the sublists involved aren't the same size. LCLLT requires all sublists to be the same size, but can handle any number of lists. Zip returns its results as a list of sublists, but LCLLT returns all of the data in one single list. So conversions are required in both directions when comparing these complementary functions:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{Zip} & 0.1134 & 0.1863 & 0.8451 & 1.8365 & 50 \\
\textbf{LCLLT DUP SIZE 2 / LSDIV} & 0.0705 & 0.1128 & 0.7510 & 2.0134 & 50 \\
\hline
\textbf{Zip ΣLIST} & 0.2651 & 0.6426 & 21.6099 & 319.9845 & 1 \\
\textbf{LCLLT} & 0.0322 & 0.0426 & 0.1271 & 0.2285 & 50 \\
\hline
\textbf{Unzip} & 0.1468 & 0.2423 & 1.1414 & 2.6013 & 10 \\
\textbf{ΣLIST 2 LDST} & 0.1780 & 0.4396 & 6.5892 & 24.4145 & 10 \\
\hline
\textbf{DROP DUP SIZE 2 / LSDIV Unzip 2 →LIST} & 0.1814 & 0.3041 & 1.7102 & 4.2611 & 5 \\
\textbf{LDST} & 0.0272 & 0.0346 & 0.0948 & 0.1667 & 5 \\
\hline
\end{array}

The above tests had two glaring standouts, and both of them involved the ΣLIST command. This caused me to look more closely at what was happening, and it should come as no surprise that I discovered that using ΣLIST to "explode" the contents of a list of lists was not a good idea. Whereas ΣLIST is good at many things, that particular purpose is not its strongest. And that's putting it nicely. So I opted to create my own version of a command for that purpose: LXIL (List eXplode Inner Lists). It won't win any awards for speed, but compared to ΣLIST it is much faster for its stated purpose:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{ΣLIST} & 0.3333 & 0.9277 & 53.9323 & 658.0647 & 1 \\
\textbf{LXIL} & 0.0527 & 0.1102 & 1.4303 & 4.8115 & 20 \\
\hline
\end{array}

Using LXIL instead of ΣLIST in the above tests gave much better results:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{Zip ΣLIST} & 0.2651 & 0.6426 & 21.6099 & 319.9845 & 1 \\
\textbf{Zip LXIL} & 0.1388 & 0.2382 & 1.4557 & 3.7946 & 10 \\
\hline
\textbf{ΣLIST 2 LDST} & 0.1780 & 0.4396 & 6.5892 & 24.4145 & 10 \\
\textbf{LXIL 2 LDST} & 0.0530 & 0.0866 & 0.7026 & 2.1245 & 10 \\
\hline
\end{array}

...so the final results for the Zip/LDST comparisons became:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{Zip LXIL} & 0.1388 & 0.2382 & 1.4557 & 3.7946 & 10 \\
\textbf{LCLLT} & 0.0328 & 0.0422 & 0.1264 & 0.2272 & 10 \\
\hline
\textbf{Unzip} & 0.1467 & 0.2401 & 1.1347 & 2.5791 & 10 \\
\textbf{LXIL 2 LDST} & 0.0530 & 0.0866 & 0.7026 & 2.1245 & 10 \\
\hline
\end{array}


The final category of testing was simply the commands in my library that had no GoferList counterparts. I thought it would be nice just to see how each command performed with those same list sizes:
\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{LCNT - none matched} & 0.0245 & 0.0347 & 0.1113 & 0.2086 & 20 \\
\textbf{LCNT - 100\% matched} & 0.0334 & 0.0515 & 0.2954 & 0.6088 & 20 \\
\hline
\textbf{LEQ} & 0.0240 & 0.0346 & 0.1189 & 0.2249 & 50 \\
\hline
\textbf{LGRP - Sorted Data} & 0.0304 & 0.0568 & 0.3541 & 1.0933 & 10 \\
\textbf{LGRP - Shuffled Data} & 0.0456 & 0.1030 & 1.2533 & 3.6518 & 10 \\
\hline
\textbf{LRPCT - Sorted Data} & 0.0500 & 0.1068 & 0.7310 & 2.3372 & 10 \\
\textbf{LRPCT - Shuffled Data} & 0.0907 & 0.2513 & 3.1239 & 9.4632 & 10 \\
\hline
\textbf{LREPL - nothing replaced - 1 target} & 0.0716 & 0.1479 & 1.4741 & 5.0333 & 50 \\
\textbf{LREPL - 100\% replaced - 1 target} & 0.0724 & 0.1507 & 1.4747 & 5.0292 & 50 \\
\textbf{LREPL - nothing replaced - 20 targets} & 0.1283 & 0.3022 & 2.2166 & 6.4884 & 50 \\
\textbf{LREPL - 100\% replaced - 20 targets} & 0.1486 & 0.2664 & 2.0512 & 6.1830 & 50 \\
\hline
\textbf{LROT} & 0.0257 & 0.0338 & 0.1008 & 0.1819 & 50 \\
\hline
\textbf{LSDIV} & 0.0611 & 0.1145 & 1.1616 & 3.3086 & 20 \\
\hline
\textbf{LSHF} & 0.2523 & 0.5041 & 2.9164 & 5.9838 & 20 \\
\hline
\textbf{LSWP} & 0.0245 & 0.0309 & 0.0823 & 0.1436 & 50 \\
\hline
\end{array}

The process of going through all of this testing showed me that there was definitely some value in pursuing the development of these additional commands, and even the similar ones to GoferList's have varying degrees of performance improvement in most instances. As a result, I'll continue to refine my contributions and probably add a few more commands before I'm done with it.