[Haskell-cafe] None brute-force BWT algorithm

[Henning Thielemann]

On Thu, 23 Jun 2011, larry.liuxinyu wrote:

> I think that version is still a brute-force solution. The only difference is that it uses EOF (sentinel) so that it can sort the
> suffixes instead of rotations.
> However, the big-O complexity is the same.
> 
> Let's take the rbwt for example:
> 
> > rbwt xs = let
> >     res = sortBy (\(a:as) (b:bs) -> a `compare` b) (zipWith' (:) xs res)
> >   in
> >     tail . map snd . zip xs $ head res
> Here we can see that, although the infinity res is lazy-evaluated, it actually sorts the matrix N times, adding one column per
> evaluation.

Did you also compare the actual runtimes? As far as I understand, the 
matrix in Bertram's code is sorted once. Sharing of data avoids 
recomputation.