Programming puzzles: processing lists!

[pier4r]

(10-31-2017 12:31 PM)DavidM Wrote:  ...

list 2000 elements 0 or 1 (random)

list 1 OVER SWAP MPOS LRMOV
: 9.57s on my 50g


list \->STR ".1" "" SRPL DROP OBJ\->
: 13.68s seconds on my 50g

Not bad in both cases.

[DavidM]

(11-03-2017 09:42 PM)pier4r Wrote:  

Code:


\<< 12 N 0.1 * +  \>>
1
2118
1
SEQ

A shorter form of what you've already got above would be:

Code:

'N' DUP
12.1
223.8
0.1
SEQ

That completes in about 7.1s as opposed to your original at 12.4s.

[pier4r]

(11-03-2017 11:15 PM)DavidM Wrote:  A shorter form of what you've already got above would be:

That completes in about 7.1s as opposed to your original at 12.4s.

Interesting, so assuming that the iteration costs in a similar way, the difference was in the function to execute.

[DavidM]

(11-04-2017 07:56 AM)pier4r Wrote:  Interesting, so assuming that the iteration costs in a similar way, the difference was in the function to execute.

Definitely.

SEQ takes the arguments you give it and constructs a User RPL program out of them. That program is then executed, and anything placed on the stack more recently than the original arguments are imploded into a list.

In the case of your original SEQ invocation, this is the program that SEQ creates:

Code:

«
   1. 2118. FOR N
      « 12. N .1 * + » EVAL
   NEXT
»

This is the RPL program created by the simplified version:

Code:

«
   12.1 223.8 FOR N
      'N' EVAL
   .1 STEP
»

So you can see there's much less going on in the innermost loop in the second version, which accounts for the difference. The overhead of the FOR loop structure is roughly the same in both cases.

This also gives a clue for a somewhat faster version, though there's more to type so I didn't go that direction earlier. Looking at the output of the second version, you can see that there's no need to actually EVAL a single quoted local variable -- it's simpler to place the ID in the inner loop without the quotes. Since we're using constants for all the arguments here, we already know how many elements will be in the final list. That makes it easy to use the following to create the same list result:

Code:

«
   12.1 223.8 FOR N
      N
   .1 STEP
   2118 \->LIST
»

Execution time: 4.9s

I know you didn't want to use any non-native commands for this, but I can't help myself. This is actually a really good example of a situation where LSEQR comes in handy, and the fact that the step value is 0.1 makes this even easier:

Code:

«
   121. 2238. LSEQR
   10. /
»

Execution time: 4.1s, most of which is spent doing that final division. Building the initial list of integers only takes 0.31s.

[pier4r]

Thanks David. I don't mind other commands if they are compact .

Anyway my point was not to create that particular list quicker. Rather if there was something better than SEQ to create a list based on a sequence of numbers.

[StephenG1CMZ]

I have implemented #32 multiple GET on the Prime.

Code:



 EXPORT GETLST(LST,GETLST)
 //Solves Puzzle #32. POSN≥0.
 BEGIN
 LOCAL II;

  IF SIZE(GETLST) THEN
   RETURN MAKELIST(LST(GETLST(II)),II,1,SIZE(GETLST));
  END;
  RETURN {};//ASKED TO GET NOTHING
 END;

Update: As typed here, the procedure name and parameter name are the same.
I'd suggest they shouldn't be, to minimise the risk of SIZE() measuring the wrong one.

