List Commands Library for 50g

03102018, 11:09 PM
Post: #273




RE: List Commands Library for 50g
I thought it might be useful to show an example of where the ListExt library commands can be used to support a "listcentric" approach to solving a problem which would typically be addressed with an iterative processing approach. It also helps to show where performance gains are made (and not).
The problem description: Quote:Write a UserRPL program to convert an exact integer to a string, with thousands separators inserted at appropriate intervals (choose whatever character you prefer to separate the digits). I'll first create a program using only standard RPL commands, using a method that doesn't use lists. I start off by converting the number to a string, then determine how many digits to output before the first separator: Code: @ part 1 Next I want to preload the stack by splitting the current string into two parts as identified by the number computed above: Code: @ part 2 Now I simply create a loop to repeatedly create a separator followed by a chunk of 3 digits, which is then appended to the "workinprogress" string. This repeats until all digits are appended: Code: @ part 3 A final DROP is required because the above loop needed an empty string to act as a sentinel for exiting. Code: @ part 4 So the final program looks like this: Code: \<< The program requires an exact integer as input (reals aren't handled properly), and assumes a comma as the separator (feel free to use a space, period, backquote, or whatever your favorite character may be). It gives reasonable output for numbers <1000, and properly handles the initial digits as described above. A test case using the exact integer 123456789 results in a string of "123,456,789" in about 0.11s on my 50g. I'm sure that there's lots of other standard UserRPL approaches, and I have no doubt that the denizens here could find smaller/faster/more elegant ways to do the same thing. But this helps to show a comparison with the listfocused approach that follows. Looking at this with a "list bias", it occurs to me that there's two parts to the result: the initial digits, and a list of separated groups. So I start off by determining the initial digits in the same fashion as before: Code: @ part 1 Now I get to use the first ListExt command: SPLIT. It directly takes the place of the previous construct that split the string into two pieces: Code: @ part 2 Presuming there are more than an initial group of 13 digits, the rest fit into a nice repeating pattern: ",<3digits>,<3digits>...,<3digits>". I simply need to construct that pattern with the given digits, and in this case I use the list commands to make that happen. I start off by grouping the digits (which are currently characters in a string) into groups of 3: Code: @ part 3 The result of the above is a list containing all of the remaining digits as 3character sublists. Using the sample integer from above, stack level 1 now contains: { { "4" "5" "6" } { "7" "8" "9" } } Now I need to preface each sublist in the current list with a separator character. This could be done several different ways, but I'll use some commands that tend to be good performers in situations like this. Notably, I plan to use LCLLT to "collate" the current list with a list of separators of the same dimension. That implies that I first need to create the list of separators: Code: "," OVER SIZE RPTCHR S\>SL Now I'm going to use LCCLT to regroup the separators into a list paired up with the 3digit sublists. Since the separators need to be in front of the digit sequences, I swap the two lists before collating them: Code: SWAP 2 \>LIST LCLLT Using the same sample as before, stack level 1 now contains: { "," { "4" "5" "6" } "," { "7" "8" "9" } } A command that I use surprisingly frequently explodes the inner sublists of the list (LXIL  eXplode Inner Lists). This then leaves one final step to combine all of the individual characters into a final string (SL→S). So this segment becomes: Code: SWAP 2 \>LIST LCLLT Now the stack contents for the example case are: 2: "123" 1: ",456,789" So a final + appends the two strings for the final result: "123,456,789" The finished listfocused version of the program is as follows: Code: \<< The list version isn't as straightforward (IMHO), and is even slightly slower than the standardRPL version for 123456789 at 0.19s (vs. 0.11s for the previous version). So what is the point? Why use it? It may not have been obvious when going through the construction of the second program in pieces, but there's a fairly major difference between the two approaches: the listfocused one doesn't have a single UserRPL loop in it. The internals of the individual commands use loops, of course, but they are always being executed at either SysRPL or Saturn speeds. Using a small integer like 123456789 means that the UserRPL program only has to loop through the substrings twice after biting off the first 3 digits. That's why it can produce a result relatively quickly. It turns out that the two approaches perform similarly once the number of digits in the program's argument reaches about 20. The listfocused version scales quite well, though, and achieves much faster results than the standard one as the digit counts grow. An exact integer of 1000 digits takes about 8.92s using the looped standardRPL version of this program. The listfocused version provides the answer in 0.62s. As a general concept, the same kind of results apply to many of the ListExt commands. Very short/small arguments may not show much advantage (or actually be slightly slower) than traditional processing methods. But as list/string sizes grow, the performance advantages improve substantially. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)