Programming puzzles: processing lists!

[pier4r]

I renew the request that someone with the HP prime starts to check / evaluate the solutions of Han and Didier. At the moment I have time just for the RPL.

Challenge 3 code, reusing one of the list operation programmed some time ago
https://app.assembla.com/spaces/various-...ms/general

Code:



    c3vaV1
    @given alist of length 100 of integers
    @ put floor(list_size/3) elements at the beginning
    
    @it seems correct
    @ avg 0.039 secs for 10 lists of 10 elements.
    @ avg 0.15 secs for 50 lists of 100 elements.
    \<<
      { } @resultList
      \->
      @input
      inputList
      @local
      resList
      \<<
        inputList
        inputList SIZE 3 / IP
        rotateListTail
      \>>
    \>>

    rotateListTail
  \<<
    
    0 @numElements
    \->
    @input
    listV
    numRotationsV
    @local var
    numElements
    \<<
      listV OBJ\-> 'numElements' STO
      
      1 numRotationsV
      START
        numElements ROLLD
      NEXT
      
      numElements \->LIST
    \>>
  \>>

VS davidM code of the previous post (nice code once again, but this time the operation was complicated)

Mine: @ avg 0.15 secs for 50 lists of 100 elements.
DavidM: @ avg 1.94 secs for 50 lists of 100 elements.

This time I got one back (although with an helper routine).

Side question: I am not able to save a list in a list, without using another variable.

I mean {1 2 3} {1 2 3} + returns {1 2 3 1 2 3}. What is the operation to return {1 2 3 {1 2 3} } ?

[pier4r]

Challenge 4 finished and got a strange result

Code:


    c4vaV1
    @ given alist of length 100 1s or 0s
    @ threat it as a binary number and add 1 to it.
    
    @ very nice to test, a result is valid for the next test.
    @ it works.
    @ avg: 0.86 secs 100 lists of 100 elements 
    \<<
      { } @resList
      0 @value
      10 @ufCarry
      \->
      @input
      inputList
      @local
      resList
      value
      ufCarry
      \<<
        ufCarry SF
          @ we add 1
        
        inputList REVLIST 
          @revert to read the binary number from low to high.
        1
          @taking one element at time 
        \<<
          'value' STO
          IF
            ufCarry FS?
          THEN
            @add
            
            @ If element read is 0, just leave a 1, stop carry.
            @ If element read is 1, just leave a zero, carry on.
            value 0 ==
            \<< 1 ufCarry CF \>>
            0
            IFTE
          ELSE
            value
          END
        \>>
        DOLIST
        
        ufCarry FS?
          @still a carry
          @add one to the list
        \<< 1 + \>>
        IFT
        
        REVLIST
          @revert like original list.
      \>>
    \>>

This code runs for an average of 0.86 secs for 100 lists of 100 elements.
The code of DavidM takes 0.98 secs for the same workload.

I wonder why, his code seems way more compact (although more cryptic ), doing mostly the same of what my code does, or even less.

same with challenge 5.

Code:


\<<
      0 @value
      10 @ufSub
      \->
      @input
      inputList
      @local
      value
      ufSub
      \<<
        ufSub SF
          @ we sub 1
        
        inputList REVLIST 
          @revert to read the binary number from low to high.
        1
          @taking one element at time 
        \<<
          'value' STO
          IF
            ufSub FS?
          THEN
            @sub
            
            @ If element read is 0, just leave a 1, continue subtract..
            @ If element read is 1, just leave a zero, stop subtract.
            value 0 ==
            1
            \<< 0 ufSub CF \>>
            IFTE
          ELSE
            value
          END
        \>>
        DOLIST
        
        REVLIST
          @revert like original list.
      \>>
    \>>

mine: 0.87 secs, 100 lists 100 elements.
davidM: 0.96 seconds, 100 lists of 100 elements.

[DavidM]

(04-21-2017 09:03 PM)pier4r Wrote:  @ 10 lists of 10 elements: 0.22 secs
@ 50 lists of 100 elements: 2.32 secs
David
@ 10 lists of 10 elements: 0.08 secs
@ 50 lists of 100 elements: 0.59 secs

Outclassed!
Let's see for the next challenges if I can step up the solution. Furthermore the solution of david are very quick. I wonder if working with the stack could be faster or just be barely faster.

