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 10:26:07 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed1.cidera.com!Cidera!cyclone.columbus.rr.com!cyclone3.kc.rr.com!news3.kc.rr.com!twister.socal.rr.com.POSTED!not-for-mail Message-ID: <3CC6EABC.5E766F0D@san.rr.com> From: Darren New X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 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> <3CC59ED2.1000803@home.com> <3CC5B286.6FE61551@san.rr.com> <3CC5B9EE.32F3060@san.rr.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Wed, 24 Apr 2002 17:25:41 GMT NNTP-Posting-Host: 66.75.151.160 X-Complaints-To: abuse@rr.com X-Trace: twister.socal.rr.com 1019669141 66.75.151.160 (Wed, 24 Apr 2002 10:25:41 PDT) NNTP-Posting-Date: Wed, 24 Apr 2002 10:25:41 PDT Organization: RoadRunner - West Xref: archiver1.google.com comp.lang.ada:23066 Date: 2002-04-24T17:25:41+00:00 List-Id: Stephen Leake wrote: > > Darren New writes: > > > Stephen Leake wrote: > > > > point in sorting the values. Of course, if you ever need it sorted, > > > > chances are you want to keep it sorted. But AFAIK, none of the scripting > > > > languages (Tcl, Perl, Python) have sorts for their > > > > internally-implemented maps. > > > > > > And they all live with O (n) time? amazing ! :). > > > > No. Hash tables aren't O(n) except in the worst case. In the best case, > > they're O(1). > > But if I just declare a map in Python, there's no way it's guaranteed > to be best case. So I think you are saying "yes, they live with the > O(n) worst case, and hope for the O(1) best case, and take whatever > they actually get". Well, if you want to look at it like this, yes. But it's O(N) with a really tiny constant multiplier. I'd also expect that the hash tables get grown as the chains get long. > > When you'd doing things like looking up variables, it's pretty easy > > to pay the sort time if you want to iterate over all variable names > > in sorted order, compared to getting close to O(1) when referencing > > a variable instead of O(logN) each time. Think "symbol table". > > Well, the question is, is a "typical" map in Perl or Python "close to" > O(n), or "close to" O(1)? Anybody have any data? Well, honestly, a hash table of any fixed size is technically O(N), but divided by the number of buckets in the hash table. If the number of buckets is sufficiently larger than the number of entries, you have O(1) for practical purposes. Nobody really stores unlimited numbers of items in a hash. As far as the rehashing goes, you have to touch each item whenever you rearrange the buckets, to put each in the right bucket, so that's probably at least O(N) also. So yes, my guess is that hashes are O(N) with a really, really small multiplier, small enough to make O(lg N) operations not worthwhile. > If I use a red-black tree, I _know_ it is O(log n). O(N)/1000 < O(log N) for sufficiently small N. I think that's the trick. -- 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%.