sustrik at 250bpm.com
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
> 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.
> 'though I guess that sparks another question: How long are the keys
> 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.
More information about the rabbitmq-discuss