[Haskell-cafe] None brute-force BWT algorithm
lemming at henning-thielemann.de
Fri Jun 24 23:03:20 CEST 2011
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
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
More information about the Haskell-Cafe