Post Reply 
Programming puzzles: processing lists!
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
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - DavidM - 05-26-2018 10:11 PM



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