Post Reply 
Programming puzzles: processing lists!
06-12-2017, 09:41 PM
Post: #142
RE: Programming puzzles: processing lists!
(06-12-2017 07:46 PM)pier4r Wrote:  So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist)
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)
Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

I'm a little surprised that the GET/GETI commands did that well, but I'd guess you'd start to see them slow down a bit as the list sizes grow.

LROT is actually fairly simple, but it does take some time. It basically determines the two sublists that need to be swapped based on the given parameter, makes the sublists, then reassembles them. I might be able to speed it up some with a slightly different approach, but I'm guessing it won't be a significant difference in the final timings. I should add this to my list of things to check, though.

The bulk of the time in the LROT loop is probably from LROT itself. DUP is very fast (it simply copies a pointer, not the actual data), and HEAD is pretty fast as well. My testing on lists of 100 items showed an average timing of .0336 seconds, so a loop of 100 iterations taking 3.36 seconds just for LROT alone would be expected. The remainder of the time for the other commands (and loop overhead) seems reasonable to me.

The internal representation of a list isn't very sophisticated. It's basically a prologue token, each object's data one after the other, and an epilogue token. So any commands that access individual objects within a list have to (literally) traverse/skip each and every object before the one in question in order to access it. In the case of embedded sublists, each element in them also has to be traversed. There's no way to skip over entire embedded sublists, as lists don't contain size information. Even getting the length of a list requires traversing all contained elements. So you can see where the longer a list is, the more time is required to deal with the list's elements.

HEAD is relatively fast because only the first element has to be accessed. TAIL can quickly skip the first element, but it still has to make a copy of the remainder of the list. So it's more sensitive to list size.

I haven't yet traced through DOSUBS and DOLIST to see how they work, but I suspect they do something similar to STREAM (which I have looked at) that allows relatively quick access to list contents by isolating one element at a time in the runstream. That method isn't available to UserRPL programs, as it requires manipulation of the return stack -- a technique that has to be executed very carefully to avoid blowing everything up. 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 - 06-12-2017 09:41 PM

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