From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,ac39a12d5faf5b14 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-04-23 00:11:17 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!news.net.uni-c.dk!uninett.no!dax.net!juliett.dax.net!not-for-mail Newsgroups: comp.lang.ada Subject: Re: Grace and Maps (was Re: Development process in the Ada community) References: <3CB46975.90408@snafu.de> <3CBAFFEE.2080708@snafu.de> <4519e058.0204171036.6f0a7394@posting.google.com> <3CBDD795.4060706@snafu.de> <4519e058.0204180800.44fac012@posting.google.com> <3CBF0341.8020406@mail.com> <4519e058.0204190529.559a47ae@posting.google.com> <3CC1C6B3.6060306@telepath.com> <3CC21747.5000501@telepath.com> <4519e058.0204220534.2eb33730@posting.go <3CC48F34.5A474E0F@boeing.com> <3CC49C50.485AE213@san.rr.com> <3CC4B5C0.4D16077C@acm.org> <3CC4E9DA.E02BE0DA@san.rr.com> From: Ole-Hjalmar Kristensen Message-ID: <7vznzukhzf.fsf@vlinux.voxelvision.no> User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Tue, 23 Apr 2002 07:10:45 GMT NNTP-Posting-Host: 193.216.12.150 X-Complaints-To: abuse@tele2.no X-Trace: juliett.dax.net 1019545845 193.216.12.150 (Tue, 23 Apr 2002 09:10:45 MET DST) NNTP-Posting-Date: Tue, 23 Apr 2002 09:10:45 MET DST Organization: Tele2 Norway AS Public Access Xref: archiver1.google.com comp.lang.ada:22973 Date: 2002-04-23T07:10:45+00:00 List-Id: Darren New writes: > Jeffrey Carter wrote: > > Maybe my memory is faulty, but I seem to recall that these trees still > > need rebalancing to maintain O(log N) search times. > > Yes, but only on inserts, only rebalancing of a limited amount of the > tree (O(log N) for the worst case rebalance) and generally do *not* > require rebalances on every insert. It's not like keeping a list sorted, > for example. For example, a red-black tree touches at worse the nodes > between the node you just inserted and the root, IIRC. A B-tree (which > is based on blocks of pointers) touches the block you inserted in and > potentially back to the root, either splitting or combining as needed. > > Red/black trees don't get nodes moved when they're rebalanced. You just > adjust the pointers. > Yes, they are very nice. > I'm not sure why a hashtable wouldn't have a worst-case time of O(N) (if > all the elements hash to the same value) or how you'd guarantee any > particular limit on execution time of inserting a value (for example, in > the same case). In contrast, a red-black tree is *never* going to see > O(N) time in any operation. > You're right, you cannot in general guarantee it. But if you use hash functions which on average change half the bits as a result of a single bit change in the input, you can rest assured that it will not happen in practice. A more serious problem is that the average time increases as you add more data items. For your typical hash link table, you should try to keep the table not more than 50-80% full. This will give you search times very close to O(1) with a good hash function. For general use, I would certainly prefer a good tree implementation, but when you need the utmost speed and have a fixed size data set, I would go for the hash table. > -- > Darren New > San Diego, CA, USA > (PST). Cryptokeys on demand. > The 90/10 rule of toothpaste: the last > 10% of > the tube lasts as long as the first 90%.