Am Dienstag 22 September 2009 21:31:08 schrieb Dan Rosén:
Dear haskell-cafe users,
I am constructing a shuffle function: given an StdGen and a list, return the list permuted, with all permutations of equal probability.
There is the simlpe recursive definition: generate a number from 1 to length list, take this element out from the list, call the function recursively on the remaining list and then cons the element on the shuffled list.
A more imperative approach is to make the list an array, and traverse the array in reverse, swapping the iterated element with an arbitrary element less than or equal to the iterator.
These functions are implemented as shuffleRec and shuffleArr, respectively.
What complexity does these functions have?
I argue that the shuffleArr function should be O(n), since it only contains one loop of n, where each loop does actions that are O(1): generating a random number and swapping two elements in an array.
I argue that the shuffleRec function should be O(n^2), since for each call, it creates a new list in O(n), with the drop and take calls, and calls itself recursively. This yields O(n^2).
However, they both have the same runnig time (roughly), and through looking at the plot it _very_ much looks quadratic.
Regarding
shuffleRec :: StdGen -> [a] -> [a] shuffleRec g list = x:shuffleArr g' xs where (n,g') = randomR (0,length list-1) g (x:xs') = drop n list xs = take n list ++ xs'
it's not surprising they take more or less the same time. Make it shuffleRec g list = x:shuffleRec g' xs and prepare to kill the process pretty soon. That doesn't explain the quadratic behaviour of shuffleArr, though. I suspect it's laziness, things aren't actually done until the result is finally demanded, but I would have to take a closer look to really find out.
I am compiling with GHC and I guess there is something in the lazy semantics that confuses me about the complexities, and maybe I have misunderstood how STArrays work.
Any pointers to what's going in is greatly appreciated!
Best regards, Dan Rosén, Sweden
Here is the code: