Bhavin, > Thanks for the links. We checked the code and I am kicking myself for not > realizing that a basic trie would be all that's needed :). We also noticed > the nice lil optimization to the trie data structure implementation to > reduce storage space requirements :)
It's trading functionality (no sexy regular expressions) for performance... There's still one possibility for optimisation though: If, at any particular place of the tree there's a single-branch node (currently the memory footprint optimisation you've noticed), the associated structure could possibly hold up to say 8 subsequent characters. The idea is that single-branch nodes tend to appear in strings. Consider following example. Plus signs correspond to real branchings while minus signs denote strings of single-branch nodes: animals.dogs --------+++- animals.donkeys --------+++---- animals.ducks --------++--- animals.cats --------+--- The whole point is to significantly lower memory footprint which in turn should have severe impact on performance. Specifically with large search trees it may happen that some parts of the tree are eliminted from the CPU cache. In such case, access to physical memory can slow down the algorithm by an order of magnitude. Thus keeping the data structure as compact as possible will make it much faster, even for sparsely used topics. Thoughts? Martin _______________________________________________ zeromq-dev mailing list zeromq-dev@lists.zeromq.org http://lists.zeromq.org/mailman/listinfo/zeromq-dev
