Programming puzzles: processing lists!

[John Keith]

Another point worth noting is that the time required for replacing or appending list objects is proportional to the square of the list size. This means that you will see a "knee" in the curve of processing time with around 100 to 250 objects depending on what proportion of the program's running time is taken by the list operations.

While this means that processing lists in this way is impractical for larger lists, it also implies that using these list operations on smaller lists does not slow programs down that much.

Manipulating objects on the stack will almost always be the fastest way though.

[pier4r]

yeah but manipulating objects on the stack is not always so possible and even when it is, it is time consuming to maintain for large operations.

Maybe do I have more luck with row vectors (since I want to save numbers) or is the same story?

[John Keith]

In theory vectors should be faster to manipulate than lists since each number is the same size (at least for approximate numbers), but they don't seem to be any faster in practice. Hopefully David can shed some more light on this subject.

[DavidM]

(05-26-2018 09:24 PM)John Keith Wrote:  In theory vectors should be faster to manipulate than lists since each number is the same size (at least for approximate numbers), but they don't seem to be any faster in practice. Hopefully David can shed some more light on this subject.

Well, this gets a little more complicated...

There's actually three different types of "arrays" that a 49-50g knows about. They go by different names, and you might see them listed as:

Type 3/Standard Array
Type 23/Linked Array
Type 29/Symbolic Array

You can pretty much forget about Linked Arrays. There's no way to create them using built-in commands, and I'm not sure how many of the existing built-in commands even know what to do with them. So you really only need to know about the other two.

A Type 3/Standard array is what is created when you use the ->ARRY command with real (approximate) or complex numbers on the stack. The meta data in the header for that object stores the data type and dimensions, so the actual data stored after the header is more compact (without prologues) and always a fixed size. This storage format has another advantage I'll describe in a moment.

A Type 29/Symbolic array is actually very much like a list. It is what you get when you use ->ARRY with exact integers and/or rationals and/or symbolics on the stack. A Type 29 array is a simpler data structure, very similar to a list in that it has a prologue, either raw data elements one after the other (with their own prologues) or "sub-"arrays for multi-dimensions, then an epilogue at the end (which just happens to be the same as a list). Since every data element is a complete object with prologue, they are usually larger for the same data as a type 3.

There's an advantage that comes from using a type 3 array: PUT works more efficiently with it because all of the data elements are a consistent size. A copy of the original list is still made, but it's easier to determine exactly where the newly PUT object goes, so you'll find that PUT commands perform better with type 3 arrays than with type 29.

You really need to test an array with the TYPE command to know which type it is, though. You can't simply assume that it is type 3 if it contains real or complex elements. In particular, if you create an array by populating a list of reals and then convert it with AXL, you'll get a type 29 array as the result. Some arrays can be converted back and forth between type 29 and 3 with AXM (it depends on what the array contains).

So... it can be to your advantage to use PUT with a type 3 array. It still makes a copy, but it is faster to perform the operation. PUT with a type 29 array is no better than with a list, though.

I doubt I've cleared this up much, but it's the best I can do on a holiday weekend!

[pier4r]

