Post Reply 
List Commands Library for 50g
08-30-2017, 03:33 PM
Post: #101
RE: List Commands Library for 50g
nice work!

I'll try to use it asap with my life gamification backup. (I will have to write about this).

One note:
"Thanks to everyone for your combined efforts at making this a useful collection of commands!"

While it is true that without starting ideas there is no result, I'd say that you deserve a lot of credit because it is true that you listen to the ideas (you could just ignore them) and of course you implement them!

The library is getting really neat and I wonder how many useful commands could be still devised. (I will ask you more about "when do you put some versions on hpcalc-org ?")

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
08-30-2017, 04:55 PM
Post: #102
RE: List Commands Library for 50g
(08-30-2017 03:33 PM)pier4r Wrote:  ...I will ask you more about "when do you put some versions on hpcalc-org ?"

I was hoping that the never-released "1.0.0" version would have been the one. This current one may end up being a good candidate, but I'll feel better about it once others have had a chance to try out the newer commands for their own particular situations. It's not that I'm expecting catastrophic failures in the code, but rather that others may apply the commands in situations that I hadn't anticipated (like John using MPOS on 10-20K length strings). Knowing of John's application prior to my recoding of the command caused me to use an entirely different approach for that particular overloaded function. I don't presume to know in advance what kind of "cans" people will use this "can opener" with.
Find all posts by this user
Quote this message in a reply
08-31-2017, 07:18 PM (This post was last modified: 08-31-2017 07:44 PM by pier4r.)
Post: #103
RE: List Commands Library for 50g
I like the about page, it gets better and better. Now it explains also the complement to goferlist. "compact" meaningful notes are always precious.

Side note. I just thought "hey, since I am involved, let's pick all the discussed library/commands from lists ... well aside those shared on the forum that, while neat, takes a bit of time to be collected, now I want just to pick those I remember from memory". The I have already goferlist and I picked LSORT (that is in saturn assembly. I think also HRAST basic is saturn assembly. Is that emulated as well?). There are nice notes in LSORT, but may be overkill for the list of David. Anyway the notes once again confirm that: shared documentation is better.

Quote:5.To Do

- binary integers
- units
- degeneracy check for Quicksort, switch to Heapsort
- v1.0 will be the first version that incorporates all of the above. From then on
it can be used as a true replacement for the built-in SORT.
- ASORT (array sort) using the same subroutines
- CSORT (column sort)
- ORDERBY (multiple keys)
- LUNIQ (remove duplicates)
- make a lib of the above

I'd say ASORT, CSORT, ORDERBY are nice ideas (units too, but that starts to be professional even though CSORT/ORDERBY are really hard already I think).
LUNIQ is already done IIRC.

For CSORT in terms of lists, I'd imagine a list of sublists (with the same length, like exploding a matrix in lists) and ordering by the n-th element of all the lists.

OrderBY would be similar to Csort actually, just one could give multiple elements in terms of priority. Like "order first the sublists by the 3rd element, then if the 3rd element is equal, use the 4th as tiebreak" and so on.


Moreover it is amazing to see that while a new firmware/language for the hp50g gets developed (newRPL and not only those, some months ago there was HRAST basic), the built in language gets expanded with very nice utilities to this day. Really amazing. I wish every collection of devices that were useful and popular would have the same dedication from the community.

But this was discussed also here: http://www.hpmuseum.org/forum/thread-8204.html

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
08-31-2017, 08:12 PM
Post: #104
RE: List Commands Library for 50g
If I do:

{ 1 1 2 2 } 2 \<< \>> DOCOMB

I get
{ {1 1} {1 2} {1 2} {1 2} {1 2} {2 2} }

Is this result wanted? Well I guess so because it is like combination between entries, regardless of their end value.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
08-31-2017, 11:53 PM
Post: #105
RE: List Commands Library for 50g
(08-31-2017 08:12 PM)pier4r Wrote:  If I do:

{ 1 1 2 2 } 2 \<< \>> DOCOMB

I get
{ {1 1} {1 2} {1 2} {1 2} {1 2} {2 2} }

Is this result wanted? Well I guess so because it is like combination between entries, regardless of their end value.

The number of combinations of n elements taken m at a time is mathematically defined as: \[C_{n,m} = \frac{n!}{m!\cdot(n-m)!}\]

This is the same equation that the built-in COMB command uses. Any result for DOCOMB that had a different number of combinations sent to the user program would simply be wrong (IMHO).

What to do about duplicates in the result list (if anything) is entirely dependent on the problem itself, and should not be assumed by the internals of DOCOMB. Same applies to DOPERM. Depending on the problem, those duplicates may actually be exactly what you are looking for.
Find all posts by this user
Quote this message in a reply
09-01-2017, 04:00 AM (This post was last modified: 09-01-2017 04:01 AM by Joe Horn.)
Post: #106
RE: List Commands Library for 50g
(08-31-2017 11:53 PM)DavidM Wrote:  The number of combinations of n elements taken m at a time is mathematically defined as: \[C_{n,m} = \frac{n!}{m!\cdot(n-m)!}\]

This is the same equation that the built-in COMB command uses.

Not possible, for two reasons:

Reason 1:
999 995 COMB --> 41251456251 (correct) in 0.042 seconds.
But 999! alone takes 28.8 seconds. COMB can't be using factorials.

Reason 2:
999. 995. COMB --> 41251456251. (correct)
But 999.! overflows. COMB can't be using factorials.

My gut feeling is that COMB's speed and accuracy suggest that it's calculating COMB(999,995) in this order (straight through, left to right):

999/1*998/2*997/3*996/4.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
09-01-2017, 05:29 AM
Post: #107
RE: List Commands Library for 50g
(08-31-2017 11:53 PM)DavidM Wrote:  What to do about duplicates in the result list (if anything) is entirely dependent on the problem itself, and should not be assumed by the internals of DOCOMB. Same applies to DOPERM. Depending on the problem, those duplicates may actually be exactly what you are looking for.

Yeah that's a good point. Fortunately your great library as LDDUP so no problem.

I am not sure you checked it but I'd like to know if you would have done the program here (that is using your library a lot) http://www.hpmuseum.org/forum/thread-892...l#pid78250 differently.

I paste it here

Code:
OEISA014261
  @see www.hpmuseum.org/forum/thread-8928.html
  @in practice we should generate all the positive integers not containing
  @even digits.
  @Those small challenegs are nice because are not overwhelming and still can be
  @approached in many ways.
  
  @listExt of DavidM
  @LSORT from hpcalc
  \<<
    @Input: N
    @Output: Nth number in the sequence.
  
    @Plan
    @ combining digits 1 3 5 7 9 in increasing way.
    
    @so making heavy use of the awesome list library of david.
    @I can just generate tuples and sort them.
    
    { 1 3 5 7 9 } "baseList" DROP
    { } "currentIterBaseList" DROP
    {} "currentIterationList" DROP
    1 "digitsInIteration" DROP
    0 "mthGeneratedNumber" DROP
    0 "skippedNumbers" DROP
    
    \->
    @input
    valueN
    
    @local var
    baseList
    currentIterBaseList
    currentIterationList
    digitsInIteration
    mthGeneratedNumber
    skippedNumbers
    \<<
      IF
        valueN 1 > NOT
      THEN
        0
      ELSE
        WHILE
          valueN 5 digitsInIteration ^
          >
        REPEAT
          'skippedNumbers' 5 digitsInIteration ^ STO+
          'digitsInIteration' 1 STO+
        END

        @generate a source list with enough digits 
        @(small limits of the current version of the list library of davidM)
        @in general to generate 111 we need 3 "1" in the list, so
        baseList digitsInIteration LMRPT 'currentIterBaseList' STO
          @can we use sorted? so we have the numbers generated in order?
          @nu. Generating a list from sorted input list and then removing duplicates
          @does not help. This may be a request for another command similar to DOPERM
        
        @generate all the permutations of the elements, turn them in numbers
        @clear the equal ones
        currentIterBaseList digitsInIteration 
        \<< NL\->I \>> 
        DOPERM
        LDDUP
        :2:LSORT EVAL
        
        @then we pick the right element
        valueN skippedNumbers -
        GET
      END
    \>>
  \>>

