[Haskell-cafe] Quadratic complexity though use of STArrays
daniel.is.fischer at web.de
Tue Sep 22 16:57:46 EDT 2009
Am Dienstag 22 September 2009 22:31:48 schrieb Daniel Fischer:
> 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
Yep. Strictifying things gives the expected linear behaviour.
swap a n m = do
[n',m'] <- mapM (readArray a) [n,m]
mapM (uncurry $ writeArray a) [(m,n'),(n,m')]
you don't actually read and write values, but ever longer thunks.
Changing swap to
swap a m n
vm <- readArray a m
vn <- readArray a n
writeArray a n $! vm
writeArray a m $! vn
is all you need to do (as long as your values have a simple type).
More information about the Haskell-Cafe