On Tue, Jun 28, 2011 at 6:20 PM, Eric Rasmussen <[email protected]> wrote: > It runs quickly, but I naively thought I could outperform it by reworking > "many" to build a vector directly, instead of having to build a list first > and then convert it to a vector: > > manyVec :: Alternative f => f a -> f (V.Vector a) > manyVec v = many_v > where many_v = some_v <|> pure V.empty > some_v = V.cons <$> v <*> many_v
That's an O(n^2) loop, and a thunk leak to boot. If you don't know the size of the vector ahead of time, the only way I can think of to beat Vector.fromList is to use a mutable vector with a "highwater" mark, and double the size if you fill it. At the end, you'd use "unsafeFreeze" to turn the mutable vector into a pure one, and "unsafeTake" to truncate the vector into the correct size. For an example of a similar technique (minus the freezing part), I did a similar thing in the hashtables library: https://github.com/gregorycollins/hashtables/blob/master/src/Data/HashTable/Internal/Linear/Bucket.hs#L45 It's unlikely to be worth the extra effort except for extremely performance-critical code. G -- Gregory Collins <[email protected]> _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
