Post Reply 
Programming puzzles: processing lists!
05-26-2018, 08:00 PM
Post: #241
RE: Programming puzzles: processing lists!
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.
Find all posts by this user
Quote this message in a reply
05-26-2018, 08:27 PM
Post: #242
RE: Programming puzzles: processing lists!
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?

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
05-26-2018, 09:24 PM
Post: #243
RE: Programming puzzles: processing lists!
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.
Find all posts by this user
Quote this message in a reply
05-26-2018, 10:11 PM
Post: #244
RE: Programming puzzles: processing lists!
(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... Smile

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! Smile
Find all posts by this user
Quote this message in a reply
05-26-2018, 10:19 PM (This post was last modified: 05-26-2018 10:24 PM by pier4r.)
Post: #245
RE: Programming puzzles: processing lists!
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.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
05-27-2018, 07:56 AM
Post: #246
RE: Programming puzzles: processing lists!
(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.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 




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