DavidM thanks a lot. First time I see such info (well, it will be true also in the future, if I won't use it).

So I guess for some operations, especially numbers, I will have to start using also row vectors.

The nice part is that the element by element processing is very much like lists with basic operations at least, and what will be missing well, will be subject of discussions/requests/challenges.

Rpl (and its experts) never stops giving new paths to explore.

[pier4r]

(05-26-2018 10:11 PM)DavidM Wrote:  So... it can be to your advantage to use PUT with a type 3 array. It still makes a copy, but it is faster to perform the operation. PUT with a type 29 array is no better than with a list, though.

Another problem is development time. With the list there are a lot of really neat commands, for example LMRPT, thanks to goferlist, listExt, lsort and what not. With vectors I presume I will have to create (or search) a lot of equivalents by myself as they are not available in libraries (even better optimized libraries).

Plus from your description one should be really careful in creating a vector and - you don't state it - but I feel the increment in speed would be noticeable only with many many many operations.

[pier4r]

Stumbled on an expected behavior

In userRPL having
{ { 1 2 } { 2 3 } { 3 4 } } \GSLIST (sigma list) returns
{ 1 2 2 3 3 4 }

Noticed while I wast trying options to sum sublists of a list.

At the end something like this should be ok.

Code:


  listSumSubList
  \<<
    \<< ADD \>>
    STREAM
  \>>

I'll add it here when the wiki4hp will work for me. http://www.hpmuseum.org/forum/thread-10271.html

Another point is that one has a list of sublists of the same dimension and one would like to know the average value of a particular position across the sublists. Say
{ { 1 2 3 } { 2 3 4 } { 3 4 5} } what is the average value in the 3rd position of the sublists?
So far I thought that having the sum of the sublists and then dividing for the number of lists, then picking the wanted element is the fastest (also in terms of code readability) way to reach the solution. Picking only the k-th element from every sublist and keeping a local sum and then computing the average should be more costly at runtime and in terms of readability.

[DavidM]

(01-27-2019 11:49 AM)pier4r Wrote:  Stumbled on an expected behavior
...

This topic comes up from time to time, and is the source of confusion for many people. I suppose we'll never know why the original RPL designers decided to make "+" for lists a concatenation command instead of following the model already used by -, *, and /. Since ΣLIST uses repeated applications of "+", it shares the same fate.

Your proposed alternative is exactly what I would do in that situation.

(01-27-2019 11:49 AM)pier4r Wrote:  Another point is that one has a list of sublists of the same dimension and one would like to know the average value of a particular position across the sublists. Say
{ { 1 2 3 } { 2 3 4 } { 3 4 5} } what is the average value in the 3rd position of the sublists?

Just using the built-in commands, you could do something like the following:

Code:

\<<
   1 \<< 3 GET \>> DOSUBS
   DUP \GSLIST SWAP SIZE /
\>>

That is reasonably compact, and I believe fairly straightforward in terms of readability.

When I read the phrase "a list of sublists of the same dimension" followed by the idea of performing numerical processing on the same data, I also start to think that it may be better to use an array instead of a list. It depends on the processing you need to perform, of course, but some of the array commands may be handy here.

Let's first convert the list to an array with AXL:

Code:

{ { 1 2 3 } { 2 3 4 } { 3 4 5} } AXL

...which yields:
[[ 1 2 3 ]
[ 2 3 4 ]
[ 3 4 5 ]]

Now we can use COL- to extract the third column. Since we aren't concerned with the rest of the array, that can be discarded with NIP:

Code:

3. COL- NIP

...which yields:
[ 3 4 5 ]

We can then determine the average (or some other result) as needed. In this particular case, the average takes a couple more steps than with a list, but it's not too bad. Other types of numeric processing may actually be simpler with an array than if the data is in list form:

Code:

\<<
   OBJ\-> EVAL
   DUP \-> count
   \<<
      2 SWAP START + NEXT
      count /
   \>>
\>>

[pier4r]

Thanks !

Yes arrays and matrices would be pretty powerful if, somehow, their processing would cost similarly to list (or having the same amount of helpful list commands. For example there is no sigma row or sigma array, while there is sigma list to get the sum of the numbers). Instead at times they are slow, especially with large matrices.

Or maybe I am influenced by past experiences. I didn't touch matrices for a while.

[John Keith]

(01-27-2019 11:49 AM)pier4r Wrote:  Another point is that one has a list of sublists of the same dimension and one would like to know the average value of a particular position across the sublists. Say
{ { 1 2 3 } { 2 3 4 } { 3 4 5} } what is the average value in the 3rd position of the sublists?
So far I thought that having the sum of the sublists and then dividing for the number of lists, then picking the wanted element is the fastest (also in terms of code readability) way to reach the solution. Picking only the k-th element from every sublist and keeping a local sum and then computing the average should be more costly at runtime and in terms of readability.

Though it seems counterintuitive, list processing commands on the HP 50g are usually faster than array commands. The following short program will return a list of the last elements of each sublist:

Code:


\<< DUP LXIL SWAP SIZE LDIST LPOPR NIP
\>>

Averaging (or any other operation) can then be performed on the resulting list. You can also use n GET instead of LPOPR NIP to get any nth element of each sublist.

BTW, your example list makes this process hard to visualize because it is its own transpose! Try {{ 1 2 3 }{ 4 5 6 }{ 7 8 9 }} instead.

[DavidM]

(01-27-2019 06:55 PM)pier4r Wrote:  Thanks !

Yes arrays and matrices would be pretty powerful if, somehow, their processing would cost similarly to list (or having the same amount of helpful list commands. For example there is no sigma row or sigma array, while there is sigma list to get the sum of the numbers). Instead at times they are slow, especially with large matrices.

Or maybe I am influenced by past experiences. I didn't touch matrices for a while.

I was thinking more of things like matrix multiplication (vs. Hadamard product), creating constant arrays, identities, etc. The commands can simplify the coding, even if the processing isn't as speedy. I suppose it depends entirely on the processing that is needed.

[pier4r]

Yes. It is also true that through matrix operations, see multiplication, one can achieve quite a bit (with multiplication you can get a sum). If one is not used to it though (me), it doesn't come to mind as a "indirect command" like "sigma array".

I'll have to open the "processing matrices!" thread (together with the "processing strings!" that still is in limbo).

[DavidM]

(01-27-2019 07:18 PM)John Keith Wrote:  

Code:


\<< DUP LXIL SWAP SIZE LDIST LPOPR NIP
\>>

Well if you only need the last column (and you're going to allow external libraries ), here's another option:

Code:

« DUP LCLLT SWAP SIZE LLAST »

[John Keith]

(01-27-2019 07:54 PM)DavidM Wrote:  

(01-27-2019 07:18 PM)John Keith Wrote:  

Code:


\<< DUP LXIL SWAP SIZE LDIST LPOPR NIP
\>>

Well if you only need the last column (and you're going to allow external libraries ), here's another option:

Code:

« DUP LCLLT SWAP SIZE LLAST »

Yes, shorter and simpler. I posted my code because I use

Code:


\<< DUP LXIL SWAP SIZE LDIST 
\>>

as a list transpose. In fact,

Code:


\<< AXL DUP LXIL SWAP SIZE LDIST AXL
\>>

is faster than the built-in TRAN for matrices.

[pier4r]

(01-28-2019 07:10 PM)John Keith Wrote:  Yes, shorter and simpler. I posted my code because I use

Code:


\<< DUP LXIL SWAP SIZE LDIST 
\>>

as a list transpose. In fact,

Code:


\<< AXL DUP LXIL SWAP SIZE LDIST AXL
\>>

is faster than the built-in TRAN for matrices.

List transpose? Could you elaborate more with a couple of use cases and/or examples?

The second code is going to end in the userRPL library on wiki4hp (that today works for me, yay!). And added! http://www.wiki4hp.com/doku.php?id=rpl:s...=revisions
http://www.hpmuseum.org/forum/thread-10271.html

[John Keith]

(01-28-2019 07:37 PM)pier4r Wrote:  List transpose? Could you elaborate more with a couple of use cases and/or examples?

Matrix transpose basically swaps rows for columns.

Code:


[[ 1 2 3 ]
 [ 4 5 6 ]
 [ 7 8 9 ]]

becomes

[[ 1 4 7 ]
 [ 2 5 8 ]
 [ 3 6 9 ]]

By "list transpose" I mean the analogous operation for a list of lists:

Code:


{{ 1 2 3 {} 4 5 6 }{ 7 8 9 }}

becomes

{{ 1 4 7 }{ 2 5 8 }{ 3 6 9 }}

You can see that

Code:


\<< AXL DUP LXIL SWAP SIZE LDIST AXL
\>>

does the same thing as the built-in command TRAN.

Though as David pointed out my code in the earlier post was unnecessarily long, I think the ability to transpose lists like one would matrices is generally useful.

[Thomas Klemm]

(01-28-2019 07:37 PM)pier4r Wrote:  List transpose?

Maybe a bit off topic, but here's a party trick to transpose a matrix in Python:

Code:

>>> matrix = [[1, 34, 46, 31], [32, 40, 82, 40], [30, 16, 24, 18]]
>>> zip(*matrix)
[(1, 32, 30), (34, 40, 16), (46, 82, 24), (31, 40, 18)]

Found in: Dissecting a code golf challenge

Cheers
Thomas

BTW: The matrix is a list.

Code:

>>> type(matrix)
<type 'list'>

[Thomas Klemm]

(01-28-2019 08:16 PM)John Keith Wrote:  I think the ability to transpose lists like one would matrices is generally useful.

Here's a program to transpose a list for the HP-48GX:

Code:

« OBJ→ → n
  « n
    « n →LIST
    » DOLIST
  »
»

Example:

{ { 1 2 3 } { 4 5 6 } }
→
{ { 1 4 } { 2 5 } { 3 6 } }

Cheers
Thomas

PS: That's how the Python program works.

---

Edit: Fixed typo that John Keith spotted in post #260.

[pier4r]

(01-28-2019 08:16 PM)John Keith Wrote:  By "list transpose" I mean the analogous operation for a list of lists:

Nice little idea there! Adding that too.


Edit. Thomas had one pretty nice. Well done there! Added it too.
Sure using only RPL built in is also valuable (for those that are not so updated about extra glorious libraries)
http://www.wiki4hp.com/doku.php?id=rpl:s...=revisions

[John Keith]

(01-28-2019 08:43 PM)Thomas Klemm Wrote:  Here's a program to transpose a list for the HP-48GX:

Code:

« OBJ→ → n
  « n
    « n →LIST
    » DOLIST
  »
»

Example:

{ { 1 2 3 } { 3 4 5 } }
→
{ { 1 4 } { 2 5 } { 3 6 } }

Nice elegant program, Thomas.
Shouldn't the result be {{ 1 3 } { 2 4 }{ 3 5 }} ?