My point is that with DOPERM (the implementation is really neat, with flags to kill the process) I nevertheless have to produce all the permutations with X digits, then remove the duplicates and then sort them to pick the right element.

I was not able to devise a way to create permutations already "sorted" somehow. If I would be able to do that, I could quit in the middle of the process with the right element.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
09-01-2017, 06:11 AM
Post: #108
RE: List Commands Library for 50g
(09-01-2017 04:00 AM)Joe Horn Wrote:  Not possible, for two reasons:
...

Joe, I don't doubt that the specific implementation details are more efficient than the equation listed. I was merely quoting from the Advanced Users Reference (p. 3-41), which clearly states the above-referenced equation is the one used for COMB. While the specific code executed in the firmware may be different than a brute-force implementation of the formula, the result is essentially the same as the symbolic one referenced.

DOCOMB's output currently includes, and will continue to include, all of the combinations that result from the given list. Duplicate source elements will always result in duplicate combinations.
Find all posts by this user
Quote this message in a reply
09-01-2017, 03:05 PM
Post: #109
RE: List Commands Library for 50g
(09-01-2017 05:29 AM)pier4r Wrote:  I am not sure you checked it but I'd like to know if you would have done the program here (that is using your library a lot) http://www.hpmuseum.org/forum/thread-892...l#pid78250 differently.
...
I was not able to devise a way to create permutations already "sorted" somehow. If I would be able to do that, I could quit in the middle of the process with the right element.

Well, I had seen Gerald's posts (both the even- and the odd-digit ones) and hoped to spend more time trying them out after working through some other projects. So I've actually been trying to avoid looking at how other folks have approached the problem, at least until I could put more thought into it. Smile

Believe it or not, there is actually a pattern to the output of both DOCOMB and DOPERM. Combinations are "chosen" in a different order than permutations, though. I'll explain that further in a separate post. First, an observation about using these commands for this kind of problem: while there are similarities between these sequences and permutations of the digits in question, the actual permutations needed don't line up in a convenient way (as you have found). That's because the ordinal sequence doesn't have all of the "permutation groups" lumped together in a contiguous range. They are intermingled.

While it should be possible to "permute" most of the needed numbers in the sequence, the process would be somewhat messy and you'd end up having to combine the output of multiple permutations with other numbers and re-sort them to get them into the order defined by the sequence. For this reason, I wouldn't have used those commands for this kind of situation. You'd effectively have to create a lot of permutations, add in the missing numbers, sort the output, then determine which value is indexed at the needed position.

As an example, consider the following simplified variant of using permutations to obtain a sequence. In this version, the sequence is simply all two-digit integers that contain the digits 0-9. For simplicity, I'll include 2-digit numbers that start with "0" in this example.

It shouldn't take too long to realize that there should be a total of 100 numbers in this sequence (00-99). Approaching this from a permutation standpoint, the "low hanging fruit" would be to start with { 0 1 2 3 4 5 6 7 8 9 } and permuting all combinations of 2 digits. So how close does that get us to the solution? Fortunately we don't have to guess -- 10 2 PERM tells us how many "groups" should result from a set of 10 digits chosen 2 at a time. The answer of course is 90, which implies that there are 10 other numbers in the sequence that need to be included. I bet you already know which numbers weren't included, and hopefully this starts to show why this approach is "messy". In this two-digit example, you'd have to add in all of the "repeated digit" numbers (00, 11, 22, etc.), then sort all of the results to put them in order. When you increase the number of digits to 3, the "missing" numbers get even more complicated.

