Threaded Mode | Linear Mode

pier4r · (This post was last modified: 06-13-2017 10:24 AM by pier4r.)

Neat addition. And yes the revlist works.

So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist) . wrong, the code had a bug.
start headList: avg 1.66 s
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)

So if exploding a list with userRPL gets a speed (maybe only for 100 elements, I need to test with 1000) comparable to dolist/dosubs and way better than the compact TAIL + HEAD (those may be few commands but I beleive are intensive), I was thinking that exploding the list and handling it with sysRPL would be super fast, like 3 times faster.

Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

if the "headTail" procedure holds its speed, it is a great replacement for dosubs/dolists for iterations, at least in userRPL.
Also using a for is not as bad as I thought. Going for 1000 elements now.

Of course, if you see other ways (debug friendly) to iterate over a list, please tell me!

Code:

headListHelp

"input:

L1: list

output:

L2: list without head element

L1: head element"

  headList

  \<<

    @given a list in input, leaves on level1 the first element

    @ and on level 2 the rest of the list.

    @0 

      @numEl

    \->

    @external input

    list

    @local input

    @numEl 

      @elements in the list.

    \<<

      list OBJ\-> 1 - \->LIST

        @reducing the number of elements of 1 for the new list

        @we have the tail on level 2

      SWAP

        @now the head element is on the level 1 stack

    \>>

  \>>

testIterationSpeed

    @ testing the efficiency of different iteration approaches,

    @ given that DOLIST and DOSUBS although fast are not

    @ so debug friendly especially when nested

    @ The approach tested the fact to get an element from the list

    @ that then can be processed

    \<<

      {} "baseList" DROP

      100 "baseListSize" DROP

      {} "resListDosubs" DROP

      {} "resListDolist" DROP

      {} "resListForGet" DROP

      {} "resListStartGeti" DROP

      {} "resListStartheadList" DROP

      {} "resListStarttailhead" DROP

      {} "resListStartLrot" DROP

      0 "temp" DROP

      \->

      @input

      iterations

      @localVar

      baseList

      baseListSize

      resListDosubs

      resListDolist

      resListForGet

      resListStartGeti

      resListStartheadList

      resListStarttailhead

      resListStartLrot

      temp

      \<<

        baseListSize seqList 'baseList' STO

        1 iterations

        START

          \<<

            @ 10 times, list 100 el: avg 0.48 s

            baseList

            1

            \<<

              \->

              elementIn

              \<<

                elementIn

              \>>

            \>>

            DOSUBS

            DROP

            @"dosusbs"

          \>>

          TEVAL DTAG

          'resListDosubs' STO+

          \<<

            @ 10 times, list 100 el: avg 0.50 s

            baseList

            1

            \<<

              \->

              elementIn

              \<<

                elementIn

              \>>

            \>>

            DOLIST

            DROP

            @"dolist"

          \>>

          TEVAL DTAG

          'resListDolist'STO+

          \<<

            @ 10 times, list 100 el: avg 0.93 s

            1 baseListSize

            FOR pos1

              baseList

              pos1

              GET DROP

            NEXT

            @"for get"

          \>>

          TEVAL DTAG

          'resListForGet' STO+

          \<<

            @ 10 times, list 100 el: avg 1.19 s

            baseList

            1

            1 baseListSize

            START

              GETI DROP

            NEXT

            DROP

            DROP

            @"start geti"

          \>>

          TEVAL DTAG

          'resListStartGeti' STO+

          \<<

            @ 10 times, list 100 el: avg 0.42 s

            baseList

            1 baseListSize 1 -

            START

              headList DROP

            NEXT

            HEAD DROP

            @ "start headList"

          \>>

          TEVAL DTAG

          'resListStartheadList' STO+

          \<<

            @ 10 times, list 100 el: avg 0.96 s

            baseList

            1 baseListSize 1 -

            START

              DUP TAIL SWAP HEAD DROP

              @www.hpmuseum.org/forum/thread-8209-post-74498.html#pid74498

            NEXT

            HEAD DROP

            @ "start tail head"

          \>>

          TEVAL DTAG

          'resListStarttailhead' STO+

          \<<

            @ 10 times, list 100 el: avg 3.50 s

            baseList

            1 baseListSize

            START

              DUP HEAD DROP

              -1 LROT

            NEXT

            DROP

            @ "start lrot"

          \>>

          TEVAL DTAG

          'resListStartLrot' STO+

        NEXT

        "dosubs"

        resListDosubs

        "dolist"

        resListDolist

        "for get"

        resListForGet

        "start geti"

        resListStartGeti

        "start headList"

        resListStartheadList

        "start tail head"

        resListStarttailhead

        "start lrot"

        resListStartLrot

      \>>

    \>>

