List Commands Library for 50g

[pier4r]

Collecting some results about RAND * CEIL (as reference against the other commands).

Measuring distances from the original position.

https://app.assembla.com/spaces/various-...esults.txt

I will add there the results of the other commands as soon as I am able to.

[DavidM]

(04-02-2018 08:51 AM)pier4r Wrote:  Finding the min and maximum of a list. LMAX and LMIN. It would suprise me if no one asked for this before.
...
Therefore
inputList DUP LSORT 1 LLAST
SWAP OVER MPOS

and
inputList LSORT HEAD
SWAP OVER MPOS

In the past I've used the following:

« MAX » STREAM
« MIN » STREAM

...to find the max and min values of a list. It's both small and efficient. A list of 500 reals can be completed in about 0.75s with either of these.

Creating specialized functions for these would take up room with little (if any) performance gain, so I guess I've never been inclined to consider something like that for the library.

STREAM is a built-in list processing command that doesn't get quite as much attention as its cousins, but it's actually a good performer. It was the first command that I recall looking at (with Nosy) that used the technique of pushing a list onto the RPL return stack in order to step through its contents one element at a time. Used in the proper context, this is a very effective way to traverse a list's contents in SysRPL programs.

[pier4r]

nice ones with stream.

Added http://www.wiki4hp.com/doku.php?id=rpl:s...=revisions

[ttw]

<< <<MAX>>Stream>> and the corresponding MIN work very well except that they fail with lists of a single element, lists of no elements, non-list variables, and an empty stack. None of these are a particular problem but for a general purpose code, they are insufficient. What does happen is that in the small cases, 0, one, or null elements, one spends much more time testing than in taking extrema. I try to code around this on the HP50g by special-casing small cases. I'm not sure what the MAX of an empty list should return. The smallest value representable is the "identity" of the MAX function as 0 is for addition and 1 for multiplication.

[DavidM]

(04-04-2018 03:56 AM)ttw Wrote:  << <<MAX>>Stream>> and the corresponding MIN work very well except that they fail with lists of a single element, lists of no elements, non-list variables, and an empty stack.

...which puts those constructs in good company with the rest of the built-in list functions that also get wonky in edge cases. You make good points, though. Perhaps a slightly longer version would still be versatile:

Code:

DUP 1 GET + « MAX » STREAM

That doesn't cover a null list, but I'd be happy with an error in that case anyway. And while there's a bit of risk using "+" here, I believe it should be OK for any object types that MAX is also OK with. As for the argument checking, that applies to any UserRPL code, doesn't it?

That said, I'm still pondering the merits of creating specialized functions for LMAX/LMIN processing. I've used MAX in particular for lists on several occasions recently.

[DavidM]

(04-04-2018 04:57 PM)DavidM Wrote:  That said, I'm still pondering the merits of creating specialized functions for LMAX/LMIN processing. I've used MAX in particular for lists on several occasions recently.

Ok. It was easy to throw this together for a test. LMAX/LMIN both do the following:

- check the stack for a list argument
- if the list only has one element, return that element
- if the list is empty, STREAM generates "invalid dimension"
- otherwise do the functional equivalent to << MAX/MIN >> STREAM (whichever one was appropriate)

It's a small amount faster than the UserRPL counterpart, mostly because the executable passed to STREAM doesn't need the « » encapsulation. The total code size for all of this is 76 bytes. Is it worth including in the next update?

If so, which menu group makes the most sense? I'm thinking TEST, but LMATH might also be appropriate. I could see either for this.

[pier4r]

Lmath. 76 byte is great and surely the faster code helps in loops.

[DavidM]

After playing around with LMAX and LMIN a bit, I realized something that I hadn't noticed before: MAX and MIN don't support strings. This is a little surprising given that the comparison operators > and < do support them.

In any event, I added string support to LMAX and LMIN. It grew the footprint to 171 bytes, but I think it definitely adds value to the commands and makes adding them to the library even more sensible.

This makes 2 more additions to the new commands since the last release. Others include:

LRPC→: reverses the effect of LRPCT
LPSHR: "right side" version of LPUSH that treats lists the same as any other single object
REV: reverses the elements of a list, string, or number

The updated LSHUF is still being tested. The current version utilizes a SplitMix64 PRNG instead of the built-in RAND results, but the SM64 initial seed still comes from the system seed so that RDZ can be used. I've run a series of Chi-squared distribution tests, as well as a series of Kendall-Tau positional change tests. I've also used Pier's "hit rate" test to validate the results.