That's a long way to say why I wouldn't approach these sequences using permutations, but hopefully answers your question.
Find all posts by this user
Quote this message in a reply
09-01-2017, 05:25 PM
Post: #110
RE: List Commands Library for 50g
yes it was helpful although I meant something else.

My question was if it was possible to get in order those numbers in the range 00-99 although the repeated digits are missing. So far I see only "SORT"/LSORT at the end of the generation.

For the missing digits, it is not only that the problem.

For example "I want all the number with 4 digits having only 1 or 2" . It won't work with { 1 2 } 4 <program> DOPERM .

One needs the input equal to { 1 1 1 1 2 2 2 2 } 4 <program> DOPERM to have chance to generate all, or, excluding 1111,2222 one should still use { 1 1 1 2 2 2 } 4 <program> DOPERM .

Anyway that's not the point, my point was if it was possible to get the result ordered, like
1111
1112
1121
1122
1211
1212
1221
1222
...

with DOPERM. Maybe with a properly adjusted input list?

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
09-01-2017, 11:55 PM
Post: #111
RE: List Commands Library for 50g
OK, thanks for the explanation. I think I understand what you are asking now, though I'm afraid my answer is that there isn't a way to have DOPERM output the permutations in the order you're seeking. Attempting to generate the "missing" numbers by permuting lists with duplicated digits would require de-duping as well as sorting. Adding that to the user program argument might be possible with judicious use of POS, but I would think that this is just not a very effective way to attempt to generate a sequence out of multiple permutations.

It's really good that you asked this, though, because it caused me to find a minor bug in the combination algorithm. It was producing all the combinations OK, just not in the originally intended order that I meant for it to use. I hadn't actually noticed that the order wasn't as intended until I started putting together this response and noticed that the order of combinations wasn't what I expected.

Here's a bit more detail on how things are (now) ordered:

For permutations where all of the list elements are "chosen", the output will be in ascending lexicographical order iff the input list is already in ascending order. In other words, if you do something like
Code:
{ 1 2 3 4 } 4 \<< NL\->I \>> DOPERM

you will end up with output which is also sorted in order:
Code:
{ 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 }

This is due to the internal method that DOPERM uses to "step" through the permutations. While the code doesn't care about the contents of each element, its position in the original list does matter. It's those original position indexes that are actually being sequenced in lexicographical order, not the contents of the elements.

Now that I've fixed the above-mentioned bug, DOCOMB works in a similar fashion, except it does so regardless of how many elements are specified for the combinations. If you check any of the previous releases, however, you'll see that it didn't work that way before. It was intended to, though. I just hadn't noticed it until you prompted me to look! Smile

Where the lexicographical ordering stops holding, however, is when you specify anything less than the total number of elements for a permutation (eg. { 1 2 3 4 } 3 \<<NL\->I \>> DOPERM). This is due to the fact that there are two inherent loops in DOPERM. They can be thought of as follows:
Code:
for each combination of n list elements
    for each permutation of the current combination
        pass the permutation to the user program

This results in a series of combinations which will themselves be ordered, but the aggregate list will no longer be in order as a whole. It's easier to see this in the output than it is to describe it in words (I've inserted line breaks to make the combinations more obvious). Notice that each combination is still ordered, even while the complete list isn't:
Code:
{ 1 2 3 4 } 3 \<< NL\->I \>> DOPERM =>

{ 123 132 213 231 312 321 
124 142 214 241 412 421 
134 143 314 341 413 431 
234 243 324 342 423 432 }
Find all posts by this user
Quote this message in a reply
09-02-2017, 09:08 AM (This post was last modified: 09-02-2017 09:09 AM by pier4r.)
Post: #112
RE: List Commands Library for 50g
Understood. Thanks for the insights, are always interesting!

