On Mon, 2008-11-10 at 18:05 +0100, Bertram Felgenhauer wrote:
Alexey Khudyakov wrote:
Hello!
I'm tryig to write efficient code for creating histograms. I have following requirements for it:
1. O(1) element insertion 2. No reallocations. Thus in place updates are needed.
accumArray won't go because I need to fill a lot of histograms (hundrends) from vely long list of data (possibly millions of elements) and it will traverse input data for each histogram.
That's just not true, for GHC's implementation of accumArray at least, which goes via the ST monad.
Perhaps I misunderstood but I think Alexey means that he wants to accumulate several different histograms (ie different arrays) but to only make one pass over the input data. The form of accumArray does not make that possible (unless one managed to pack the different histograms into different parts of the same array). If a fold using a pure persistent map type really is too slow then it should still be possible to do an ST implementation in a reasonably elegant way using a foldr on the input list, accumulating an ST action. Duncan