Definitely not outclassed! My solution is too fragile, and it is entirely dependent on the data being exactly as described. My approach used what I call an "assumptive" process (if the given element wasn't a 3, I assumed it must be a 5), which is something I don't consider to be a good programming practice. It just made it easier to have a very small procedure to hand off to DOLIST for this particular problem.

[DavidM]

(04-22-2017 11:50 AM)pier4r Wrote:  VS davidM code of the previous post (nice code once again, but this time the operation was complicated)

Mine: @ avg 0.15 secs for 50 lists of 100 elements.
DavidM: @ avg 1.94 secs for 50 lists of 100 elements.

This time I got one back (although with an helper routine).

I thought the intent was to avoid exploding the list and processing the elements on the stack, and I used a very inefficient application of DOSUBS. In retrospect, I've decided that the SUB command should be considered as one of the "list operators" since it has an overloaded function that directly operates on a list. Using that command, I wrote a second version that should perform much better than my first:

Code:

\<<
  @ get list size
  DUP SIZE

  @ determine last position of first subset
  DUP 3 / FLOOR OVER SWAP -

  @ determine indices of last subset
  DUP 1 + ROT

  @ get last subset
  4 PICK UNROT SUB

  @ get first subset
  UNROT 1 SWAP SUB

  @ concatenate the lists
  +
\>>

(04-22-2017 11:50 AM)pier4r Wrote:  Side question: I am not able to save a list in a list, without using another variable.

I mean {1 2 3} {1 2 3} + returns {1 2 3 1 2 3}. What is the operation to return {1 2 3 {1 2 3} } ?

You essentially need to explode the first list, then combine all the elements with →LIST. So something like this would work:

Code:

\<<
  @ I'm using two different lists in this example for clarity
  { 1 2 3 }
  { 4 5 6 }

  @ explode the first list
  SWAP LIST\->

  @ reposition the second list by determining its current position
  DUP 2 + ROLL

  @ determine new list size and implode
  SWAP 1 + \->LIST
\>>

[DavidM]

(04-22-2017 03:49 PM)pier4r Wrote:  Challenge 4 finished and got a strange result...

This code runs for an average of 0.86 secs for 100 lists of 100 elements.
The code of DavidM takes 0.98 secs for the same workload.

I wonder why, his code seems way more compact (although more cryptic ), doing mostly the same of what my code does, or even less.

We are essentially doing similar things here, but there's an important difference in the algorithms that makes yours faster. Notice what happens when there's no carry for a given iteration of the list subprogram: your code (nicely) just leaves the list element alone and proceeds. This results in a measurable savings of time for the overall process.

It would be interesting to see the results if you change the test input to mostly 1s for each list test. I believe that would bring more parity to the timings between our samples.

This underscores an important list processing concept: anything that can be done to minimize the list subprogram for DOLIST/DOSUBS could have a large impact on performance as list sizes increase.

And, yes, I (intentionally) did something a bit strange/cryptic with #5 that may not be very obvious. I was curious as to whether anyone would notice.

Finally, a suggestion for your consideration: there's no need for you to store the 'value' variable for #4. Your subprogram is fine as-is without it:

1) remove "'value' STO"
2) remove "value" before 0 ==
3) remove "ELSE value"

Your code will be even faster!

[pier4r]

David thanks for your posts!

Please provide also the rest of the challenges otherwise I challenge myself (not bad, but still).

About the post #24 . As I wrote, if one writes helper functions to work on list in a general way (and not, say, only considering 3s and 5s) then it is fine.

Said that, Is the code that you pasted the helper function that should be called SUB!? I don't understand how is that routine used.

[Claudio L.]

(04-24-2017 05:03 PM)DavidM Wrote:  

(04-22-2017 11:50 AM)pier4r Wrote:  Side question: I am not able to save a list in a list, without using another variable.

I mean {1 2 3} {1 2 3} + returns {1 2 3 1 2 3}. What is the operation to return {1 2 3 {1 2 3} } ?

You essentially need to explode the first list, then combine all the elements with →LIST.

Actually, all you have to do is put that list inside a list:

{1 2 3 } {1 2 3} 1 ->LIST +

it's simpler, though most likely slower, as you are essentially creating 2 lists instead of 1.