Side note: I am discovering more and more that - at least in discussions involving me - when I express myself poorly then the chances that the discussion is not about what I mean are really high. So at the end: damn me.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
09-05-2017, 08:51 PM
Post: #113
RE: List Commands Library for 50g
Lists, Explosions, and Taking Out the Trash

I've recently been testing some of the library routines with larger lists to see where I might be able to improve performance. It turns out that many of the library's commands see significant performance degradation when list sizes climb -- much more than would be anticipated simply as a result of the increased element count. So I took a bit more time to understand this issue better, and have found that there's a particular scenario that consistently causes significant slowdowns. The good news is that it can be anticipated, and there is a way around the problem. The bad news is that the cause is a common situation, and the work-around may not always be possible or practical.

To understand this issue better, consider a common approach to manipulating lists:

- Explode the list onto the stack
- Manipulate elements and/or their ordering
- Combine stack objects back into the result list

As you might expect, many of the library's commands use this approach in their operations. Given the nature of how lists are implemented in RPL, it's really the most practical approach for many types of list alterations. Unfortunately, it can also set up a performance bottleneck quite easily when available memory is more of a constraint. The larger the list, the more of an issue this becomes.

So what's the issue? Two words: Garbage Collection. Most RPL users are already familiar with the occasional GC pauses that occur during normal use. They're usually in the form of a momentary "freeze", where the system appears to ignore user actions briefly and then suddenly resumes normal operation. We don't see them all that often, and when we do, they don't last very long and they are easy to ignore. The GC's that I'm referring to in this thread aren't like those, however. They last much longer, and they're actually fairly common as list sizes grow.

How bad can it really be? Try the following simple experiment:

1) Execute MEM. If the result is 25000 or more, proceed. If not, you'll have to reduce the number in step 3.
2) Enter "12345." onto the stack
3) Enter 750
4) NDUPN
5) →LIST
6) EVAL (or LIST→ if you prefer)
7) « MEM » TEVAL

