[rabbitmq-discuss] topix

Mon Feb 22 12:10:51 GMT 2010

David R. MacIver wrote:

 >> If that's the case, all three fundamental operations can be
 >> implemented in O(1) time where n is number of topics and/or bindings
 >
 > Well, O(log(branching rate for the tree)) (you need to do key lookups at
 > each level), but near enough.

Right. However, in ideal case you'll use hash table for the lookup which 
will get the average case down to a constant.

 >> and O(n) time where n is length of the longest subscription.
 >> Such an algorithm can be turned on by a specific hint passed to
 >> Exchange.Create 'arguments' parameter, or, more transparently, it
 >> can be used as long as subscriptions adhere to "x.y.z.#" pattern and
 >> once there's a non-compliant subscription, matching algorithm can
 >> switch dynamically to a more generic one.
 >
 > I'm not sure this actually needs quite such specific logic. It should 
be possible
 > to add rules which means this behaviour falls out naturally rather 
than having a sharp transition between the two behaviours e.g. in the 
NFA approach suggested the only special handling needed would be to make 
sure that binding the pattern # was sensibly implemented as a "go 
straight to queue, do not pass go, do not collect O(key length) 
operations" node rather than doing a full scan of the rest
 >  of the key.

Ack.

 > 'though I guess that sparks another question: How long are the keys 
people are
 > actually using with this?

My experience from stock trading sphere is that most keys are 3-5 items 
long, the longest being somewhere in the range of 15-20 items.

Martin