List Commands Library for 50g

[DavidM]

Playing around with some other things, it occurred to me that I could benefit from having an equivalent to LSPLT/LRPSL for strings. It was actually pretty simple to overload the existing commands to accommodate strings as well (most of the code was shared between the two object types).

The "L" at the beginning of these command names designates their use for lists, which is no longer the only object type they apply to. Keeping the LSPLT/LRSPL commands names makes sense for backward compatibility, but I'm wondering if it makes sense to create aliases for these commands now that they apply to strings as well. SPLIT and RSPLT perhaps?

Thoughts? Are the aliases even needed?

[John Keith]

(03-03-2018 08:35 PM)DavidM Wrote:  Playing around with some other things, it occurred to me that I could benefit from having an equivalent to LSPLT/LRPSL for strings. It was actually pretty simple to overload the existing commands to accommodate strings as well (most of the code was shared between the two object types).

The "L" at the beginning of these command names designates their use for lists, which is no longer the only object type they apply to. Keeping the LSPLT/LRSPL commands names makes sense for backward compatibility, but I'm wondering if it makes sense to create aliases for these commands now that they apply to strings as well. SPLIT and RSPLT perhaps?

Thoughts? Are the aliases even needed?

I strongly approve of overloading those commands (and any others that make sense) to work with strings. I would go in the opposite direction, however, and have SPLIT / RSPLT be the "official" command names and LSPLT/LRPSL be the aliases.

Many built-in commands (e.g. POS and SUB) work with strings and lists. SIZE also works with arrays and exact integers. It has always annoyed me that SREV and REVLIST are two different commands. With Gerald Hillier's ZREV, we now have 3 different command names that should have been one all along.

Basically, the point of my rant is to encourage combining useful operations into as few commands as possible. :-)

John

[pier4r]

(03-03-2018 11:07 PM)John Keith Wrote:  Basically, the point of my rant is to encourage combining useful operations into as few commands as possible. :-)

John

But then one has to be careful checking the input. I'm in for precise commands that are freed from checking the input. Unless doing the input check is easy.

[DavidM]

(03-04-2018 09:01 AM)pier4r Wrote:  But then one has to be careful checking the input. I'm in for precise commands that are freed from checking the input. Unless doing the input check is easy.

Checking argument counts and types is much easier in SysRPL than in UserRPL (IMHO). There are standardized structures for this, and all well-written SysRPL programs can and should use them. Function overloading is common throughout the command set of the 48-50 systems, so following that practice makes sense to me wherever possible.

What John is suggesting seems reasonable, and could be done with no impact to existing UserRPL programs. While there's a distinct difference in the source code of the library between command labels vs. aliases, changing the "official" names of the commands and keeping the old ones as aliases wouldn't require anyone to alter their own programs. An interesting side effect would be that any programs saved on your calculator when you replace the library with the newer version would automatically have instances of LSPLT/LRSPL changed to SPLIT/RSPLT the next time you edit or recall them to the stack. Source code saved as text would keep the old names, of course, but those commands would now be aliases for the newly-named versions. So at this point I don't really see much of a downside to changing the names in this manner.

[pier4r]

Thanks for sharing, then go for it. If the input checking routines already there, tested and easy to use, why not.

[DavidM]

(03-04-2018 04:51 PM)pier4r Wrote:  Thanks for sharing, then go for it. If the input checking routines already there, tested and easy to use, why not.

Of course, now I have another dilemma: seems like I should also accommodate reals and exact integers as well for SPLIT/RSPLT. Much to my dismay, it actually makes sense to do those -- it's easy to see where they could be useful. Gets a bit more complicated, though.

What should the proper result be if the following is attempted?

123.456 2 SPLIT
(I'm guessing most would expect 12 3.456)

Ok, now how about:

123.456 4 SPLIT
or
1.23456E99 4 SPLIT
or
123.456E3 4 SPLIT

...at least exact integers seem a bit more straightforward to interpret. There's just one "wrinkle" I can think of, and it also applies to reals: when the "split point" is at either end of the number, the "opposing chunk" needs to have some kind of value, and to me it seems like it should be 0. That would be in keeping with the list and string versions, which create null versions of their base type. 0 seems like the most reasonable choice for a numeric "null" in this situation.

Edit: just thought of another wrinkle: negative numbers! If a negative number is split, should either/both/none of the results be negative?

[John Keith]

I can't see an easy and obvious solution for splitting integers, and I would be pleased as punch if these commands could just split integers.

If a negative integer is split, I think that both halves should be negative. I also agree that if the split point is <= 0 or >= the size of the integer, the other "part" should be 0, but I am willing to listen to counter arguments.

John

[DavidM]

(03-05-2018 09:33 PM)John Keith Wrote:  I can't see an easy and obvious solution for splitting integers, and I would be pleased as punch if these commands could just split integers.

If a negative integer is split, I think that both halves should be negative. I also agree that if the split point is <= 0 or >= the size of the integer, the other "part" should be 0, but I am willing to listen to counter arguments.

John

I'm guessing you meant "I can't see an easy and obvious solution for splitting reals", based on the context of the original question. Please let me know if I'm assuming incorrectly.

After thinking about this some, I'm wondering if reals could be handled in a similar fashion to integers, but with the following conditions:

• only the integer part of the argument is considered
• |real| must be <= 999999999999.
  

It seems like that may cover the majority of situations where this would be useful, and would simply throw a "Bad Argument" error if the exponent were larger than 11. Handling it this way also keeps the user from having to worry about the numeric type when the range of possible values is already known to be small enough.

Still pondering the sign issue. I can't really think of a use case where preserving the sign is important, so it's difficult for me to guess at which option covers more scenarios.

The extra processing for these commands will slow them down slightly, but hopefully the added convenience will outweigh any performance considerations in the long run.

[John Keith]

Yes, you assume correctly. :-) I posted as I was on my way out the door.

