24 Jun
2011
24 Jun
'11
9:03 p.m.
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.