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