[Claudio L.]

(04-24-2017 04:04 PM)DavidM Wrote:  It just made it easier to have a very small procedure to hand off to DOLIST for this particular problem.

I wonder if using MAP instead of DOLIST would be any faster.

[DavidM]

(04-24-2017 09:32 PM)Claudio L. Wrote:  Actually, all you have to do is put that list inside a list:

{1 2 3 } {1 2 3} 1 ->LIST +

it's simpler, though most likely slower, as you are essentially creating 2 lists instead of 1.

That's much cleaner. Good solution!

[John Keith]

(04-24-2017 09:35 PM)Claudio L. Wrote:  I wonder if using MAP instead of DOLIST would be any faster.

I doubt it, MAP tends to be quite slow.

DOLIST, DOSUBS, and STREAM are pretty efficient. Exploding the list onto the stack usually makes for the fastest code, but at the cost of less readability and longer, more complex programs.

John

[DavidM]

(04-24-2017 08:27 PM)pier4r Wrote:  Please provide also the rest of the challenges otherwise I challenge myself (not bad, but still).

I've got preliminary versions of #6 through #12, but I already know of a couple of things I want check first before posting them. One particular method of doing something is used a couple of times and I want to try some alternate versions of it. I haven't had much time in the last few days to devote to this, though. I'll post something when I can. Not sure about the remainder of the challenges, though. They'll require more thought. I'll get to them when I can.

(04-24-2017 08:27 PM)pier4r Wrote:  Is the code that you pasted the helper function that should be called SUB!? I don't understand how is that routine used.

SUB is a built-in RPL command that, given a list and start/end positions, returns the sublist denoted by those arguments. As such, it is simple work to piece together the list in challenge #3 when you know the start and end positions of the two sublists. The code I listed was meant as a total replacement for my submission for #3, not just a subroutine.

[DavidM]

(04-24-2017 09:35 PM)Claudio L. Wrote:  I wonder if using MAP instead of DOLIST would be any faster.

(04-24-2017 10:00 PM)John Keith Wrote:  I doubt it, MAP tends to be quite slow.

Yet another list processing command to add to the list of dedicated RPL list-processing commands! I hadn't noticed that one before.

Syntax-wise, it appears that it could be used in the same situations where DOLIST (or DOSUBS) would be used with a single list and n=1. I don't see anything documented about it using NSUB, though, so a subprogram that needs to differentiate its process for specific iterations wouldn't be able to take advantage of that. So I suppose it is more like DOLIST than DOSUBS in that regard.

Would be interesting to compare the performance for a couple of these (where it is a good fit, of course).

[Claudio L.]

(04-24-2017 11:50 PM)DavidM Wrote:  Syntax-wise, it appears that it could be used in the same situations where DOLIST (or DOSUBS) would be used with a single list and n=1. I don't see anything documented about it using NSUB, though, so a subprogram that needs to differentiate its process for specific iterations wouldn't be able to take advantage of that. So I suppose it is more like DOLIST than DOSUBS in that regard.

Would be interesting to compare the performance for a couple of these (where it is a good fit, of course).

The commands are quite different:
DOLIST works with one element from several lists.
DOSUBS works with several elements within the same list
MAP works with a single element of a single list, but fully recursive (goes inside lists of lists and preserves the structure).

[DavidM]

(04-25-2017 01:11 AM)Claudio L. Wrote:  The commands are quite different:
DOLIST works with one element from several lists.
DOSUBS works with several elements within the same list
MAP works with a single element of a single list, but fully recursive (goes inside lists of lists and preserves the structure).

Yes, but my point was that DOLIST, DOSUBS, and MAP all appear to work similarly in the special case where you are working with one list, one element at a time (ie. n=1).

If there's a need to utilize the loop index for that type of scenario, that seemingly limits the choice to DOSUBS. But if that need doesn't exist, any of the three could be used.

I just ran a couple quick trials of a simple test of all three of these commands with the same subprogram:

Code:

D01
\<<
  1 100 FOR x
    x
  NEXT
  100 \->LIST
\>>

DoMAP
\<<
  MAP
\>>

DoDOLIST
\<<
  DOLIST
\>>

DoDOSUBS
\<<
  DOSUBS
\>>