And no, I can't really think of a case where preserving the sign is important either.

I am fairly "speed obsessed" and if dealing with reals and negative numbers will slow the commands down I can live without them quite easily.

John

[DavidM]

(03-07-2018 08:35 PM)John Keith Wrote:  I am fairly "speed obsessed" and if dealing with reals and negative numbers will slow the commands down I can live without them quite easily.

Performance should still be fairly good, even with numeric arguments. I've got a handler for exact integers that can split a 2000-digit number into two 1000-digit integers in about 0.037s.

I also have a SysRPL version of a handler for reals that works under the previously-mentioned constraints, but it's not very efficient and slower than I'd like. I'm planning to replace it with a Saturn-based code object instead. Just have to get caught up on a couple other things first.

[John Keith]

(03-08-2018 11:14 PM)DavidM Wrote:  I've got a handler for exact integers that can split a 2000-digit number into two 1000-digit integers in about 0.037s.

Cooool.

[DavidM]

SPLIT is now a tiny bit slower than my previous report due to an extra step being required to handle results that would contain leading 0s for numeric arguments. Still reasonably fast, though. Approximate numbers (reals) are handled as was previously described:

• only the integer part of the argument is considered for splitting
• |real| must be <= 999999999999.
  

The first post in this thread has now been updated to contain what I hope to be the final beta release before a general release of version 1.1.3.

I've attempted to consider a wide range of arguments while testing SPLIT and RSPLT, but there may be some that I've missed. I'd be most appreciative if those commands could receive some extra attention for anyone willing to check them out. Here's the updated command descriptions for those two:

______________________________________________________________________________

SPLIT (List/String/Number Split)
(aliases: LSPLT, LSPLIT)

Input
2: { a list of 0 or more objects } or "String" or number
1: integer (first group size)

Output
2: { the designated objects } or "First Substring" or first sub-digit number
1: { the objects after the designated list } or "Last Substring" or last sub-digit number

Splits a list, string, or number into two parts where the length of the first object is given as the numeric argument. The result is both sub-objects as separate stack entries. A negative group size is treated the same as 0. A group size greater than the number of elements in the object will be treated the same as the object length. If the group size argument equals the object size, the object and an empty object are returned. If 0, an empty object and the object are returned. Only the integer part of approximate numbers are considered, and the absolute value of those must be less than 1E12. The sign of numbers is maintained for both constituent parts in the result.

Examples:
{ a b c d e f g h i j k l m n o p } 5 SPLIT => { a b c d e } { f g h i j k l m n o p }
{ a b c d e } 5 SPLIT => { a b c d e } { }
{ a b c d e } 0 SPLIT => { } { a b c d e }
{ a b c d e } 99 SPLIT => { a b c d e } { }

"ABCDEFG" 2 SPLIT => "AB" "CDEFG"
"ABCDEFG" 0 SPLIT => "" "ABCDEFG"
"ABCDEFG" -99 SPLIT => "" "ABCDEFG"
"ABCDEFG" 99 SPLIT => "ABCDEFG" ""

123456789 3 SPLIT => 123 456789
-555 8 SPLIT => -555 0
123000456 3 SPLIT => 123 456
123456.789 2 SPLIT => 12. 3456.
100000. 5 SPLIT => 10000. 0.


______________________________________________________________________________

RSPLT (List/String/Number Right Split)
(aliases: LRSPL, LSPLITR)

Input
2: { a list of 0 or more objects } or "String" or number
1: integer (second group size)

Output
2: { the objects prior to the designated list } or "First Substring" or first sub-digit number
1: { the designated objects } or "Last Substring" or last sub-digit number