DavidM · 06-12-2017, 09:41 PM

(06-12-2017 07:46 PM)pier4r Wrote: So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist)
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)
...
Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

I'm a little surprised that the GET/GETI commands did that well, but I'd guess you'd start to see them slow down a bit as the list sizes grow.

LROT is actually fairly simple, but it does take some time. It basically determines the two sublists that need to be swapped based on the given parameter, makes the sublists, then reassembles them. I might be able to speed it up some with a slightly different approach, but I'm guessing it won't be a significant difference in the final timings. I should add this to my list of things to check, though.

The bulk of the time in the LROT loop is probably from LROT itself. DUP is very fast (it simply copies a pointer, not the actual data), and HEAD is pretty fast as well. My testing on lists of 100 items showed an average timing of .0336 seconds, so a loop of 100 iterations taking 3.36 seconds just for LROT alone would be expected. The remainder of the time for the other commands (and loop overhead) seems reasonable to me.

The internal representation of a list isn't very sophisticated. It's basically a prologue token, each object's data one after the other, and an epilogue token. So any commands that access individual objects within a list have to (literally) traverse/skip each and every object before the one in question in order to access it. In the case of embedded sublists, each element in them also has to be traversed. There's no way to skip over entire embedded sublists, as lists don't contain size information. Even getting the length of a list requires traversing all contained elements. So you can see where the longer a list is, the more time is required to deal with the list's elements.

HEAD is relatively fast because only the first element has to be accessed. TAIL can quickly skip the first element, but it still has to make a copy of the remainder of the list. So it's more sensitive to list size.

I haven't yet traced through DOSUBS and DOLIST to see how they work, but I suspect they do something similar to STREAM (which I have looked at) that allows relatively quick access to list contents by isolating one element at a time in the runstream. That method isn't available to UserRPL programs, as it requires manipulation of the return stack -- a technique that has to be executed very carefully to avoid blowing everything up. Smile

pier4r · (This post was last modified: 06-12-2017 09:52 PM by pier4r.)

For lrot I thought you exploded the list and rolled the elements, as I do in user rpl.

This should be faster I think.

And thanks for sharing insights!

DavidM · 06-12-2017, 10:19 PM

(06-12-2017 09:51 PM)pier4r Wrote: For lrot I thought you exploded the list and rolled the elements, as I do in user rpl.

This should be faster I think.

And thanks for sharing insights!

Explode/roll/implode would work ok for an argument of 1/-1, but you'd have to loop the rolls for other numbers. Once list sizes get into the hundreds, rolls start to slow down. Try the "roll" method on a list of 1000 items rotated by 500 (or -500). How does it do? LROT handles that in about .19 seconds.

The method I want to test is similar to what I'm currently doing, but would involve loading the elements onto the stack from two different streams and then imploding the whole list. It may not actually be any faster than splitting a list into two pieces and reassembling them, but it's worth a try.

pier4r · (This post was last modified: 06-13-2017 08:16 AM by pier4r.)

(06-12-2017 10:19 PM)DavidM Wrote: Explode/roll/implode would work ok for an argument of 1/-1, but you'd have to loop the rolls for other numbers. Once list sizes get into the hundreds, rolls start to slow down. Try the "roll" method on a list of 1000 items rotated by 500 (or -500). How does it do? LROT handles that in about .19 seconds.

Understood, I thought it was always quite quick. Then Lrot seems to be effective on a big chunk of rotations but not many little ones. Good to know.

The test with lists of 1000 elements is still running, over an hour now.

I'll be interested in the results.

DavidM · 06-13-2017, 12:43 AM

(06-12-2017 10:26 PM)pier4r Wrote: The test with lists of 1000 elements is still running, over an hour now.