(A version with error checking is in my List API: ListGETLIST
http://www.hpmuseum.org/forum/thread-9411.html)

[DavidM]

(11-04-2017 07:22 PM)pier4r Wrote:  Thanks David. I don't mind other commands if they are compact .

Anyway my point was not to create that particular list quicker. Rather if there was something better than SEQ to create a list based on a sequence of numbers.

I guess that depends on your definition of "better than SEQ".

LSEQ/LSEQR were created for the scenario where you know the start and stop values and the step value is 1 or -1. If that's a good fit, then those commands require fewer arguments (and are 10-30x faster) than SEQ. Even if the step value doesn't match, they may still be useful if the input and output can be easily modified to make it fit (as in your above example). They do require the input to be in the form of integers, though. So if that can't be done easily, they aren't a good fit and wouldn't be appropriate.

[DavidM]

(11-05-2017 10:04 PM)StephenG1CMZ Wrote:  I have implemented #32 multiple GET on the Prime.

That's a nice set of list functions you've created, Stephen! I don't have a Prime to use them on, but they seem to cover a lot of ground. Nice work!

[StephenG1CMZ]

(11-07-2017 01:55 PM)DavidM Wrote:  

(11-05-2017 10:04 PM)StephenG1CMZ Wrote:  I have implemented #32 multiple GET on the Prime.

That's a nice set of list functions you've created, Stephen! I don't have a Prime to use them on, but they seem to cover a lot of ground. Nice work!

Thanks David.
Version 1 now also implements a solution to puzzle #40 (remove all instances of an item from the list).

[pier4r]

(11-07-2017 01:45 PM)DavidM Wrote:  I guess that depends on your definition of "better than SEQ".

LSEQ/LSEQR were created for the scenario where you know the start and stop values and the step value is 1 or -1. If that's a good fit, then those commands require fewer arguments (and are 10-30x faster) than SEQ. Even if the step value doesn't match, they may still be useful if the input and output can be easily modified to make it fit (as in your above example). They do require the input to be in the form of integers, though. So if that can't be done easily, they aren't a good fit and wouldn't be appropriate.

Thansk for the input, and nice to see that slowly another library is being done. StephenG1CMZ I recommend you to see the library of DavidM to get some more inspiration!

[StephenG1CMZ]

I have now also implemented a solution to #31 frequencies in my List API for the Prime.
http://www.hpmuseum.org/forum/thread-9411.html Version 1.1.
I was surprised to note that implementing the simple solution of first sorting the list, then producing the already-sorted frequencies, seemed quicker than producing the values and frequencies of the unsorted list and then sorting those.

[pier4r]

Just discovered, thanks to the work of Terje here (I wonder why HP does not release a pdf with the prime help. It would make things way easier, especially for search and bookmarking) that #41 on the prime can be done with the function cumSum.

The more I look into the prime, the more I see a quite extended standard library of commands.

[StephenG1CMZ]

(12-30-2017 02:39 PM)pier4r Wrote:  Just discovered, thanks to the work of Terje here (I wonder why HP does not release a pdf with the prime help. It would make things way easier, especially for search and bookmarking) that #41 on the prime can be done with the function cumSum.

The more I look into the prime, the more I see a quite extended standard library of commands.

One oddity I just noticed was that cumSum({}) returns 0...
Many built-ins don't handle empty lists well.
But what should the answer be?
{} means you can distinguish input {} from input {0} if desired
Whereas
{0} treats {} as {0}, just like my ListSigmaSum procedure (whereas the builtin SigmaSum fails).
I am thinking returning {0} would be better, assuming there is no good reason to return 0.

Eddie W Shore has a workaround for some other oddities here:
http://www.hpmuseum.org/forum/thread-381...ght=cumSum

[pier4r]

For a discussion between {} and "error" (same problem in the 50g) I would point to the thread of the library of DavidM, where the question about consistency was discussed.

here: http://www.hpmuseum.org/forum/thread-8555.html

[pier4r]

added #42 and #42.1

[DavidM]

(11-03-2017 09:42 PM)pier4r Wrote:  A way that is still feasible to type on the 50g (therefore no help from a qwerty) but it is also quite quick to generate a list equivalent to the following:

Code:


\<< 12 N 0.1 * +  \>>
N
1
2118
1
SEQ

Just thought I'd return to this one, given the new LASEQ command in ListExt:

Code:

12.1
0.1
2118
LASEQ

...yields the result list in about 0.43s on a 50g. It also has about the least amount of required typing you can have for a problem like this, especially if you simply select the command from a menu.

[DavidM]

#39:

Code:

\<<
  UNROT
  DUP2 GET
  4 ROLL +
  PUT
\>>

#41:

Code:

\<<
  1
  \<<
    NSUB 1 -
    { OVER + }
    IFT
  \>>
  DOSUBS
\>>

[John Keith]

#41 is easy with GoferLists:

\<< + \>> Scanl1

[pier4r]

user rpl question:
- With all the talking about stack and lists here: http://www.hpmuseum.org/forum/thread-8555.html it seems that the stack is maintained as array of pointers while list, on extension, have to be duplicated. Therefore the larger they are, the more intensive is to extend them of 1 element.

If instead I size a list large enough to likely keep the output I expect, therefore only modifying its elements. Is it any faster than extending a list?

In other words is:
{ ... large list with, say, 200 elements } 1 +
faster or slower than
{ .... list with 201 elements } 201 1 PUT

If I remember correctly the knowledge shared by DavidM, with PUT the list will be exploded and modified, but this may be less costly than copying it entirely.

[DavidM]

(05-26-2018 10:17 AM)pier4r Wrote:  If instead I size a list large enough to likely keep the output I expect, therefore only modifying its elements. Is it any faster than extending a list?

Unfortunately, no. In fact, appending a single element to the end of a list is probably still faster than using PUT, since there's less work going on to determine segment sizes before copying to the new list object.

Even with PUT, an entirely new list is built by copying everything before the new element, then the new element, then everything after the new element into the new list object. If you think about the nature of RPL lists for a moment, you'll understand why this is: since the list contains the actual objects themselves (instead of pointers), a newly "PUT" object may be a different size than the previous one. Even if it is the same size, I'm pretty sure the code just uses the same copy-to-a-new-list method. You can see this simply by timing some tests.

To be fair, I have to point out that copying memory from one location to another on the ARM-based systems is helped substantially due to the inclusion of some native ARM pseudo-opcodes that were created for the Saturn emulation layer. Skipping objects (to determine sizes or simply to find the next item) and copying memory blocks are such common operations on these systems that it made sense for the designers to create ARM-native opcodes to do the heavy lifting (along with some other common functions). This is one of the reasons that it's hard to guesstimate how much faster equivalent code will run on the ARM systems compared to a native Saturn CPU -- if there's lots of skipping and copying going on, the code will likely run much faster on the ARM systems than other code that is mostly bogged down just by number crunching.

While keeping objects on the stack instead of in list form during the execution of a program or subroutine requires "stack juggling" within your code, it will almost always pay off in performance gains.