Splits a list, string, or number into two parts where the length of the second object is given as the numeric argument. The result is both objects as separate stack entries. A negative group size is treated the same as 0. A group size greater than the number of elements in the object will be treated the same as the object length. If the group size argument equals the object size, an empty object and the object are returned. If 0, the object and an empty object are returned. Only the integer part of approximate numbers are considered, and the absolute value of those must be less than 1E12. The sign of numbers is maintained for both constituent parts in the result.

Examples:
{ a b c d e f g h i j k l m n o p } 5 RSPLT => { a b c d e f g h i j k } { l m n o p }
{ a b c d e } 5 RSPLT => { } { a b c d e }
{ a b c d e } 0 RSPLT => { a b c d e } { }
{ a b c d e } 99 RSPLT => { } { a b c d e }

"ABCDEFG" 2 RSPLT => "ABCDE" "FG"
"ABCDEFG" 0 RSPLT => "ABCDEFG" ""
"ABCDEFG" -99 RSPLT => "ABCDEFG" ""
"ABCDEFG" 99 RSPLT => "" "ABCDEFG"

123456789 3 RSPLT => 123456 789
-555 8 RSPLT => 0 -555
123000456 3 RSPLT => 123000 456
123456.789 2 RSPLT => 1234. 56.
100000. 5 RSPLT => 1. 0.


______________________________________________________________________________

[DavidM]

I thought it might be useful to show an example of where the ListExt library commands can be used to support a "list-centric" 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
  \->STR
  DUP SIZE 3 MOD
  3 OVER NOT * +

→STR should come as no surprise to anyone, but what follows is a bit more twisted due to the nature of how such numbers are usually written. It should be more or less intuitive that the first chunk of digits is the "remainder" of digits after the rest have been grouped into 3s from the right. But we don't put the first separator at the beginning of a number if it contains an even multiple of 3 digits, so I don't really want a pure "MOD" result here. The method I've used gives me 3, 1, or 2 as a result instead of 0, 1, or 2.

Next I want to pre-load the stack by splitting the current string into two parts as identified by the number computed above:

Code:

  @ part 2
  DUP2 1 SWAP SUB UNROT
  1 + OVER SIZE SUB

Now I simply create a loop to repeatedly create a separator followed by a chunk of 3 digits, which is then appended to the "work-in-progress" string. This repeats until all digits are appended:

Code:

  @ part 3
  WHILE DUP SIZE REPEAT
    "," OVER 1 3 SUB +
    ROT SWAP + SWAP
    4 OVER SIZE SUB
  END

A final DROP is required because the above loop needed an empty string to act as a sentinel for exiting.

Code:

  @ part 4
  DROP

So the final program looks like this:

Code:

\<<
  @ part 1
  \->STR
  DUP SIZE 3 MOD
  3 OVER NOT * +
  
  @ part 2
  DUP2 1 SWAP SUB UNROT
  1 + OVER SIZE SUB
  
  @part 3
  WHILE DUP SIZE REPEAT
    "," OVER 1 3 SUB +
    ROT SWAP + SWAP
    4 OVER SIZE SUB
  END
  
  @ part 4
  DROP
\>>

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 list-focused 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
  \->STR
  DUP SIZE 3 MOD
  3 OVER NOT * +

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
  SPLIT

Presuming there are more than an initial group of 1-3 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
  IF DUP SIZE THEN
    S\->SL 3 LSDIV

The result of the above is a list containing all of the remaining digits as 3-character 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 3-digit 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
    LXIL SL\->S

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 list-focused version of the program is as follows:

Code:

\<<
  @ part 1
  \->STR
  DUP SIZE 3 MOD
  3 OVER NOT * +
  
  @ part 2
  SPLIT
  
  @ part 3
  IF DUP SIZE THEN
    S\->SL 3 LSDIV
    "," OVER SIZE RPTCHR S\->SL
    SWAP 2 \->LIST LCLLT
     LXIL SL\->S
  END
  
  @ part 4
  +
\>>

The list version isn't as straightforward (IMHO), and is even slightly slower than the standard-RPL 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 list-focused 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 list-focused 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 standard-RPL version of this program. The list-focused 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.

[John Keith]

Excellent, David! SPLIT is impressively fast for integers and even faster for strings.

Your above explanation is enlightening and illustrates well the power of the Library.

I have another little program here which finds all the Kaprekar numbers up to 1000:

Code:


\<< 0. 1 1000
   FOR n n DUP SQ DUP SIZE 2. / IP SPLIT + SAME
      { 1. + n SWAP } IFT
   NEXT \->LIST
\>>

Takes about 42 seconds (less than one second on the emulator), which is 2-1/2 to 3 times as fast as my best program using previous versions of the Library. Without ListExt commands it would be very slow indeed.

[DavidM]

(03-11-2018 09:30 PM)John Keith Wrote:  I have another little program here which finds all the Kaprekar numbers up to 1000:

Code:


