[Haskell-cafe] Quadratic complexity though use of STArrays

Daniel Fischer daniel.is.fischer at web.de
Tue Sep 22 16:31:48 EDT 2009

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.


> 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:

More information about the Haskell-Cafe mailing list