From: | "Devon H. O'Dell " <dodell@xxxxxxxxxxxxxxx> |
Date: | Mon, 18 Apr 2005 09:33:34 +0200 |
Mail-followup-to: | kernel@crater.dragonflybsd.org |
On Mon, Apr 18, 2005 at 12:14:27AM -0700, Matthew Dillon wrote: > Skip lists... Well, based on that documentation my first reaction > is "ick". It looks like a flattened, bastardized n-way tree. Searches > basically cost the same. Insertions and deletions should theoretically > be faster, but the trade-off is against additional loss of determinism. It's a quite interesting ADT that behaves in some ways like a DAG, as I discovered after discussing it with Daniel Hartmeier. PF uses skip lists for its ruleset, which behave in a quite interesting way. In the case that two rules match the same object, they are compiled in such a way that they will `skip' to the node containing that check. I found this quite interesting, because it performs very well in normal case, although it does have a O(n) performance at worst case. I've been researching various algorithms for use in packet classification, which has produced a variety of various papers, all with interesting discussions. I've not been following this thread very well, so I'm not sure what this is for. If the data is random, a skip list probably wouldn't be great. So, if the rest of this email is off-key, sorry. > Degenerate conditions have a way of sneaking up on data structures > that try to be sneaky. I'd rather have the determinism of a red-black > tree, frankly. > > Patricia trees are basically just radix trees... unsuitable for > arranging large fixed-length numerical values. > > -Matt I suppose a DAG deserves discussion as well, since it allows for a good bit of compression since multiple nodes may point to each other. For instance: (23) / \ (15)--(19) / / \ \ / (12) (11)----/ / \ / \ / \ / (10) This graph has no real life purpose, but perhaps shows how such a diagram could be compressed. The same thing as a binary tree might look like: (23) / \ / (19) / / \ (15) (11) (12) / \ / \ (11) (19) (11) (10) I'm sure there's a better way to order or balance this tree. Anyway, hope this isn't too off topic. --Devon
Attachment:
pgp00013.pgp
Description: PGP signature