I'll be interested in the restults.

I ran a single cycle with 1000 list elements, and got these results:

"dosubs" { 7.8397 }
"dolist" { 7.7578 }
"for get" { 34.002 }
"start geti" { 54.728 }
"start headList" { 535.6086 }
"start tail head" { 33.1366 }
"start lrot" { 4244.4562 }

The LROT loop is most likely a victim of multiple garbage collection events, as the expected time based on previous timings would have been closer to 385 seconds.

Garbage Collections can be made worse by using certain techniques, though I must confess the reasons aren't always obvious. It could be that simply splitting a large list into two sublists is one of those techniques that causes problems. It doesn't make sense to me that it would be any worse than exploding everything then imploding it back, but the evidence speaks for itself!

I'll continue to test some other methods for LROT. I may also "special case" it to use a roll/unroll if the argument is 1 or -1, since that would almost certainly be better than creating two lists to join when one of them has only one element.

pier4r · 06-13-2017, 08:23 AM

(06-13-2017 12:43 AM)DavidM Wrote: I ran a single cycle with 1000 list elements, and got these results:

"dosubs" { 7.8397 }
"dolist" { 7.7578 }
"for get" { 34.002 }
"start geti" { 54.728 }
"start headList" { 535.6086 }
"start tail head" { 33.1366 }
"start lrot" { 4244.4562 }

You saved me. The night is passed but the 50g is still working. Based on your measurements I would expect 13.5 hours for 10 cycles.

Impressive how headList dropped his efficiency and started to be not linear (so exploding a list does not help too) and impressive for + get. I remember now I tested it with 1000 elements and I was getting like 35 seconds. Even for it is not linear (one would expect 9 seconds, 10 times 0.9, not 35) but still only "5" times slower than the DOx commands. Also tail+head very quick.

Quote:The LROT loop is most likely a victim of multiple garbage collection events, as the expected time based on previous timings would have been closer to 385 seconds.

I'll continue to test some other methods for LROT. I may also "special case" it to use a roll/unroll if the argument is 1 or -1, since that would almost certainly be better than creating two lists to join when one of them has only one element.

Yes I guess special cases of an "handful" of elements rotated (I do not know a meaningful threshold, but maybe up to +10 , -10 ?) would make LROT really effective even for multiple calls.

pier4r · (This post was last modified: 06-13-2017 11:49 AM by pier4r.)