\<< 0. 1 1000
   FOR n n DUP SQ DUP SIZE 2. / IP SPLIT + SAME
      { 1. + n SWAP } IFT
   NEXT \->LIST
\>>

Takes about 42 seconds (less than one second on the emulator), which is 2-1/2 to 3 times as fast as my best program using previous versions of the Library. Without ListExt commands it would be very slow indeed.

I'd love to feel good about that, but unfortunately I believe the SPLIT command is probably the primary time consumer in your loop. Even the following simple scenario takes a little over 30s on a 50g:

Code:

\<<
  1 1000 FOR n
    n 2 SPLIT DROP2
  NEXT
\>>

SPLIT started out in life as a simple SysRPL "helper" command that took the place of doing 2 separate SUBs on a list. That structure is still in place, but it now also notes the original argument type and branches to type-specific SUB commands as needed (list, string, real, or zint). The first two of those are built-ins, the last two are custom-designed Saturn code. So any invocation of SPLIT (or RSPLT) is functionally equivalent to two consecutive SUB commands with a little pre-work being done to determine the indices.

[John Keith]

Even so, the UserRPL equivalent of SPLIT requires several commands and makes the program larger and more cluttered. There are a few other ListExt commands that are a bit slower than UserRPL equivalents but are valuable for the same reason. Not that I would complain if any of them were faster, of course. :-) The HP 50 is not exactly a speed demon and needs all the help it can get.

John

[DavidM]

(03-13-2018 08:37 PM)John Keith Wrote:  Even so, the UserRPL equivalent of SPLIT requires several commands and makes the program larger and more cluttered. There are a few other ListExt commands that are a bit slower than UserRPL equivalents but are valuable for the same reason. Not that I would complain if any of them were faster, of course. :-) The HP 50 is not exactly a speed demon and needs all the help it can get.

John

Yes, you're right of course. I think it's the fact that SPLIT invokes two separate SUB-like steps that bothers me. Splitting things in one step could be done, but it would significantly increase the code size (which is already bigger than I'd like).

I remember having some discussion at some point about a couple of "convenience commands" that weren't good performers, but right now can't recall which ones they were. If you happen to notice commands that fit in this category, please let me know and I'll add them to my list of things to check for possible updates. In the meantime I'll try to dig back and figure out what those were.

[John Keith]

As far as I remember they were LFRST, which is just 1. SWAP SUB, and LPUSH, which is SWAP +. I'm at work now and don't have my notes available, but I'll check tonight if I have time.

John

[DavidM]

(03-15-2018 08:21 PM)John Keith Wrote:  As far as I remember they were LFRST, which is just 1. SWAP SUB, and LPUSH, which is SWAP +. I'm at work now and don't have my notes available, but I'll check tonight if I have time.

John

I found an old PM where we were discussing a prior version of LFRST that was definitely slower than 1. SWAP SUB. That prior version was sharing some code with LLAST, and the overhead was getting in the way. The current version is completely independent, and essentially uses the same internal code as 1. SWAP SUB and performs the same or slightly better in the tests I just tried. LFRST does do one extra thing, though. It checks to see if the argument you give it is negative, in which case an error is generated. 1. SWAP SUB simply gives you an empty list for that kind of input.

LPUSH is actually the simplest command in the entire library. After checking the arguments (2: list, 1: anything), it executes a single SysRPL command: >HCOMP. It was faster than SWAP + in the couple of checks I just tried (though just by a very small amount). I believe I was inclined to keep that command as a logical partner to LPOP, even though in a program it consumes 5.5 bytes as opposed to SWAP + which only takes 5 bytes.

We also discussed LSEQ in those exchanges, which now has a significant speed advantage (as do the other sequence commands). And LNDUP, which no longer exists . LMRPT now does what LNDUP used to do, as well as its original stated purpose (repeating the contents of a list multiple times).

I'm pretty sure that was the discussion I was remembering. I'll stay on the lookout for others, though.

[pier4r]

I do not know if LSHUF is changed much since 1.1.0d (that is in one of my 50g, as I hadn't the need to update it), but it seems to behave a bit differently than random picks.


Setup.

You have a list with elements { 1 2 3 4 }

You want to pick elements from this list until they match a certain combination. Say { 1 2 4 3 1}

If I use (this in a loop)

Code:


1 goalSize
START
  listElements LSHUF HEAD
NEXT
goalSize \->LIST
goal ==

vs

Code:


1 goalSize
START
  listElements listElementsSize RAND * 1 + IP GET
NEXT
goalSize \->LIST
goal ==

with a check to stop if trying more than
listElementsSize goalSize ^ 2 *
attempts, for the test done by me LSHUF is never successful, while the approach with rand return a result in approximately (over a lot of repetitions)
listElementsSize goalSize ^ 0.3 *
attempts.

A known issue? Maybe LSHUFdoesn't really work with small lists?