## [REBOL] Re: Question and comment about randomizing a block of values

### From: joel:neely:fedex at: 18-Jun-2001 17:18

Hi, Jos, Minor tweaks and a major suggestion... Jos Yule wrote:> My question centers on 'shuffling' the deck. I know there are _many_ > methods of shuffling, with various degrees of randomness. I'd like to > know what you all think about the following 'shuffle' function (this > function is in a class. the list-of-cards var is a class variable): > > shuffle-deck: func [ "Randomizes the list-of-cards" > number-of-passes [number!] > ] [ > for a-pass 1 number-of-passes 1 [ > sort/compare list-of-cards func [a b /local c] [ > c: random 2 > if c = 1 [return true] > if c = 2 [return false] > ] > ] > ] > > Using the sort/compare works really fast, but i'm not sure that this > is the way its meant to be used ;), but it seems to work quite well, > especially with multiple passes. If anyone has any suggestions, > please let me know! >Your existing design above can be simplified and sped up by the following changes: 1) Since you're not using A-PASS within each pass, you can dispense with it (and the overhead of a FOR loop) entirely: shuffle-deck: func [ "Randomizes the list-of-cards" number-of-passes [number!] ] [ loop number-of-passes 1 [ ;... ] ] 2) We can evolve the comparison function to a much simpler state: 2.1) Since RANDOM 2 must always return 1 or 2, we don't need two IF tests. This first step gives us: func [a b /local c] [ either 1 = c: random 2 [return true] [return false] ] 2.2) Now C is unnecessary, so eliminate it: func [a b] [ either 1 = random 2 [return true] [return false] ] 2.3) Now we have a tautology; we're returning the same LOGIC! value that EITHER is testing, so there's no point in restating it: func [a b] [ return [1 = random 2] ] 2.4) A function returns the last expression evaluated, so we don't need to say RETURN anymore: func [a b] [1 = random 2] I've incorporated both of these into the generic block-shuffling function which follows (after a little block constructor): iota: func [n [integer!] /local c r] [ r: make block! n c: 0 loop n [append r c: c + 1] ]>> iota 10== [1 2 3 4 5 6 7 8 9 10]>> iota 2== [1 2] shuffle-block: func [b [block!] n [integer!]] [ loop n [sort/compare b func [a b] [1 = random 2]] ]>> shuffle-block iota 20 10== [15 4 13 19 9 16 6 10 12 18 5 20 3 17 14 7 2 1 8 11] Now for a suggested change to your design... I can think of two problems with using RANDOM inside the comparison function: 1) It adds cycles in the inner-most loop. The cost of calling a user-written comparison function, plus the cost of whatever that function does, can really add up for large blocks. (I'm assuming that the time complexity of SORT is O(n log n) , which is canonical.) 2) Since successive calls on RANDOM make the comparison unstable that can inflate the time complexity of the sort (depending on what sort algorithm is used internally). We can solve both of those by making this observation. You can shuffle a block by copying elements from the block using a set of index values that have been shuffled (as long as each index value occurs exactly once). Consider this little modification on IOTA from above: random-iota: func [n [integer!] /local m f c r] [ f: n + 1 m: f * f c: 0 r: make block! n loop n [append r (f * random m) + c: c + 1] ] This creates a block of (weird-looking ;-) numbers like this:>> foo: random-iota 10== [859 794 850 1115 1193 963 689 536 1219 714] But there's method in my wierdness! Those number actually have the property that their remainders (mod N + 1) are the set of numbers 1 thru N, and their "high-order" bits are random! That means that we can sort them and use their remainders to get a shuffled set of indexes, as follows:>> sort foo== [536 689 714 794 850 859 963 1115 1193 1219]>> foreach n foo [prin [n // 11 " "]] print ""8 7 10 2 3 1 6 4 5 9 Based on that, we can create a shuffling function that generates a block of random indexes and then builds a new block by copying the indexed elements from the original block. shuffled: func [b [block!] /local m n i r] [ r: make block! n: length? b i: sort random-iota n m: n + 1 foreach n i [append r pick b n // m] ] which behaves as follows:>> test-data: iota 20== [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]>> new-data: shuffled test-data== [6 10 9 12 20 19 15 13 7 11 2 5 18 8 16 14 3 1 17 4] This version sorts a block of weird-looking integers which can then have unique index values remaindered out to build the result from the input block. I believe it to be a significant speed improvement (although I haven't had the time to benchmark it ;-) because: 1) It sorts a block of INTEGER! values. I suspect this is the fastest thing we can sort (but I'm sure Holger will let us know if I'm wrong on this detail). 2) It eliminates the need for the "call-back" to a user-written comparison function. 3) It will call RANDOM (within RANDOM-IOTA) exactly once for each element in the original block. Hope this helps! -jn- ___ ___ ___ \/ 2 + \/ 2 = 4 (for sufficiently large approximations of \/ 2 ) joel'dot'neely'at'fedex'dot'com