In the meanwhile my 50g finished. Those are the results for 10 iterations over lists of 1000 elements (the same as the one from David, just to confirm the results. Wait not, there is one that does not fit)
"dosubs" avg { 7.85 }
"dolist" avg { 7.76 }
"for get" avg { 34.08 }
"start geti" avg { 54.86 }
wrong: "start headList" avg { 4.12 } (instead of 535 s. What's going on here? Surely replicating the test in different setups helps)
"start headList" avg { likely 535 as David tested } I found a bug and I checked the code for a list of 100 elements, it returns 1.66s on average (I corrected the older post). So likely it uses 530 seconds or more on 1000 elements. I do not have the time, at the moment, to let it run.
"start tail head" avg { 33.38 }
"start lrot" avg { 4867.04 }

I'll have to double check the headList result because it seems to good to be true. Moreover david reports 535 seconds, mine 4 seconds.

Edit: checked, indeed there was a bug.

Anyway, all in all, the for + get is quite feasible as subsitute for nested iterations of dolist/dosubs

DavidM · 06-13-2017, 06:23 PM

(06-13-2017 10:06 AM)pier4r Wrote: ...Anyway, all in all, the for + get is quite feasible as subsitute for nested iterations of dolist/dosubs

After spending more time than I care to admit trying alternative methods for LROT, I've come to the conclusion that any method that involves breaking the list apart into its constituent elements will eventually lead to a heart-stopping garbage collection if the function is called repeatedly in succession with a large-ish list as its argument. I was able to get it to the point where they were a bit less often, but it only delayed the inevitable.

So I've decided to try going the route I originally wanted to go in the first place, but thought might not be worth the hassle: I'll recreate the list by copying the two blocks of memory containing the reversed parts into a new list object directly. It will require a bit more setup (and a lot more code), but it should be a relatively fast option that is nicer to the overall memory footprint of the machine. It will be a good exercise that may have other benefits as well for the other functions I'm contemplating.

Regarding the GET performance, it occurs to me that I should probably temper my criticism of its performance. GET is better than PUT, owing to the fact that it's relatively quick to skip a series of objects when you don't actually have to explode them. But I still maintain that if you know you need to manipulate more than a couple of items in a list (or array, though they are a bit more efficient), it's better to break them apart and then reassemble them later than to loop a bunch of GET/PUT pairs.

pier4r · 06-13-2017, 10:00 PM

Well from a completely ignorant point of view I somehow believe that consuming a list (for iterations) is somehow quick (indeed your tail head method is as fast as for + get). Just one has to extract elements properly. For this I asked you a sysrpl approach, because maybe there is a way.

DavidM · 06-14-2017, 05:40 AM

(06-13-2017 06:23 PM)DavidM Wrote: I'll recreate the list by copying the two blocks of memory containing the reversed parts into a new list object directly. It will require a bit more setup (and a lot more code), but it should be a relatively fast option that is nicer to the overall memory footprint of the machine.

First stab at the new version of LROT (LROT7 below) is promising:

\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{LROT} & 0.0259 & 0.0339 & 0.1006 & 0.1820 & 50 \\
\textbf{LROT7} & 0.0262 & 0.0299 & 0.0592 & 0.0945 & 50 \\
\hline
\end{array}

Timings are comparable to the original for smaller lists, but it scales nicely as the list sizes grow. And it's much nicer with regards to the memory footprint, in that it doesn't explode the list and rebuild it. Completed the 1000-element "stress test" (1000 loops with DUP/HEAD/etc.) in about 125 seconds.

pier4r · (This post was last modified: 06-14-2017 08:06 AM by pier4r.)

Nice. and 125 seconds vs 4800 is quite an improvement. Because, at least from my pov, I do believe that the average use case of rotating a list is not rotating it once, but multiple times.

pier4r · (This post was last modified: 06-14-2017 12:08 PM by pier4r.)

@DavidM: another request if I may ask.

POS , as far as I know, returns the first matching position in a list.

What if I want to know all the positions that matches the element? I did, for one of the challenges, an helper routine. Do you find reasonable to develop one for your library?

Small argument by me: whether a routine it is good already in userRPL, it does not mean that it ready available for a user (which has to find it or develop it), that is the reason to have a "useful" library.

request:

Code:

returnAllPosHelp

"input:

The built in POS, as far as I know,

returns only the first match.

L2: input list

L1: element to search

output

L1: list of position where elment appears in list

"

  returnAllPos

  \<<

    { } @resultList

    \->

    @input

    inputList

    elementV

    @local

    resultList

    \<<

      inputList

      \<<

        \->

        value

        \<<

          IF

            value elementV ==

          THEN

            'resultList' NSUB STO+

          END

        \>>

      \>>

      DOSUBS

      resultList

    \>>

  \>>

edit. another request, list contains

Code:

listContainsHelp

"input:

2: list L1 

1: list L2

output:

1: { list of elements in L2 present in L1}

remarks:

- duplicates not checked.

todo:

- handle duplicates. If the same element occurs in L2 N times

and it appears in L1 K times, with K <= N . Then the element

will appear in the result K times, not N.

" 

    listContains

    @it seems to work

    \<<

      {} "resList" DROP

      \->

      @input

      inL1

      inL2

      @var

      resList

      \<<

        {} @handle empty result

        inL2

        1

        \<<

          \->

          @input

          element

          \<<

            inL1 element POS 0 \=/

            element

            IFT

          \>>  

        \>>

        DOSUBS

        IF

          DUP SIZE 0 >

        THEN

          @non empty result

          @clear the list before

          +

        END

      \>>

    \>>

request: does your library complement goferlist or not? (I would say: until you find faster and/more flexibile code, yes) Because otherwise diff/intersect may be useful.

edit. Also #36

Code:

c36vaV1

    @given a list made of sublists

    @returns the sublists (positions) that contain a given element

    @it seems working

    \<<

      {} "resList" DROP

        @in the case it will be the result when no match is found

      \->

      @input

      inL1

      element

      @local var

      @L1size

      resList

      \<<

        1 inL1 SIZE

        FOR index

          inL1 index GET  @get sublist

          element POS @get the position

          IF

            @if the element is present (at least once)

            DUP 0 \=/

          THEN

            @at the position to the result

            'resList' index STO+

          END

          DROP @clean the stack

        NEXT

        resList

      \>>

    \>>

edit: check goferlist from time to time, I have to say that the documentation of the single commands is, well, too "twitter like". Sometimes really cryptic. Whatever the product, a proper documentation is part of its value.

Werner · 06-14-2017, 11:49 AM

ALLPOS

Code:

\<<

  \-> o

  \<<

    1.

    \<< o == NSUB IFT \>>

    DOSUBS

  \>>

\>>

or, when no match returns an empty resultlist:

Code:

\<<

  \-> o

  \<<

    {} SWAP

    1.

    \<< o == NSUB IFT \>>

    DOSUBS

  \>>

  IF DUP SIZE THEN + END

\>>

Cheers, Werner

DavidM · 06-14-2017, 02:34 PM

(06-14-2017 08:04 AM)pier4r Wrote: Nice. and 125 seconds vs 4800 is quite an improvement. Because, at least from my pov, I do believe that the average use case of rotating a list is not rotating it once, but multiple times.

I agree with you about the multiple rotations, which is part of the reason I went ahead and did this.

To be fair, this is (for a 50g) a fairly extreme situation due to the list size. Exploding a list and then rebuilding it leaves behind unreferenced objects; the number of discards will be (at a minimum) equal to the number of objects in the list + the original list. When you do that rapidly in succession, the "garbage" builds up quickly. It's inevitable that a GC will take place, and when it does, it has to locate/flag-objects-for-disposal/re-compress all of the space they were inhabiting.

The changes I made still leave a large block of memory disposed, but it's contiguous and easily "skippable". When watching a loop make 1000 calls to LROT (v7) operating on a list of 1000 elements, you can barely discern when the GCs occur. The previous version left 1000 disposable objects behind every iteration, so the GCs would lock up the system for a painful period every time they happened.

I should note that this phenomenon is not unique to my library; any activity (whether built-in or user-programmed) that explodes/implodes large lists will be vulnerable to this issue.

DavidM · 06-14-2017, 03:27 PM

(06-14-2017 08:57 AM)pier4r Wrote: @DavidM: another request if I may ask.
...
request: does your library complement goferlist or not? (I would say: until you find faster and/more flexibile code, yes) Because otherwise diff/intersect may be useful.
...
edit: check goferlist from time to time, I have to say that the documentation of the single commands is, well, too "twitter like". Sometimes really cryptic. Whatever the product, a proper documentation is part of its value.

I think of this "working project" as a collaborative effort, and I'm happy to consider all suggestions for additional functions/commands. It continues to be a good exercise for me to consider the application of list processing in solving problems as opposed to my more "iterative" inclinations.

I've been somewhat concerned that showing my earlier timing comparisons with GoferList functions would be perceived as my wanting to replace it (or even "compete" with it). That definitely wasn't/isn't my intent. It seemed like a good benchmark for comparison with similar functions that I'd already created, so I thought it would make sense to show the data that way.

GoferList appears to have been originally created with the idea that it would replicate known list functions from the Haskell language, so I'm guessing that the original developers were less concerned about documenting the commands and only felt the need to provide the minimum needed to use the commands in an RPL context. They probably figured that it's main appeal would be to people who already knew what the functions did, or would seek the meaning in other ways.

I definitely see my library as a complement to GoferList, even though there is a small amount of overlap. If I'm to implement more functions, I'd prefer to focus on those things that aren't already available in GoferList (or trivial to implement). As an example, many of the GoferList commands are designed to apply a user-defined function to a process. I have no desire to replicate that sort of functionality, as I don't think I could really add anything useful to those commands. Gilles' suggestion of a DOPERM command would represent new functionality that definitely would add value (and isn't trivial), so it's high on my list to investigate. So that's more the type of thing that interests me at present.

