Devon H. O'Dell
dodell at offmyserver.com
Mon Apr 18 00:39:34 PDT 2005
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,
> 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.
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:
/ / \
\ / (12)
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:
/ / \
(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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 187 bytes
Desc: "Description: PGP signature"
More information about the Kernel