Re: What is the quickest way to randomize a list?
Re: What is the quickest way to randomize a list?
- Subject: Re: What is the quickest way to randomize a list?
- From: "Arthur J Knapp" <email@hidden>
- Date: Sat, 07 Apr 2001 14:42:55 -0400
>
Date: Sat, 07 Apr 2001 13:46:34 +1000
>
Subject: What is the quickest way to randomize a list? (was Re: Long
>
From: Timothy Bates <email@hidden>
>
I have some handlers for randomizing lists.
Me too. :)
>
Now I see Chris's handler (copied below).
>
Can anyone improve on this for speed?
>
6/04/2001 7:57 AM, "Chris Nebel" <email@hidden> wrote:
>
> repeat with i from length of pin_list to 1 by -1
>
> set current_item to (random number from 1 to i)
>
> do_stuff(item current of pin_list)
>
> tell pin_list -- exchange item current_item with item i
>
> set temp to item i
>
> set item i to item current_item
>
> set item current_item to temp
This type of three-step exchange can be made slightly faster, (we're
only talking milliseconds here), by using AppleScript's pattern
replacement:
tell pin_list
set {item i, item current_item} to {item current_item, item i}
In any case, here is something I very recently threw together.
I would really appreciate the time anyone would be willing to take
to test these handlers for accuracy, "randomness", and speed.
on EraSeconds()
(*
* Seconds since beginning of Mac era. (Has this changed with
* MacOS X ??? )
*)
-- date - date = integer
--
return (current date) - (date "Friday, January 1, 1904 12:00:00 AM")
end EraSeconds
on ajk_unsort_01(lst)
(*
* This is based on several programs contained in
* Robert Sedgwick's "Algorithms in C". Basically,
* I have modified the idea of a universal hash for
* determining a "random" location in a given list.
*)
-- One osaxen call to the "current date" command, instead of
-- a (length of lst)-amount of calls to the "random number"
-- command.
--
-- Only one problem: Because the date data type of AppleScript
-- only works with seconds, two or more calls to this handler
-- in one second won't be random!!!
--
-- Solution: Replace the call to EraSeconds with a single call
-- to "random number", (I think you need a fairly large number).
--
set seed to EraSeconds()
-- We need something to modify seed, (to avoid the possibilty
-- of "collision").
--
set mseed to 31415 -- something to modify seed
set len to length of lst
repeat with i from 1 to len
set j to (seed mod len) + 1 -- our "random" location
set seed to (seed * mseed) mod len -- new seed
tell lst
set {item i, item j} to {item j, item i}
(*
* set temp to item i of lst
* set item i of lst to item j of lst
* set item j of lst to temp
*)
end tell
end repeat
end ajk_unsort_01
set lst to {"a", "b", "c", "d", "e", "f", "g"}
ajk_unsort_01(lst)
lst
Here is a more obfuscated version, (for when you want to show off ;-) ).
The only functional change is one call to "random number" rather than
EraSeconds():
on ajk_unsort_02(lst)
set {s1,s2,len} to {random number from 1 to 100000, 31415, lst's length}
repeat with i from 1 to len
set {j, s1} to {(s1 mod len) + 1, (s1 * s2) mod len}
set {lst's item i, lst's item j} to {lst's item j, lst's item i}
end repeat
end unsort
Arthur J. Knapp
http://www.stellarvisions.com
mailto:email@hidden
Hey, check out:
http://www.LateNightSW.com