Test
\<<
  D01 \<< \v/ \>> 'DoMAP' TEVAL NIP
  D01 \<< \v/ \>> 'DoDOLIST' TEVAL NIP
  D01 \<< \v/ \>> 'DoDOSUBS' TEVAL NIP
\>>

A typical run gave these results on my 50g (approx. mode):
MAP: 1.0255
DOLIST: 0.4794
DOSUBS: 0.4556

As John indicated, MAP appears to be much slower. With this (albeit simple) test, MAP took over twice as long to produce the same results as the other two. Interestingly, DOSUBS seemed to have a very slight edge over DOLIST. But the difference was very minor and may not even be consistent over multiple runs.

That being the case, I have to wonder if the only time you'd really want to use MAP is when you need the recursive processing of lists that include other lists. Any other scenario for MAP would seemingly perform better with either of the other two commands.

[John Keith]

(04-25-2017 01:11 AM)Claudio L. Wrote:  MAP works with a single element of a single list, but fully recursive (goes inside lists of lists and preserves the structure).

This is an important point and makes MAP useful despite its slowness.

I believe that MAP is part of the CAS since it does not appear in the LIST\PROC menu, and it has built-in HELP in the CATalog.

John

[Claudio L.]

(04-25-2017 03:01 AM)DavidM Wrote:  A typical run gave these results on my 50g (approx. mode):
MAP: 1.0255
DOLIST: 0.4794
DOSUBS: 0.4556

Interesting. For completeness, I tested also just doing {...} << \v/ >> TEVAL and got 0.4485 seconds.
So it's fair to say the overhead of using DOLIST or DOSUBS versus just applying the function to the list seems to be negligible (< 10 ms, probably uses some internal version of DOLIST).
MAP on the other hand is introducing a significant delay.

I also tested newRPL on this and there's a negligible difference between DOSUBS, DOLIST and MAP. Actually MAP seems slightly faster (< 20 ms with my calc locked to 6 MHz due to low battery). In fact, in newRPL doing MAP is even faster than applying the square root to the list directly (because it uses MAP internally, so it's MAP+overhead) but the difference in all cases is very small so as to be negligible.

[pier4r]

Nice info!

I wonder the goferlist how would behave. In general I wonder if the built in commands of the hp 50g, using the original firmware, not newRPL, are written in sysRPL. In that case a library like GoFerList would be competitive.

[DavidM]

(04-25-2017 02:32 PM)pier4r Wrote:  In general I wonder if the built in commands of the hp 50g, using the original firmware, not newRPL, are written in sysRPL. In that case a library like GoFerList would be competitive.

This is actually a great question, and the answer is a bit complicated. But the short response which gets to what I believe is your intent is yes, much of the list-processing code in the built-in list commands is written in SysRPL at the outermost levels.

Somewhat longer answer:

All built-in UserRPL commands are actually SysRPL routines. They usually follow a standard format that includes provisions for argument checking, error handling, saving copies of arguments, list processing, and function overloading (for varying argument types). A dispatch mechanism is integral to this process, and once the appropriate action is determined a jump usually occurs to the appropriate firmware routines. Those routines may in turn still be RPL, Saturn, or ARM routines, which then call other routines, etc.

The meat of what you're asking gets to how quickly the processing of a command leaves the User/SysRPL realm and gets to a "lower level" of code -- presumably Saturn and/or ARM code. Of course the answer is "it varies", but as you might guess the heavy-hitters in the list processing arena make good use of SysRPL to handle much of the iterative processing of the arguments before diving into lower-level code.

@Claudio: does newRPL have a "layer" similar in function to SysRPL? If so, is that how you approach the outer-loop processing of the list commands?

[pier4r]

Thanks david. So maybe go fer list would be still not as efficient. But surely faster than userRPL (well that's is well known).

[DavidM]

(04-25-2017 06:06 PM)pier4r Wrote:  Thanks david. So maybe go fer list would be still not as efficient. But surely faster than userRPL (well that's is well known).

I have no direct experience with GoferLists, so I'm not qualified to render any opinions on its performance. My comments were directed at the built-in list processing commands that UserRPL has. I believe GoferLists is SysRPL-based, so I see no reason it wouldn't perform at least as well as the built-in commands. Possibly better if the algorithms are optimized and/or special-cased in areas that the built-in ones aren't.