All of the testing has been done with the goal of comparing the new method's results with that of a simple (but far slower) implementation that uses a "RAND * CEIL" sequence for randomization with the Fisher-Yates algorithm. So far, all testing has been favorable. I realize that rigorous testing of randomization/shuffle results is a lengthy and involved process, but I have neither the expertise nor the resources to apply any of the larger test suites to this command. If anyone knows of some other simple tests that might be useful, I'm happy to make an attempt. Otherwise, the current tests may have to suffice for now.

If anyone is interested in the approach LSHUF uses, it's essentially this method of the Fisher-Yates shuffle (referred to as the "Modern algorithm" or "Durstenfeld's method"). It also takes into account the need to avoid "modulo bias" as described here.

If testing continues to go well, I'll hopefully have another beta (b5) ready sometime next week.

[ttw]

Adding strings to LMAX and LMIN is a really good idea. String comparisons are very common in lots of programming. It's really useful in processing an input file.

[John Keith]

(04-04-2018 10:41 PM)DavidM Wrote:  Ok. It was easy to throw this together for a test. LMAX/LMIN both do the following:

- check the stack for a list argument
- if the list only has one element, return that element
- if the list is empty, STREAM generates "invalid dimension"
- otherwise do the functional equivalent to << MAX/MIN >> STREAM (whichever one was appropriate)

It's a small amount faster than the UserRPL counterpart, mostly because the executable passed to STREAM doesn't need the « » encapsulation. The total code size for all of this is 76 bytes. Is it worth including in the next update?

If so, which menu group makes the most sense? I'm thinking TEST, but LMATH might also be appropriate. I could see either for this.

