Re: LOGO-L> *FAST* Shuffling & Dealing

["Tom Lynn" <thl22@cam.ac.uk>]

On 16 Sep 98, at 20:49, Brian Harvey wrote:

> "Tom Lynn" <thl22@cam.ac.uk> writes:
> >Your solution reminded me that item and setitem were two more commands
> >which avoid needing a recursion as well as member and .setbf which I
> >mentioned in my last posting.  Are there any others?
> 
> I don't think that's the main point.  The key is that using an array
> instead of a list make ITEM and SETITEM constant-time operations
> instead of O(N) ones.  (That is, finding the 100th element of an array
> takes no longer than finding the first element, which is not true for
> lists whether it's a primitive or an interpreted procedure doing the
> work.)

Well yes, but the overhead (in MSWLogo at least) is so massively 
concentrated in the parsing that unless you are using very large lists, the 
actual time-order of the operations is pretty much irrelevant.

As an example, take your figure of finding the 100th element.  I've just 
dashed off a quick test, and you may be interested in the results:

Finding the 100th item of a list with ITEM... 0.096 milliseconds
Finding the 100th item of a list without ITEM... 7.96 milliseconds
Copying a list of 100 items into an array... 12.36 milliseconds
Finding the 100th item of an array... 0.096 milliseconds

As you can see, it /doesn't/ take noticeably longer using a list than an 
array, at least for lists of 100 or fewer items.  Even for lists of 1000 
items, it only takes approx 0.3ms longer.  This should be compared with the 
time taken to copy the list into an array, even with ITEM.  So if setitem 
worked for lists as well as arrays, sd could be considerably faster still 
for most lists by cutting out the arrays altogether.  I suspect that the 
arrays were only used because they had to be in order to use setitem.

I think this kind of reasoning argues for making listtoarray and 
arraytolist primitives, so that people don't have to sacrifice performance 
on small lists in order to make theoretical improvements such as this, 
which only become apparent for large lists.

Tom
---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.