Hi Ketil,
Ketil Malde schrieb:
"Gü?nther Schmidt" <[email protected]> writes:
let say I got an unordered lazy list of key/value pairs like
[('a', 99), ('x', 42), ('a', 33) ... ]
and I need to sum up all the values with the same keys.
So far I wrote a naive implementation, using Data.Map, foldl and insertWith.
Data.Map.fromListWith (+)
The building of this map is of course a bottleneck, the successive
processing needs to wait until the entire list is eventually consumed
the Map is built and flattened again.
Sure this is not an artifact of the laziness of foldl?
well I can't really see how the map could be consumed *while* it's still
being built, I just don't see it. (I'm using foldl' and insertWith', sry
for not saying so initially).
Is there another way of doing this, something more "streaming
architecture" like?
I don't see how you can do this much better - for a small, fixed set
of keys, you could use an (STU) array for the sums, but it depends if
the added complexity is worth it. You're already doing a single pass
over the data.
-k
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
