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=-0.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00 autolearn=no 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 20:00:13 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!colt.net!newspeer.clara.net!news.clara.net!psiuk-p2!psiuk-p3!uknet!psiuk-n!news.pace.co.uk!nh.pace.co.uk!not-for-mail From: "Marin David Condic" Newsgroups: comp.lang.ada Subject: Re: Grace and Maps (was Re: Development process in the Ada community) Date: Wed, 24 Apr 2002 13:10:18 -0400 Organization: Posted on a server owned by Pace Micro Technology plc 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: dhcp-200-133.miami.pace.co.uk X-Trace: nh.pace.co.uk 1019668220 18231 136.170.200.133 (24 Apr 2002 17:10:20 GMT) X-Complaints-To: newsmaster@news.cam.pace.co.uk NNTP-Posting-Date: 24 Apr 2002 17:10:20 GMT X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Xref: archiver1.google.com comp.lang.ada:23095 Date: 2002-04-24T17:10:20+00:00 List-Id: This is just a guess based on years of experience building apps - not any sort of statistical survey. Most of the time that you are likely to use maps in a garden variety program, they will be used to store a relatively small amount of data. A few dozen directory names with a few hundred files under them, might be one example. A few hundred employees indexed by SSN, might be another. *Most* of the time, I'd suspect you're dealing with some number less than 1000. Probably, with today's hardware, you'd not notice the difference if the performance were on the order of O(n!) :-) So the question is: "Is it worth arguing over the relative performance between a few alternate implementations?" My guess is that the best solution is to pick one that will handle the general cases needed for maps reasonably well and that will be easy to implement and move on. I certainly have no objection to providing alternate structures that offer different performance benefits, but the important thing is to get a general solution available that will work well enough for most of the programmer's needs. (I'd see those as being "easy to use" and "works reliably", rather than "must have optimal performance".) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com "Stephen Leake" wrote in message news:uhem1m47l.fsf@gsfc.nasa.gov... > > 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