David R. MacIver
david.maciver at lshift.net
Mon Feb 22 12:22:29 GMT 2010
On Mon, Feb 22, 2010 at 01:07:59PM +0100, Martin Sustrik wrote:
> 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.
True, although the worst case down to O(n) [we should probably take the resulting
vim vs. emacs style trees-vs-hash-tables debate that normally follows at this
point as read]
> >'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.
Thanks, that's good to know.
Paul Jones just pointed me to an interesting use case here.
The keys being used correspond to URLS + methods and seem to look something like
(I'm not sure if that's exactly right, but that's the idea)
so your routing would normally look something like
The keys are probably no longer than what you describe, but the initial * does
mean that they need to be able gracefully transition between simple prefixes
and the more general NFA.
More information about the rabbitmq-discuss