Post Reply 
Programming puzzles: processing lists!
02-14-2019, 05:27 PM
Post: #274
RE: Programming puzzles: processing lists!
(02-13-2019 01:30 PM)pier4r Wrote:  So the question arose again "should I avoid expanding lists?".

I was going to add a note here about building/editing elements on the stack within your program being the usual best performer, but John beat me to punch. Smile Fortunately I saw his response before I hit "Post Reply" on this one. So instead I'll say "yeah, what he said!" There's also an opportunity here to highlight a specific issue, though, so I'll address a distinction about the array/vector that you're creating in your example.

The performance of your third program (the vector/PUT one) is indeed much better, and I believe the main reason is more subtle than simply using a vector instead of a list as the targeted object type. The performance you are seeing implies that the program is creating a type 3 array object, which in turn implies that the emulated calculator was likely set to approximate mode before the program was loaded. Try adding one simple step to that program and watch what happens.

Change:
Code:
0 1000 NDUPN \->ARRY
to
Code:
0 R\->I 1000 NDUPN \->ARRY
(ie. simply add "R\->I" after the first "0")

I believe you'll find that the performance advantage disappears after making that change.

If the calculator is set to exact mode prior to entering/editing the program, the R\->I isn't even required (since the 0 is compiled as an exact integer in that case). If the values going into the array are symbolic (exact integers are considered symbolic for this purpose), the resulting array is created as a type 29 object. It's still an array, but its internal structure is more like a list since the individual elements can be of varying size. This means that it inherits the same inefficiencies of list manipulation.

When you created a type 3 array in your earlier test, you gained an efficiency inherent to that type of object: each element takes up the exact same amount of space, so the offsets to individual elements can be computed in advance and located without having to analyze/traverse all of the preceding elements. That's the main reason that version is faster. It's still making a copy of the original list before making the change, but PUT is far more efficient with a type 3 array object because of how quickly it can locate the target destination within that new copy.

That said, it's still more efficient and usually faster to manipulate items on the stack and then implode into your desired object (list or array) as a last step.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - DavidM - 02-14-2019 05:27 PM



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