Programming puzzles: processing lists!
04-22-2017, 11:50 AM (This post was last modified: 04-22-2017 02:04 PM by pier4r.)
Post: #21
 pier4r Senior Member Posts: 1,939 Joined: Nov 2014
RE: Programming puzzles: processing lists!
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} } ?

Wikis are great, Contribute :)
04-22-2017, 03:49 PM (This post was last modified: 04-22-2017 09:15 PM by pier4r.)
Post: #22
 pier4r Senior Member Posts: 1,939 Joined: Nov 2014
RE: Programming puzzles: processing lists!
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.

Wikis are great, Contribute :)
04-24-2017, 04:04 PM
Post: #23
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
04-24-2017, 05:03 PM
Post: #24
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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 \>>
04-24-2017, 07:39 PM
Post: #25
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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!
04-24-2017, 08:27 PM
Post: #26
 pier4r Senior Member Posts: 1,939 Joined: Nov 2014
RE: Programming puzzles: processing lists!

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.

Wikis are great, Contribute :)
04-24-2017, 09:32 PM
Post: #27
 Claudio L. Senior Member Posts: 1,456 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
04-24-2017, 09:35 PM
Post: #28
 Claudio L. Senior Member Posts: 1,456 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
04-24-2017, 09:58 PM
Post: #29
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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!
04-24-2017, 10:00 PM
Post: #30
 John Keith Senior Member Posts: 366 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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
04-24-2017, 11:17 PM
Post: #31
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
04-24-2017, 11:50 PM
Post: #32
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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).
04-25-2017, 01:11 AM
Post: #33
 Claudio L. Senior Member Posts: 1,456 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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).
04-25-2017, 03:01 AM
Post: #34
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
04-25-2017, 01:01 PM
Post: #35
 John Keith Senior Member Posts: 366 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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
04-25-2017, 01:31 PM (This post was last modified: 04-25-2017 01:32 PM by Claudio L..)
Post: #36
 Claudio L. Senior Member Posts: 1,456 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
04-25-2017, 02:32 PM
Post: #37
 pier4r Senior Member Posts: 1,939 Joined: Nov 2014
RE: Programming puzzles: processing lists!
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.

Wikis are great, Contribute :)
04-25-2017, 04:27 PM
Post: #38
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.

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?
04-25-2017, 06:06 PM
Post: #39
 pier4r Senior Member Posts: 1,939 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Thanks david. So maybe go fer list would be still not as efficient. But surely faster than userRPL (well that's is well known).

Wikis are great, Contribute :)
04-25-2017, 06:25 PM
Post: #40
 DavidM Senior Member Posts: 721 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(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.
 « Next Oldest | Next Newest »

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