On Saturday 18 September 2010 22:42:57, Luke Palmer wrote:
> I think this is O(n) time, O(1) space (!).
>
> lastk :: Int -> [a] -> [a]
> lastk k xs = last $ zipWith const (properTails xs) (drop k xs)
> where properTails = tail . tails
>
> Luke
No, it's O(k) too. You zip [[x_n, x_{n+1}, ... ], ... ] with
[x_{n+k}, ... ], so all of [x_n, ..., x_{n+k}] stays in memory.
It's *very* nice though, and scales better than my stuff (but my stuff is
faster for small k [< 1000, here, YMMV]).
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
