[Haskell-cafe] Quadratic complexity though use of STArrays

[Daniel Fischer]

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: