[Haskell-cafe] Nice way to calculate character frequency in a
string
Benjamin Franksen
benjamin.franksen at bessy.de
Thu Oct 27 16:56:49 EDT 2005
On Thursday 27 October 2005 10:29, Ketil Malde wrote:
> Scherrer, Chad wrote:
> >Sorry to drag this thread out, but here's one more thing you might
> >try...
>
> (This is the café, isn't it? :-)
>
> Another option is perhaps to pack both char and count in one Int and
> use some kind of Set.
> This should save some space, and possibly time as well (presuming
> bitwise ops are less expensive
> than pointer dereferences, which I believe have been a safe
> assumption since the mid-90s), but requires a Set being searchable
> for ranges. (Do any of the implementations support this, BTW?)
It's interesting that you mention this. I have been working for some
time now on a library implementation of 2-3 finger search trees (as
described in a paper by Ralf Hinze, see
http://www.cs.bonn.edu/~ralf/publications/IAI-TR-98-12.ps.gz). These
beasts give you quite efficient split (aka partition) operations:
complexity is amortized O(d,n-d), where d is the distance from the
split key to the smallest element (or the largest, if you like). You
can splice out a range using two consecutive single point splits. OTOH,
I have been considering to implement a specialized range operation
which could be even more efficient.
You could also use the similar (but *much* easier to implement)
annotated 2-3 finger /leaf/ trees (see
http://www.cs.bonn.edu/~ralf/publications/FingerTrees.pdf). As far as I
understood, these are not quite as good as the above mentioned node
trees, but they differ only by constant factors.
Ben
More information about the Haskell-Cafe
mailing list