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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
