Messages in this thread | | | Date | Fri, 22 Jan 1999 16:05:53 -0500 (EST) | From | Benjamin Saller Bender <> | Subject | Re: arca-vm-26 |
| |
On Fri, 22 Jan 1999, David S. Miller wrote:
> Date: Fri, 22 Jan 1999 10:12:07 -0500 (EST) > From: Benjamin Saller Bender <case@appliedtheory.com> > > I too like skip-list, the avg cost per ptr is low and > things like merges are very easy, but when raw perf. is an issue a > good RBtree impl usually kills a skip-list. I have and use both, > but skip-list is almost never a better solution than an RBtree. > > I guess I'm usually biased towards hashes because most of the problems > I care about (read as: socket demultiplex in the networking) requires > excellent insert/delete latencies. > > What sort of properties do RB trees have for insert and delete? Can > they be done in O(1) time like a hash insert/delete can?
Hashes have O(1) for insert/hit/miss, but something like in the avg case and worst case insert of N, worst case select of N lg N. RBtrees, may or may not be useful for socket demultiplexing in the network, but they have lgN worst case for all ops. An insert that violates the Red/Black props of the tree can be fixed in like 6-12 pointer ops, which is cheap for most apps.
For the kind of things you work on where hashes work well, I find that TSTrees often work better, on avg less ops to find the key. Worth looking at anyway.
Benjamin Saller Bender <case@appliedtheory.com> AppliedTheory Communications Software Engineering Group
Any sufficiently advanced technology is indistinguishable from a rigged demo
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |