[REBOL] Re: Question and comment about randomizing a block of values
From: agem:crosswinds at: 19-Jun-2001 13:54
RE: [REBOL] Re: Question and comment about randomizing a block of values
Hi Joel
[joel--neely--fedex--com] wrote:
> [agem--crosswinds--net] wrote:
> >
> > its in my trick-bag now. :) but card-games, ~50?
> >
>
> Clearly there's a trade-off between speed and readability.
> At ~50 there's not much speed gain to worry about, but
> for larger numbers there's an advantage to be had.
>
> OBTW, I did the benchmarking with a slightly (again!)
> modified version of my SHUFFLED-IOTA, given below. Using
> the square of N for the high-order part limits the maximum
> block size to ~1K. Inspired by your larger random range,
> I tricked M to use most of the remaining bits for high-
> order randomization. Hence:
>
> shuffled-iota1: func [n [integer!] /local m f c r] [
> m: to-integer (2 ** 30) / n
> c: -1
> r: make block! n
> loop n [append r (n * random m) + c: c + 1]
> sort r
> forall r [change r r/1 // n + 1]
> head r
> ]
>
> A quick bit of benchmarking with the above vs. your version
> with SORT/SKIP (generating 1000 blocks with 2000 entries each)
> showed times of 5:12 vs. 6:38, about 27% longer for SORT/SKIP.
>
Wow. thats close. 27% for being more readable.
IMHO of course ;-) if, it may serve as doc for your version,
then presenting the modulo trick to pack two numbers in one?
i think your main advantage about my first version is,
it depends linear on n instead of this n*n with the remove-move.
this advantage should be kept with the sort/skip?
of course programming c 27% would be horrible,
there i'm happy place optimized code everywhere :)
if i could only motivate me to write some..
a, bitmap/graphics! oh no, 3d now. matrices.
hey, lots of zeros! could unroll this loops a bit, some lines rebol..
AARGH! how to put the c in blocks?
well, hoping the compiler will do it..
what do you say, recursive templates? hey, works! cool!
needs only some years to get the right grip..
OK, going OT, but c, old friend.. ;-)
> >
> > performance-hint for great blocks: don't use remove.
> > poke deck card-no (last deck) clear back tail deck
> >
>
> I guess I'm being dense tonight, but I don't see how that
> last line above shuffles the block.
>
> >> tester: iota 10
> == [1 2 3 4 5 6 7 8 9 10]
> >> poke tester (random 10) (last tester)
> == [1 2 3 4 5 6 7 8 9 10]
> >> poke tester (random 10) (last tester)
> == [1 2 10 4 5 6 7 8 9 10]
> >> poke tester (random 10) (last tester)
> == [1 10 10 4 5 6 7 8 9 10]
> >> poke tester (random 10) (last tester)
> == [1 10 10 4 5 6 7 8 9 10]
> >> poke tester (random 10) (last tester)
> == [1 10 10 4 5 6 10 8 9 10]
>
thank you for the "late" answer. was night here to.
so my undrstanding of your understanding.. ;)
meant it this way:
instead of filling the gap by remove and moving the whole rest of the block,
i fill it with the last element and let the rest in place, then shrink the block
moves 1 element/loop instead of n/2.
you can ignore the shrink-part if you calculate card-no based on index, like
repeat i n-cards: (random length? deck) - i + 1 .. ;+/-1 , my preferred bug
[rebol []
n-cards: 20
deck: copy []
repeat i n-cards [append deck i]
probe deck
random/seed now
shuffled-deck: copy []
loop n-cards [
card-no: random length? deck
append shuffled-deck pick deck card-no
; remove at deck card-no ;replaced with
poke deck card-no (last deck) clear back tail deck
]
probe shuffled-deck
probe sort shuffled-deck
]
> It would "overstrike" a random element with the last element
> of the block, losing the one POKEd on top of.
>
> OTOH, using ...
>
> >> tester: iota 10
> == [1 2 3 4 5 6 7 8 9 10]
> >> insert at tester (random 10) last tester
> clear back tail tester
> == []
> >> insert at tester (random 10) last tester
> clear back tail tester
> == []
> >> insert at tester (random 10) last tester
> clear back tail tester
> == []
> >> insert at tester (random 10) last tester
> clear back tail tester
> == []
> >> insert at tester (random 10) last tester
> clear back tail tester
> == []
> >> tester
> == [6 1 9 8 10 2 3 4 5 7]
>
> .... does get the shuffling done, but now the INSERT is the
> culprit for having to scoot the block elements around.
>
> Have I misunderstood something?
>
> >
> > random is random i hope? ;-)
> >
>
> Perhaps RANDOM/SECURE is more random than RANDOM ... ;-)
>
:-) Carl?
-Volker
