18 Sep
2010
18 Sep
'10
5:07 p.m.
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]).