Re: LOGO-L> Re: apl:deal porting to LOGO

[Peter Tomcsanyi <tomcsany@internet.sk>]

At 16:23 17.8.1998 -0500, fajoy@uio.satnet.net wrote:
>> to deal :n :set 
>>  if :n = 0 [output []]
>>  let "picked pick :set
>>  output fput :picked deal :n - 1 butmember :picked :set
>> end
>> 
>> A shorter solution is possible in SuperLogo:
>> 
>> to deal1 :n :set
>>  output item list 1 :n shuffle :set
>> end
>
>Which of the two would be more efficient?
>
>I know "remove" is expensive because it has to look up every element 
>of the list to find out which ones to remove. And it has to run n times.
>
>On the other hand, I thing shuffing is more expensive. I believe it is done 
>by swapping two randomly choosen elements of the list. And this is done m
times,
>with m>n so that the we get a good shuffle.

In Superlogo the solution with shuffle (deal1) is much quicker.
The reason is that shuffle is a primitive and it does not exchange elements
but rearranges the whole list using lower level access to Logo data
structures (it uses pointer replacements, which is impossible in Logo
language). To shuflle a list of 10000 elements takes on my computer just 10s.
If you will not use SuperLogo and therefore you have to implement SHUFFLE
as a Logo command, then the results can be significantly different.
This is always the case with an interpreter: commands implemented inside
the interpreter run musch quicker than commands implemented in the language
which is interpreted.

Here are some empirical measurements on my computer:
I repeated deal and deal1 1000 times for three different length of the list
(the numbers were chosen to represent number of playcards in three card
palys I know) and two different :n.

DEAL    
         32    54    108
:n = 8   13s   15s    20s
:n = 16  25s   29s    42s


DEAL1

         32    54    108
:n = 8   1.1s  1.5s  2.4s 
:n = 16  1.2s  1.5s  2.4s




Peter Tomcsanyi
tomcsany@internet.sk
---------------------------------------------------------------
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.