On my 50g, that final MEM takes slightly over 37 seconds to complete. Does that last MEM really take that long? Well, no. But the GC that MEM triggers does (it's probably 2 GCs, but you get the idea here). Using a larger number of list elements will grow the GC durations dramatically.

It is tempting to think "that's because there's so many items on the stack". But that's only part of the story. If you like, repeat the above experiment, skipping steps 5 and 6 (ie. remove the list from the process). The same number of items on the stack, so it should still be slow, right? No. Try it and see. If you don't wish to play along, I'll help you: 0.28 seconds on my 50g. Technically, all of those stack items are really just pointers to a single object, but that's still not the reason for the difference. Try « 1 750 FOR N N NEXT » if you want to make sure the objects are truly different (my 50g reports 0.38 seconds for that final MEM). Note that neither the built-in SEQ command nor GoferList's Seq can be used here, as they both build a list for their result.

The problem stems from the fact that the "exploded" objects are actually still embedded in the original list in an area of memory called TEMP (or TEMPOB), and the GC routines get bogged down when checking to see if that list can be discarded. The work-around is fairly simple: force RPL to make new copies of the exploded objects instead of just copying pointers to the existing ones onto the stack. But doing so will cost you both time and memory. The extra time taken to explode the list is a no-brainer -- it is only a fraction of the time that the first avoided GC would have taken. The lack of available memory can be a deal-breaker, though.

The following program shows both the problem as well as a reasonable way to mitigate it using only standard UserRPL commands. GCDemo takes two numbers as arguments: list size (SL2) and "explosion method" (SL1). An explosion method of 1 will result in LIST→ being used, anything else will use a different method (see the code for the one I used). GCDemo will report the time it takes for each section of the code to complete.

Enter the targeted list size (750 is a good first choice), then a "1" on the stack and execute GCDemo to see how GCs stop the "processing" loop periodically. Using the same list size as before, a "2" (or anything other than 1) for the explosion type argument will use the alternate method to reduce the durations of the inevitable GCs that occur. Note how much faster the complete process is, even though the explosion step takes longer.

I'm still working on a strategy for the best way to deal with this in the library. I believe the final method will involve checking list element count, total list byte size, and available memory before determining which method of list explosion to use.

Code:
GCDemo
\<<
  @ listSize
  @ already on SL2 at entry

  @ expType
  @ already on SL1 at entry

  @ appStart
  TICKS

  @ sectionStart
  DUP

  @ memHog
  0

  @ msgList
  {
    "Checking Memory"     @ 1
    "Creating List"       @ 2
    "Exploding List"      @ 3
    "Processing"          @ 4
    "Total Time"          @ 5
  }

  \-> listSize expType appStart sectionStart memHog msgList
  \<<
    @ BegMsg subroutine
    \<<
      msgList OVER GET 31 CHR + SWAP DISP
      TICKS 'sectionStart' STO
    \>>

    @ EndMsg subroutine
    \<<
      TICKS sectionStart - B\->R 8192 / 3 RND \->STR SWAP
      msgList OVER GET ": " +
      ROT + SWAP DISP
    \>>

    \-> BegMsg EndMsg
    \<<
      @ clear the display
      CLLCD

      @ check/set available memory and target list size
      1 BegMsg EVAL     @ show status
      listSize 10.5 *   @ approximate storage needed for list
      3.1 *             @ need a bit more than 3x list storage
      MEM SWAP          @ available memory
      IF DUP2 > THEN
        @ reduce available memory to target
        -               @ memory to temporarily "eat"
        8.005 / 1 \->LIST 999. CON @ make an array to consume the excess
        'memHog' STO    @ store the array in the memHog local
      ELSE
        @ reduce the targeted list size to fit
        DROP            @ targeted storage need no longer appropriate
        3.1 /           @ memory available for list
        10.5 /          @ number of list elements memory will support
        'listSize' STO
      END

      @ show free memory and list byte size at bottom of display
      "Mem: " MEM IP R\->I \->STR + "    List: " +
      listSize 10.5 * IP R\->I \->STR + { #0 #66d } 1 DISPXY
      1 EndMsg EVAL     @ update status

      @ create the list
      2 BegMsg EVAL     @ update status
      12345 I\->R listSize NDUPN \->LIST  @ build a list of real numbers
      2 EndMsg EVAL     @ update status

      @ explode the list
      3 BegMsg EVAL     @ update status
      CASE
        expType 1 == THEN   @ argument of 1 indicates standard method
          LIST\->
        END

        @ argument wasn't 1; use NEWOB method
        DUP SIZE \-> ls
          \<<
            \<< SWAP NEWOB SWAP \>> STREAM NEWOB
            ls
          \>>
      END
      3 EndMsg EVAL     @ update status

      @ "process" the list
      4 BegMsg EVAL     @ update status
      1 OVER FOR n      @ show a loop counter
        "Loop: "
        n R\->I \->STR +
        " / " +
        OVER R\->I \->STR +
        7 DISP
      NEXT
      4 EndMsg EVAL     @ update status

      @ delete the exploded list stack objects
      DROPN

      @ update the final time
      appStart 'sectionStart' STO
      5 EndMsg EVAL     @ update status

      @ leave display intact after finishing
      7 FREEZE
    \>>
  \>>
\>>
Find all posts by this user
Quote this message in a reply
09-05-2017, 09:33 PM (This post was last modified: 09-05-2017 09:40 PM by Joe Horn.)
Post: #114
RE: List Commands Library for 50g
The problem of long garbage collections when there are a lot of exploded list items on the stack can be avoided by first storing the list into a global variable. The built-in SORT routine does this by doing the following before anything else:

Code:
ID '{}
StoHiddenVar
'
ID '{}
RclHiddenVar
DROP

This stores a copy of the input list into a hidden global variable called '{} (the name doesn't matter), recalls it from there, discards the TRUE from level 1, and then goes about sorting the list without worrying that garbage collections will take forever. It's a great trick; just remember to purge the variable afterwards, even if the operation is aborted midway. SORT uses the SysRPL command PuHiddenVar for that.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
09-05-2017, 09:45 PM
Post: #115
RE: List Commands Library for 50g
nice info David and Joe.

I am really happy that the challenges about list processing (that are not yet ended. I need only more time) triggered such endeavor that is quite interesting

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
09-05-2017, 09:49 PM
Post: #116
RE: List Commands Library for 50g
(09-05-2017 09:33 PM)Joe Horn Wrote:  The problem of long garbage collections when there are a lot of exploded list items on the stack can be avoided by first storing the list into a global variable.

Which would also cut down on the memory footprint as well, since dups wouldn't have to be created. That's a good tactic, and since moving memory around on the ARM systems is fast, it's probably not too costly in terms of time.

It's also easy enough to incorporate into a UserRPL program (which was part of why I brought this up in the first place). All-around it's probably the best option. Thanks for pointing it out, Joe!
Find all posts by this user
Quote this message in a reply
09-06-2017, 05:46 AM
Post: #117
RE: List Commands Library for 50g
Just for info: LSORT does not store the list in a hidden variable as it doesn't explode it onto the stack. It will resort to a garbage collection when necessary, but then it will just start over.

Cheers, Werner

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
09-06-2017, 01:52 PM
Post: #118
RE: List Commands Library for 50g
Don't mind me, I'm just dropping some semi-relevant SysRPL code including a wall of text, just as I usually do. Wink

Using some SysRPL tools there is another trick to accelerate list processing. In a nutshell, it's an alternative to exploding a list, then operating on the elements, and reassembling the list. The basic operation is:
- push the list to the return stack using >R
- try to pop one element off the list onto the normal data stack using ticR
- if successful (returned element and TRUE), perform your operation and repeat from the previous step.
- if not successful (returned FALSE), just continue. The end of the list has been reached, and ticR already dropped the empty remnant of the list from the return stack.
- reassemble the list in some way, if you want.

It's not suitable for all list operations, but many go well with it. Mapping and filtering is straightforward (just remember to wrap the results of the mapping operations into a list afterwards), folding is easy by either popping one additional element off the list before entering the loop, or using a neutral element to start with (0 for addition, 1 for multiplication, ...). If you don't know what folding means, it's basically (((elem1 `op` elem2) `op` elem3) `op` elem4) ... for any user-defined `op`; if you use * as `op` the result will be a product of all elements; MAX as `op` returns the greatest element, etc.

The benefit of this approach is that depending on the operation there may be only a few elements of the list on the stack at any time, so when the garbage collection kicks in, it won't waste much time trying to find out that the elements are part of that huge list. Folding keeps the stack very clean; most mapping operations create new elements which are not pointers into the list; filtering is the black sheep in that it still accumulates a lot of unmodified elements from the original list on the stack, though I believe this is still a small speed improvement over keeping the entire exploded list on the stack and rolling it until the entire list is processed. The store-to-global-var trick mentioned by Joe can be combined with this to reap the benefits of both.

I can't take credit for this trick, I found it ... somewhere a long time ago. Probably in ROM, because ticR is just made for this, and it's a command from ROM. Perhaps I was reading POSCOMP, which is one of the routines using it. (Nosy is a wonderful tool, it's so easy to quickly browse the ROM for anything!) Maybe some of the experienced SysRPL programmers already knew this trick because they did the same.

The only difficult part in using this is constructing the loop, because SysRPL's indefinite loops use one item on the return stack as well, so the programmer must keep track of what's where on the return stack. In ROM there is an easy workaround involving GOTO which doesn't care about the return stack, but that only works with fixed addresses, so we can't use it (a relative GOTO is possible, but it has to be supplied by the programmer). This loop should work:
Code:
::
  >R
  BEGIN
    RSWAP ticR
  WHILE
    ::
      RSWAP
      ... your operation ...
    ;
  REPEAT
;
This is the bare minimum for mapping purposes - you'll need to add code to wrap the results into a list, and for that you'll also need to keep track of the list size.
An alternative approach to looping would be to use recursive calls and COLA (to keep the recursion from leaving stuff on the return stack), but that's slower because recursion needs some kind of variable or ROMPTR lookup. Even NULLLAMs have a hard time beating the easy pointer storage on the return stack, as employed by the existing indefinite loop commands.

The upside of the >R and ticR loop compared to UserRPL's MAP is that you can access and modify all elements of the stack (except for the original list, but that's fixable by DUPing it beforehand) as you please; including the ones left behind by previous iterations of the loop, which is why folding is so easy. Filtering is enabled by mapping an element to itself or to nothing - MAP will fill in NOVAL if you try that, but this loop allows you to truly remove elements. (Similarly, when returning multiple results from an operation, MAP will wrap them into a list to place at the mapped element's spot, the ticR loop allows growing the list.)
The downside is that you need to dive into SysRPL, obviously.
Find all posts by this user
Quote this message in a reply
09-06-2017, 02:22 PM
Post: #119
RE: List Commands Library for 50g
(09-06-2017 01:52 PM)3298 Wrote:  Don't mind me, I'm just dropping some semi-relevant SysRPL code including a wall of text, just as I usually do. Wink

I'm actually using a variant of that technique quite a bit in the library -- instead of ticR (which returns the boolean), I've been using 'R (which only returns the object). I actually learned the technique when tracing through one of the built-in routines (probably DOLIST), and it is indeed a nice way to handle things in certain cases.

For small lists, it's actually slightly slower than "explode/ROLL/ROLLD", but the difference isn't great enough to make up for the benefits it provides. In particular, it's very nice as a means to almost have a "spare stack" to draw objects from that doesn't cause you to have to juggle others. And as list sizes grow, its measurably faster than the ROLL/ROLLD sequence. I have used it quite a bit in the library for places where I simply need a "sequential pump" of list elements. I'll check to see if I can change some of these to the indefinite structure with ticR, as I suspect I might be able to tweak performance a bit with that in some cases.

Please continue to chime in with these suggestions! Although I already knew of this one (or its cousin), there's tons that I don't. I occasionally see things like this when tracing code with Nosy, and it can take a bit to figure out what it's for. This one caused me some head scratching until I actually copied some of the code and stepped through it to understand it better.

That's also how I discovered the usefulness of OBJ>R some time back. It's documented well enough, but I simply hadn't noticed it until I saw it used in some firmware code. So tips and pointers such as yours and Joe's aren't just welcomed, they're hoped for.

Thanks!
Find all posts by this user
Quote this message in a reply
09-06-2017, 02:44 PM
Post: #120
RE: List Commands Library for 50g
(09-06-2017 01:52 PM)3298 Wrote:  ...(a relative GOTO is possible, but it has to be supplied by the programmer).

Yes, I remember that discussion, though as I mentioned in that thread I'm less enthusiastic about the GOTO possibility than I am the GOSUB. I've used that a couple of times in various projects, but not all that often. The syntax of doing it in Debug4x is awkward enough that I don't usually go that route. I can't remember exactly why right now, but there was a reason I had to use that technique sometime in the last year or so. It may have been when I was playing around with the "NoMenu" app (SOL replacement). Seems like there was some reason I had to use that technique when working on that.

(09-06-2017 01:52 PM)3298 Wrote:  The downside is that you need to dive into SysRPL, obviously.

Why is that a downside? Smile That's been my preferred environment for 48-50 coding for some time now. The ListExt library is entirely a SysRPL project, except for 20 or so Saturn routines strategically placed to enhance performance.
Find all posts by this user
Quote this message in a reply
Post Reply 




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