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-Thread: 103376,8e7ac81a215f128c X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII Path: g2news2.google.com!postnews.google.com!j9g2000vbr.googlegroups.com!not-for-mail From: Adam Beneschan Newsgroups: comp.lang.ada Subject: Re: Using Red-Black Trees Date: Tue, 16 Nov 2010 21:10:22 -0800 (PST) Organization: http://groups.google.com Message-ID: References: <2419e829-6f45-4075-9005-b9876beb8aaa@r6g2000vbf.googlegroups.com> <46306fd9-21dc-40df-88e7-fc7e568399a4@k11g2000vbf.googlegroups.com> NNTP-Posting-Host: 207.200.116.71 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1289970622 6271 127.0.0.1 (17 Nov 2010 05:10:22 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Wed, 17 Nov 2010 05:10:22 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: j9g2000vbr.googlegroups.com; posting-host=207.200.116.71; posting-account=duW0ogkAAABjRdnxgLGXDfna0Gc6XqmQ User-Agent: G2/1.0 X-HTTP-Via: HTTP/1.1 (Velocity/3.1.2.1 [uScMs f p eN:t cCMp s ]), HTTP/1.1 spider-ntc-ta05.proxy.aol.com[CFC87005] (Prism/1.2.1), HTTP/1.1 cache-ntc-ab07.proxy.aol.com[CFC87447] (Traffic-Server/6.1.5 [uScM]) X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; AOL 9.5; AOLBuild 4337.5401; Windows NT 6.1; WOW64; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; HPDTDF; BRI/1; .NET4.0C),gzip(gfe) Xref: g2news2.google.com comp.lang.ada:16502 Date: 2010-11-16T21:10:22-08:00 List-Id: On Nov 16, 6:50=A0pm, "Alex Mentis" wrote: > Randy Brukardt wrote: > > Unless you are a student, worrying about a specific data structure is > > silly in 99% of the cases. > > Some students do use Ada. > > > I don't know what data > > structures this newsreader and browser use, but they're good enough > > for the application, so why should I care?? Same goes for the > > standard containers. > > Ah, ignorance is bliss! =A0"It just works." =A0We should call it iAda and > sell it to Steve Jobs. :-) > > Implementation matters to some people, and it's not my job to decide > when it should and shouldn't matter to them. =A0Of course, maybe that > *is* your job...I don't want to be presumptuous. :-) > > Sometimes, when you're not building an airplane, you just want to use a > data structure you know works and not have to do a lot of performance > benchmarking. =A0In this case, the ARM only guarantees O((log n)**2) > performance for particular operations, but a red-black tree should > perform significantly better, so awareness of the implementation might > be nice. > > I don't really disagree with your philosphy of "trust the container" > all that much, though, and I'm not trying to start an argument. =A0So, > hopefully the smiley emoticons did their job in conveying that. I think that in a case like this, the truth is somewhere in between. Like Randy said, in most cases you should not need to care about the exact implementation. However, often one does care that an implementation works well for certain patterns of operations. For example, you might have a container-type package that supports "insert" and "search" operations; but a user that wants to insert all the data first, calling the Insert operation on data that's already sorted, and then do searches, would probably prefer a different implementation than a user that is going to be using the Insert operation interspersed with searches throughout the program. In my view, the OP shouldn't have said "I need a self-balancing binary search tree" or "I need a red-black tree", but simply saying "I need something that represents an ordered set of data" isn't always good enough, either. Sometimes it is. But ideally it should be something like "I need something that represents an ordered map, that is optimized for arbitrary sequences of insertions, deletions, and lookups" or whatever the needs are. (And to *really* dream, an implementation could provide an operation in a child package to allow the caller to select from a set of optimization options and then provide alternate implementations. No, I'm not volunteering to do the work :) ) -- Adam