[clean-list] Fastest shuffle with Clean?
CaptnJamesKirk@aol.com
CaptnJamesKirk@aol.com
Tue, 11 Sep 2001 13:26:38 EDT
Greetings all,
I am new to FP and Clean, and I need some help here. A couple of questions:
My first question is how to implement the fastest shuffle possible in Clean. I am writing what can best be described as a simulation, and at the core is an array that needs to be shuffled up to 1 billion times during the course of a simulation run. The term "shuffle" is used in the traditional sense: items in the array are randomly swapped with other items in the array (i.e., the array is *not* just populated with random values). Here is how I am attempting to do it:
shuffleArray :: *{#Int} !Int -> *{#Int}
shuffleArray ar top
| top < 0 = ar
| otherwise
#! r = randomInt mod (top+1)
#! rnd_elem = ar.[r]
#! top_elem = ar.[top]
= shuffleArray {ar & [r]=top_elem, [top]=rnd_elem} (top-1)
Is this the most efficient (read: fastest) way to shuffle an array in Clean? Also, perhaps I'm assuming this works in a way other than it does. Does this return the *same* array (now shuffled), or does it return a new array consisting of the shuffled elements? (Actually, I guess it doesn't really matter much from an implementation perspective, but I'm still not sure how it works in this regard.) Maybe this will work better when/if Clean 2.0 is released.
My other question involves the randomInt function, which isn't implemented yet. I was first developing this project in C and used the MersenneTwister generator. It was chosen because the period of the generator must be extremely large due to the number of calls to it over the course of a simulation. The Clean version of the MersenneTwister returns an infinite list instead of a new random number at each call. Given that billions of calls are made to the generator, wouldn't this result in overflow? Perhaps it would be best if I rewrote the MersenneTwister function so that it used a fixed-size array that is replenished when full, or some other method similar to the C version?
Any guidance would be greatly appreciated!
Thanks,
John