I'll add your recent suggestions to my list of things to ponder, as I can see where those functions would be useful in a variety of contexts.

DavidM · 06-14-2017, 03:38 PM

(06-14-2017 11:49 AM)Werner Wrote: ...

Code:

... { } SWAP ... IF DUP SIZE THEN + END

Nice, Werner. That's a great way to deal with the "no list returned" issue!

pier4r · (This post was last modified: 06-14-2017 06:04 PM by pier4r.)

Werner nice input, although your very usage of the stack sometimes is not so easy to follow if one loses track of what is on the stack (like the fact that you collect only one input in a variable, the other is on the stack). I prefer something that may be bigger but easier to read if I did not touch it for long.

Anyway, the #35 , that with "for + get" is feasible (still, I think that even with for + get the #20 would be quite more demanding), seems working.

Actually I am not sure I tested all the corner cases so if you want to play along, do it.
It uses, I think, the library of david and also goferlist in case some commands were missing (but I avoided to replicate them)

The #35 requires the #36 and an helper.

If you have tips were I can improve (keeping things readable), let me know.

For the timings, well, I'll do if there is a bit of competition.

Code:

c35vaV1

    @check if an input list with a certain structure makes a balanced binary tree

    @requires list library of DavidM and goferlist

    @for the test done it seems working.

    \<<

      @plan: 

      @ - first finding the root that is the only sublist of the list containing

      @   0. Also this method of search will be crucial for all the other

      @   cases. So it is like a new processing list challenge:

      @   "return the positions of all the sublists of a list containing the given

      @   object"

      @ - put the position in LI (list input)

      @   of the object containing 0 in a separated list of "checked

      @   positions", called LCP

      @ - put the root in a separated list to consume to traverse the tree,

      @   called LTT

      @ - put the height of the current element added to LTT in a list of

      @   heights, LH. Note that the height in LH should match the position of the

      @   root in LTT

      @ - consume the first element (the root) from the list LTT.

      @   (since LTT has a relationship with LH, a way to consume it is

      @   to increment a counter after reading the element)

      @   check the positions of all the sublists containing it in LI

      @   (should be max 3, otherwise the tree is invalid)

      @ - put the destinations reached by the root , that have positions

      @   not present in LCP in LTT

      @ - put the heigths of those destinations in LH, with same positions

      @   as the destinations in LTT. Of course the heights are equal to

      @   the parent height (the root) plus one.

      @   We know who is the parent because we know which elements from LTT we are

      @   consuming.

      @ - put the returned positions in LCP (if you do this step before,

      @   you cannot use to discriminate new destinations)

      @ - generic step

      @   - Consume the next element E from LTT. Check all the sublists in LI that

      @     contains it. As usual, it should be max 3, of which max 2 sublists

      @     should be new (that is, their position is not in LCP). otherwise

      @     the tree is invalid (can still be invalid in other ways though)

      @   - put the destinations of the sublists where E appears, sublists that

      @     have positions not in LCP, in LTT.

      @   - collect the height of E from LH, and add plus one and put the heights of the

      @     new destinations in LH with positions relative to the position just added

      @     in LTT

      @   - add the positions retrieved before that are new in LCP

      @   - check. A node that has a single children (so only one destination)

      @     cannot have the children having children as well. So if given an element E

      @     only one destination is added, a check has to be done and 

      @     (a) the destination should appears only once in LTT

      @     (b) searching for sublists with the destination in LI 

      @         should return only one match that should be already in LCP in

      @         terms of positions

      @     otherwise the tree is invalid.

      @   - check. For the height. Since the procedure in theory is devised to

      @     explore the tree layer by layer, it means that every children has

      @     the height of the parent, plus 1. (because we add children when we

      @     expand a parent). Now when we have a node with no children, that is

      @     a leaf and we save the __minimum__ leaf height, then we continue to

      @     expand the rest.

      @     If we ever get a node that is +2 than the minimum leaft height

      @     then the tree is invalid because not balanced.

      0 "inL1Size" DROP

      {} "LExtractPos" DROP

      {} "LNodes" DROP

      1 "indexElToExpand" DROP

      {} "LNodesHeight" DROP

      0 "minHeight" DROP

      1 "parentNode" DROP

      0 "parentNodeHeight" DROP

      {} "LTemp" DROP

      0 "LTempSize" DROP

      {} "LTemp2" DROP

      {} "LTempSublist" DROP

      0 "tempScalar" DROP

      0 "isNotValid" DROP

      \->

      @input

      inL1

      @localVar

      inL1Size

      LExtractPos

      LNodes

      indexElToExpand

      LNodesHeight

      minHeight

      parentNode

      parentNodeHeight

      LTemp

      LTempSize

      LTemp2

      LTempSublist

      tempScalar

      isNotValid

      \<<

        inL1 SIZE 'inL1Size' STO

        @find the root

        inL1 0 c36vaV1 'LTemp' STO

        IF

          @if more than one node with 0 is returned

          @remember no duplicates allowed so we cannot have 2 roots

          LTemp SIZE 1 \=/

        THEN

          1 'isNotValid' STO

        END

        @check if the sublist in the position of the root is in the proper

        @structure

        IF

          @if the tree is still valid

          isNotValid 0 ==

          @but the sublist is not

          inL1 LTemp HEAD GET 'LTempSublist' STO

          LTempSublist 0 c35vaV1isSublistValid

          NOT

          AND

        THEN

          1 'isNotValid' STO

        END

        @if we are here, the root is valid

        @ so put the root in the list of elements to expand

        'LNodes' 

        LTempSublist 2 GET STO+

        @the add the height of the element that we will expand

        @the height is equal to the parent +1 in this case the root has height

        @ 0. The position should be the same of the position in the nodes

        'LNodesHeight' 0 STO+

        @then put the sublists' positions in the list telling us

        @which ones have we already extracted

        'LExtractPos' LTemp STO+

        @we set the minimum height to a value that unlikely will be matched

        inL1Size 'minHeight' STO

        @now let's proceed with the rest of the nodes

        WHILE

          @the tree is still valid

          isNotValid 0 ==

            @it does not need to be checked for every action always,

            @since isNotValid can get only 1, it dosn't need many checks.

            @when it fails, will be reported at the next iteration

          inL1Size indexElToExpand \>=

          AND

        REPEAT

          @ we take the next parent node

          LNodes indexElToExpand GET 'parentNode' STO

          LNodesHeight indexElToExpand GET 'parentNodeHeight' STO

          @we get the positions of sublists containing the parent node

          inL1 parentNode c36vaV1 'LTemp' STO

          @the sublists should be at least 1 and not more than 3

          LTemp SIZE 'LTempSize' STO

          IF

            LTempSize 0 <

            LTempSize 3 >

            OR

          THEN

            1 'isNotValid' STO

          END

          @#############

          @LTempSize 1 ==

          @if the sublist is just one, the parent node is a leaf

          @we can set if this leaf has the minium height so far

          @but we need to check that the returned sublist position is already

          @one checked

          IF

            LTempSize 1 ==

          THEN

            IF

              @if the sublist position is not what we got already

              LExtractPos LTemp HEAD POS 0 ==

            THEN

              1 'isNotValid' STO

            END

            IF

              @if the height of the node is smaller than the minimum

              @set it as new minimum

              minHeight parentNodeHeight >

            THEN

              parentNodeHeight 'minHeight' STO

            END

            IF

              @if the height of the leaf is 2 more than the minimum heght,

              @then the tree is invalid

              parentNodeHeight minHeight 1 + >

            THEN

              1 'isNotValid' STO

            END

          END

          @#############

          @LTempSize 2 ==

          @if the sublist returns 2. It means that there is the parent

          @and a child, but we need to check that this is a child

          @and if it is a child, it was not extracted before and

          @it won't have further children as well 

          IF

            LTempSize 2 ==

          THEN

            @if we have one position known and the other unknown,

            @we need to extract the unknown position (where the parent connects to a child)

            LTemp LExtractPos Diff 'LTemp2' STO @extract the unkown position

            IF

              @the positions extracted should be one known and one unknown

              @so the unknown should be 1

              LTemp2 SIZE 1 \=/

            THEN

              1 'isNotValid' STO

            END

            inL1 LTemp2 HEAD GET @get sublist

            'LTempSublist' STO

            IF

              LTempSublist parentNode c35vaV1isSublistValid

              NOT

              @destination already in the destinations (a loop)

              LNodes 

              LTempSublist 2 GET 

              POS 0 \=/

              AND

            THEN

              1 'isNotValid' STO

            END

            @so here the additional list is valid

            @we have to expand it

            'LNodes' LTempSublist 2 GET STO+ 

            'LNodesHeight' parentNodeHeight 1 + STO+

            'LExtractPos' LTemp2 STO+

            @if there is only a child, this child cannot have more children

            @this has to be checked now otherwise the script loses the "memory"

            @that there is only one child node

            IF

              @So now we have in how many sublists the destination/child node is present

              @this should be exactly one and already extracted, equal to the last

              @addition to LExtractPos

              inL1 LTempSublist 2 GET 

              c36vaV1 LTemp2 \=/

            THEN

              1 'isNotValid' STO

            END

          END

          @#############

          @LTempSize 3 ==

          @if the sublist returns 3. it means a parent and

          @ two children. Those have to be valid lists and that's it

          IF

            LTempSize 3 ==

          THEN

            LTemp LExtractPos Diff 'LTemp2' STO @extract the unkown position

            IF

              @the positions extracted should be one known and two unknown

              @so the unknown should be 2

              LTemp2 SIZE 2 \=/

            THEN

              1 'isNotValid' STO

            END

            1 2

            FOR index2              

              @get sublist

              LTemp2 index2 GET 'tempScalar' STO

              inL1 tempScalar GET

              'LTempSublist' STO

              @verity it is valid

              IF

                LTempSublist parentNode c35vaV1isSublistValid

                NOT

                @destination already in the destinations (a loop)

                LNodes 

                LTempSublist 2 GET 

                POS 0 \=/

                AND

              THEN

                1 'isNotValid' STO

              END

              @add the destination to the nodes to expand

              'LNodes' LTempSublist 2 GET STO+ 

              @add the height of the node just added

              'LNodesHeight' parentNodeHeight 1 + STO+

            NEXT

            @add the extracted position

            'LExtractPos' LTemp2 STO+

          END

          1 'indexElToExpand' STO+

        END

        isNotValid NOT

      \>>

    \>>

    c35vaV1isSublistValid

    @ given a list (sublists of another)

    @ assumes that the list contains 2 elements

    @ of which the one passed as argument is the source, so the first one.

    @requires list library of DavidM

    @it seems working

    \<<

      1 "isValid" DROP

      \->

      @input

      inL1

      source

      @local var

      isValid

      \<<

        IF

          inL1 SIZE 2 \=/

        THEN

          0 'isValid' STO

        END

        IF

          isValid 1 ==

        THEN

          IF

            inL1 source POS 1 \=/

            inL1 source LCNT 1 \=/

            OR

          THEN

            0 'isValid' STO

          END

        END

        isValid

      \>>

    \>>

    c36vaV1

    @given a list made of sublists

    @returns the sublists (positions) that contain a given element

    @it seems working

    \<<

      {} "resList" DROP

        @in the case it will be the result when no match is found

      \->

      @input

      inL1

      element

      @local var

      @L1size

      resList

      \<<

        1 inL1 SIZE

        FOR index

          inL1 index GET  @get sublist

          element POS @get the position

          IF

            @if the element is present (at least once)

            DUP 0 \=/

          THEN

            @at the position to the result

            'resList' index STO+

          END

          DROP @clean the stack

        NEXT

        resList

      \>>

    \>>

DavidM · 06-15-2017, 06:21 PM

I thought that it might be worth a few more bytes to have two more special-purpose commands that could be wrapped around the same core that's at the heart of LROT: LRLL (List Roll) and LRLLD (List Rolldown). These are functionally equivalent to 1 LROT and -1 LROT, but faster since the amount of rotation doesn't have to be computed from an argument. It also seemed to me that a rotation of 1 or -1 would be common enough to warrant a separate command for those purposes.

The names were chosen to coincide with similar RPL stack-based functionality. LRLL does the same thing as

Code:

\<<

   LIST\-> \-> 'lsize'

   \<<

      lsize ROLL lsize \->LIST

   \>>

\>>

LRLLD is the same, just replace ROLL with ROLLD.

Johnny Knoxville · 06-15-2017, 06:30 PM

Reading the replies of all experts is just fascinating.