Arrays and arrays

[Ketil Z. Malde]

Hi

Having written a suffix-array based program using lists, I thought I'd
speed it up a bit, and perhaps more importantly, save space, using
arrays.  Basically, the problem is to sort all suffixes of a string,
represented as an array of offsets, alphabetically.

(Does anybody have such code?  Efficient?)

The good news is that space consumption is reduced -- except for a few
weird spikes (which makes me suspect there are many of them, living
for very short durations), memory use is low.

But speed is another issue -- the list based version is a lot faster.
Okay, I use UArrays and permute them by (//), and this operation is
totally dominant in the profile.  Is it correct that GHC is very naive
about updating them, and even small updates cost O(n)?  Is it better
to (//) over few large lists than over many small ones?

I'll try a IOUArray next; however, is there anything else I
could/should try?  I know there has been array sorts implemented
previously, are anybody aware of recent results?

-kzm
-- 
If I haven't seen further, it is by standing in the footprints of giants