On 24/03/11 06:10 PM, Olivier Guilyardi wrote:
Sorry. I still have plenty of releases left on the table before I have
time to get around to this stuff... and yes, I took a little break for a
I also should have mentioned I found an old radix tree implementation of
mine that should be pretty solid. I will contrast/compare these when I
get the chance.
The radix tree is for interning URIs. You could also use a hash table,
but hash tables are ugly and clunky IMO, I prefer more elegant
structures that grow organically (and radix trees are simple to
implement), and as mentioned we have many common prefixes here which
makes it a suitable choice.
Interning URIs is used to get a number to represent a URI string. This
is necessary for even remotely appropriate performance because it means
statement lookup is a series of integer comparisons, and not a series of
vastly more expensive (and redundant) string comparisons.
For a store of n statements with URIs of length k, a search will thus be
O(lg(n) + k). Without interning it would be O(k*lg(n)), and have more
fragmented memory access as well.
Linux-audio-dev mailing list