[Haskell-beginners] Eq a => [a]->[a]
daniel.is.fischer at web.de
Thu Dec 3 20:37:11 EST 2009
Am Donnerstag 03 Dezember 2009 20:00:00 schrieb Daniel Fischer:
> You can remove one factor (log k) by checking the size instead of
> f xs = map fst . takeWhile snd . zip xs . zipWith ((. S.size) . (==)) [1 ..
> ] $ cums where
> cums = tail $ scanl (flip S.insert) S.empty xs
> I think for *short* nubbed prefixes, Brent's version is faster, but I've no
> idea yet when short stops (10, 100, 1000?).
Couldn't measure a difference for short lists, starts to become faster than Brent's
between 10^5 and 10^6. The manual loop
f :: Ord a => [a] -> [a]
f xs = go 1 S.empty xs
go i s (y:ys)
| i == S.size s' = y:go (i+1) s' ys
| otherwise = 
s' = S.insert y s
go _ _ _ = 
is ~15% faster.
More information about the Beginners