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-24 05:30:56 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!cyclone.bc.net!newsfeed.telusplanet.net!peer1-sjc1.usenetserver.com!usenetserver.com!hub1.nntpserver.com!telocity-west!TELOCITY!news-out.spamkiller.net!propagator2-maxim!propagator-maxim!news-in.spamkiller.net!out.nntp.be!propagator-SanJose!in.nntp.be!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> <7vznzukhzf.fsf@vlinux.voxelvision.no> <3CC5B161.C719C5D8@san.rr.com> From: Ole-Hjalmar Kristensen Message-ID: <7vg01lwaku.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: Wed, 24 Apr 2002 12:22:10 GMT NNTP-Posting-Host: 193.216.12.150 X-Complaints-To: abuse@tele2.no X-Trace: juliett.dax.net 1019650930 193.216.12.150 (Wed, 24 Apr 2002 14:22:10 MET DST) NNTP-Posting-Date: Wed, 24 Apr 2002 14:22:10 MET DST Organization: Tele2 Norway AS Public Access Xref: archiver1.google.com comp.lang.ada:23047 Date: 2002-04-24T12:22:10+00:00 List-Id: Darren New writes: > Ole-Hjalmar Kristensen wrote: > > 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. > > I haven't done any safety-critical work, but is this how it's really > done? "It's very unlikely this airplane will crash into that nuclear > plant, unless 20 items all hash to the same value"? :-) No, > seriously... I agree, not the thing you would want in a hard real time safety-critical system. Buf for soft real time, non saftey critical systems it's good enough. And it really can make a difference in throughput in for instance applications like relational algebra processing. > > In any case, the hashes still have two problems: > > 1) You *could* be hosed this way, so while they may be faster, they're > still not deterministic, while a red-black tree has a strictly bounded > upper limit on the number of operations (given a particular number of > nodes) which is much lower than that of a hash table. In other words, > the worst-case for a hashtable is still O(N), which if you need realtime > and safety-critical, you have to take it into account. > Agree, although even O(N) might be good enough, depending on you application. Also, if the probability of O(N) behaviour is sufficiently low, it may be way below the probability of a system failure caused by other errors. > 2) You need to be able to hash the value. A red-black tree needs only an > ordering operator (like "<"), not something that gropes the insides of > an object like a hash needs to. If you want to ensure you have a > particularly good hash, then you are going to have trouble with the > strong typing in Ada, yes? That is, every type of hash table I create is > going to work only if I implement a hash appropriate to the key type, > and that'll have to get reimplemented (to some extent at least) for > every type. On the other hand, most of the built-in types and metatypes > ("record", "array", etc) already have ordering operators or rules on how > to deduce them from the components. > Yes, although the reimplementation usually just consists of calling the same hash functions with different parameters. After all, we don't really care what we are hashing, all we need to know is the location and size of the key, so one good hash function is really all you need. > -- > 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%.