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: _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
