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 09:54:55 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail From: Stephen Leake Newsgroups: comp.lang.ada Subject: Re: Grace and Maps (was Re: Development process in the Ada community) Date: 24 Apr 2002 12:49:50 -0400 Organization: NASA Goddard Space Flight Center (skates.gsfc.nasa.gov) Message-ID: 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> NNTP-Posting-Host: anarres.gsfc.nasa.gov Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: skates.gsfc.nasa.gov 1019667358 12509 128.183.220.71 (24 Apr 2002 16:55:58 GMT) X-Complaints-To: usenet@news.gsfc.nasa.gov NNTP-Posting-Date: 24 Apr 2002 16:55:58 GMT User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: archiver1.google.com comp.lang.ada:23064 Date: 2002-04-24T16:55:58+00:00 List-Id: 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". Hmm. Maybe there is a way to tell Python what the hash table size should be, and what hash function to use? Then I can get O(1). I confess to never having used either a Perl or Python map. > 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? If I use a red-black tree, I _know_ it is O(log n). -- -- Stephe