Although LSORT HEAD is noticeably faster than MIN STREAM, I think LMAX/LMIN are worth including, especially if they work with strings. Also, one cannot assume that everyone has LSORT on their calculators (although I can't imagine why not).

I also concur that they should go in the LMATH menu.

John

[DavidM]

(04-05-2018 08:30 PM)John Keith Wrote:  Although LSORT HEAD is noticeably faster than MIN STREAM...

LSORT is highly efficient Saturn code that screams through a list and sorts it using Quicksort followed by an Insertion sort once the partition size reaches a certain point. I believe he's creating a hash for the individual elements and then basing the comparisons on the hash. It's a great example of the relative speed that can be obtained using Saturn code vs. SysRPL in this case. The entire list is sorted in less time than it takes a SysRPL loop to step through each list item making a simple comparison. As is his usual, Werner has done a fantastic job with LSORT.

LMAX/LMIN are just SysRPL wrappers that create an executable to pass to the internal STREAM command (which is itself another SysRPL program). The first version simply passed MAX or MIN, but the current version also does a pre-check for string arguments and passes a special subroutine for those.

(04-05-2018 08:30 PM)John Keith Wrote:  I also concur that they should go in the LMATH menu.

Good thing I put them there, then.

Thanks!

[DavidM]

Version 1.1.3b5 is now available in the first post of this thread. There were a few commands added (they have already been discussed in prior messages in this thread), but the biggest change was an overhaul for the randomizing method of LSHUF. My goal was to fix the bias that was found in the previous version, with a quality that is comparable to using a Fisher-Yates shuffle that swaps elements targeted with a "<remaining elements> RAND * CEIL" approach.

Here's the updated command description for LSHUF:

______________________________________________________________________________

LSHUF (List Shuffle)

Input
1: { list of 0 or more objects }

Output
1: { same objects as input, in different order }

Randomizes the order of the elements in the list given as input.

Note: In the examples below, RDZ is used so that the results can be verified. Setting the random seed prior to executing LSHUF is not normally required.

Example:
123456789012. RDZ { 1 2 3 4 5 6 7 8 9 10 } LSHUF => { 7 10 6 2 1 8 3 5 4 9 }
246813579034. RDZ { 1 2 3 4 5 6 7 8 9 10 } LSHUF => { 8 1 4 9 7 2 10 6 5 3 }
135790246865. RDZ { 1 2 3 4 5 6 7 8 9 10 } LSHUF => { 6 8 5 4 3 1 10 2 7 9 }


Technical information about the method LSHUF uses to randomize lists:

Generally speaking, LSHUF explodes the given list, randomizes the resulting stack contents, then implodes the list with the new order. The explosion/implosion steps are simply the built-in SysRPL versions of those commands, but the randomization happens in a custom Saturn assembly language subroutine. The heart of this Saturn subroutine uses a Fisher-Yates algorithm (the "modern algorithm" described in this article: https://en.wikipedia.org/wiki/Fisher%E2%..._algorithm ). The critical part of this method is in selecting a pseudo-random swap target from the available pool of remaining list elements. LSHUF makes use of the SplitMix64 PRNG for this purpose, which is initially seeded by converting the system's default RAND seed to hex notation and performing an initial SplitMix64 cycle. Each iteration of the Fisher-Yates loop generates a new seed which is then shifted right by 4 bits, range-checked for validity (see https://en.wikipedia.org/wiki/Fisher%E2%...odulo_bias ), then reduced to a specific swap target within the current list elements with a simple MOD operation.

LSHUF results have been compared with a similar (but much slower) loop that uses a "<pool size> RAND * CEIL" algorithm for selecting the swap target. Specific tests were performed to check for distribution (using Chi-squared analysis) and Kendall-Tau distance for positional change. LSHUF performed slightly better than "RAND * CEIL" in the distribution tests (250000 samples) and equally in the positional change tests (3000 samples). Additionally, LSHUF was tested using a simple target-matching sequence to see if there were any measurable differences between the two methods for the frequency of random targets being found (2000 samples). No meaningful differences were found.

[pier4r]

Thumbs up!

[ttw]

Depending on the quality of results desired by randomization, I have two methods. Both are reasonably fast. In both methods, the items in each list end up independently of each other item. Thus the permutation is a legitimate "random" sample from the set of all permutations. In one method, (a bit more complicated and the RNG is about 3 times slower), each permutation is independent of the next permutation. In the second method, the permutations are uniformly distributed across the set of permutations. Were one wanting to develop statistics over the set of permutations (like how many next-neighbor-triples there were), the second method give an error about 1/N for N permutations. The first method gives and error of about 1/Sqrt(N).

For example, one may wish to generate statistics of bridge hands. In this case, one would probably want the second method as fewer samples would be required. If a dealing machine were generating hands, the first method would be better as no (even small scale) relations between hands exist.

If there is interest, I'll post the methods (and even an HP50g code) for each case.

[DavidM]

(04-14-2018 12:37 AM)ttw Wrote:  If there is interest, I'll post the methods (and even an HP50g code) for each case.

Please do!

I'd be very interested not only in your methods, but details about how you "score" their quality. I've been trying to find reasonable ways to assess shuffle results lately, so I'm very interested in how you're approaching that aspect.

It would also be good to compare the various methods from a performance standpoint, as it probably makes sense that a relationship exists between the quality and the time it takes to perform the shuffle.

[pier4r]

There is always interest! Post post post!

[John Keith]

Another fun little example of the compactness and elegance of RPL + ListExt: A005150

Code:


\<< 1 1. 24.
   START DUP I\->NL LRPCT REV LCLLT NL\->I
   NEXT 25. \->LIST
\>>

Execution time ~ 22 seconds; the last term has 1182 digits.

John

[DavidM]

(04-17-2018 09:24 PM)John Keith Wrote:  Another fun little example of the compactness and elegance of RPL + ListExt: A005150

Code:


\<< 1 1. 24.
   START DUP I\->NL LRPCT REV LCLLT NL\->I
   NEXT 25. \->LIST
\>>

Execution time ~ 22 seconds; the last term has 1182 digits.

John

That is... strangely cool. A very interesting sequence, and very good use of ListExt commands that almost seem as though they were especially tailored for such a problem.

[John Keith]

(04-18-2018 01:19 AM)DavidM Wrote:  ...ListExt commands that almost seem as though they were especially tailored for such a problem.

That was my thought when I read the description of the sequence.

BTW there is a neat YouTube video in the Links section of the OEIS page that has John Horton Conway discussing this sequence.

[DavidM]

The first post in this thread has been updated with the "official" 1.1.3 release. Only the "About" information has been changed from the previous beta release.

Anyone still using a 1.1.2 release should definitely update to this one. That version (and a couple of the 1.1.3 betas) had a bug that could cause data loss. See the release notes for specifics. Deleting the currently installed ListExt library is a simple matter of selecting the "Unins1423" menu item on page 2 of the ListExt menu. The new library can then be installed in the usual manner.

Thanks to everyone for the suggestions and testing! The library is much better as a result of your efforts.