Re: ternary search trees question
Pete Lomax wrote:
> Pete Eberlein's winning entry solved this problem by holding
> completely separate trees for different word lengths.
This is good idea! Speedup because trees are smaller plus less memory needed.
Downsides: a little more coding and limit to length of words (not necessary
though).
>
>Now I've studied that paper, it looks to me like the C code given
>stores the terminating null found on all C strings, so it does not
>match on the second a of "aba" but the 4th byte, zero.
>
Yes, it looks like it.
I understand it now; first "n" of "abandon" would be stored at the right side of
terminating 0 of "aba".
(This site has clearer code:
http://www.opensource.apple.com/darwinsource/10.4/gccfast-1621.1/libiberty/ternary.c)
But I'll use your first advice.
A hybrid between ternary search tree and digital search tree would be really
fast. For first two or three letters would be used digital search tree (for real
speedy search), for rest of the letters would be used ternary search tree (to not
consume too much memory). Although I'm not sure if digital search tree wouldn't
be too slow when inserting new keys because there would be more writing to disk
needed.
|
Not Categorized, Please Help
|
|
