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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
