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.9 required=5.0 tests=BAYES_00,FROM_NUMERIC_TLD autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,587e0e0a16d65b10 X-Google-Attributes: gid103376,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news3.google.com!feeder.news-service.com!tudelft.nl!txtfeed1.tudelft.nl!zen.net.uk!dedekind.zen.co.uk!news-peer-lilac.gradwell.net!not-for-mail From: "Stuart" Newsgroups: comp.lang.ada References: <49a6d506$0$32680$9b4e6d93@newsspool2.arcor-online.net> <4a18f335-30f6-4216-8376-0310eb560445@p11g2000yqe.googlegroups.com> <49a7ced2$0$31342$9b4e6d93@newsspool4.arcor-online.net> Subject: Re: Invade wikipedia! Date: Wed, 4 Mar 2009 13:31:41 -0000 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.3138 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3350 Message-ID: <49ae7e48_1@glkas0286.greenlnk.net> X-Original-NNTP-Posting-Host: glkas0286.greenlnk.net NNTP-Posting-Host: 20.133.0.1 X-Trace: 1236173512 news.gradwell.net 506 dnews/20.133.0.1:33592 X-Complaints-To: news-abuse@gradwell.net Xref: g2news2.google.com comp.lang.ada:4900 Date: 2009-03-04T13:31:41+00:00 List-Id: [Correcting my earlier (canceled) message - Stuart] Dmitry A. Kazakov" wrote in message news:t0tq29ariugm.aftb8vcp4aeg$.dlg@40tude.net... > On Fri, 27 Feb 2009 12:30:25 +0100, Georg Bauhaus wrote: > >> Adding the declarations of suitable number types in an example >> algorithm maybe doesn't seem to hurt that much. Taking >> http://en.wikipedia.org/wiki/Insertion_sort as an example, >> I tried >> >> type Mug is (Metal, Plastic, Thermo, Porcelain); >> type Mug_Number is range 1 .. 10; >> type Mug_List is array(Mug_Number) of Mug; > You do not need T'Base in this case because it is cleaner and more > efficient to rewrite it in a form that would always keep all indices > within > the array range: > > procedure Insertion_Sort (A: in out Mug_List) is > begin > for I in A'First + 1..A'Last loop > declare > Value : constant Mug := A (I); > J : Mug_Number := I - 1; > begin > while A (J) > Value loop > A (J + 1) := A (J); > exit when J = A'First; > J := J - 1; > end loop; > A (J) := Value; > end; > end loop; > end Insertion_Sort; > > Of course an Ada purist would also replace integer index arithmetic with > I'Succ and I'Pred. But that would likely be too much for wiki brains... > (:-)) I looked at the following: package Sort is type Element is new integer; -- or whatever type Element_Number is range 1..10; -- or whatever type List is array(Element_Number) of Element; procedure Insertion_Sort(X : in out List); end Sort; package body Sort is procedure Insertion_Sort(X: in out List) is begin for I in X'First+1..X'Last loop declare Next_Value_to_Insert : constant Element := X(I); Insertion_Point : Element_Number := I; begin for J in reverse X'first .. I-1 loop exit when (Next_Value_to_Insert > X(J)); X(J+1) := X(J); -- Shift greater values up the sorted list Insertion_Point := Insertion_Point - 1; end loop; X(Insertion_Point) := Next_Value_to_Insert; end; end loop; end Insertion_Sort; end Sort; Interestingly when the compiler I was using was set on a strong optimization mode it did a lot more loop unrolling in this case than for the other example. I don't know whether this would have translated into any performance advantage. -- Stuart