From: "Stuart" <stuart@0.0>
Subject: Re: Invade wikipedia!
Date: Wed, 4 Mar 2009 13:31:41 -0000
Date: 2009-03-04T13:31:41+00:00 [thread overview]
Message-ID: <49ae7e48_1@glkas0286.greenlnk.net> (raw)
In-Reply-To: vo7g5a9tdgei$.553b23ltkai3$.dlg@40tude.net
[Correcting my earlier (canceled) message - Stuart]
Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> 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;
<snip>
> 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
next prev parent reply other threads:[~2009-03-04 13:31 UTC|newest]
Thread overview: 91+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-02-24 11:03 Invade wikipedia! Jean-Pierre Rosen
2009-02-24 13:40 ` Dmitry A. Kazakov
2009-02-24 14:49 ` (see below)
2009-02-24 15:11 ` Dmitry A. Kazakov
2009-02-24 15:22 ` (see below)
2009-02-24 15:49 ` Dmitry A. Kazakov
2009-02-24 16:32 ` (see below)
2009-02-24 17:31 ` Dmitry A. Kazakov
2009-02-24 14:50 ` Martin
2009-02-24 15:16 ` Dmitry A. Kazakov
2009-02-24 19:48 ` Hibou57 (Yannick Duchêne)
2009-02-24 20:34 ` sjw
2009-02-24 21:27 ` Jeffrey R. Carter
2009-02-24 21:48 ` Hibou57 (Yannick Duchêne)
2009-02-24 22:43 ` Jeffrey R. Carter
2009-02-24 23:03 ` Adam Beneschan
2009-02-24 23:28 ` Martin
2009-02-24 23:33 ` (see below)
2009-02-25 0:08 ` Martin
2009-02-25 0:52 ` Adam Beneschan
2009-02-25 1:45 ` (see below)
2009-02-25 16:38 ` Martin
2009-02-25 21:03 ` Adam Beneschan
2009-02-25 8:05 ` Jacob Sparre Andersen
2009-02-25 8:59 ` Hibou57 (Yannick Duchêne)
2009-02-25 16:10 ` (see below)
2009-02-25 18:13 ` Georg Bauhaus
2009-02-25 18:53 ` (see below)
2009-02-25 19:19 ` Georg Bauhaus
2009-02-27 23:53 ` Randy Brukardt
2009-02-28 6:31 ` Hibou57 (Yannick Duchêne)
2009-02-28 8:49 ` Ivan Levashew
2009-02-25 19:17 ` Dmitry A. Kazakov
2009-02-25 22:48 ` Robert A Duff
2009-02-26 3:21 ` Hibou57 (Yannick Duchêne)
2009-02-26 10:07 ` Georg Bauhaus
2009-02-26 3:20 ` Hibou57 (Yannick Duchêne)
2009-02-25 15:57 ` (see below)
2009-02-25 22:14 ` Adam Beneschan
2009-02-24 23:53 ` Hibou57 (Yannick Duchêne)
2009-02-25 0:07 ` Martin
2009-02-24 23:02 ` Adam Beneschan
2009-02-24 14:52 ` Peter Hermann
2009-02-24 15:44 ` Georg Bauhaus
2009-02-24 15:53 ` Peter Hermann
2009-02-24 16:18 ` Georg Bauhaus
2009-02-24 16:32 ` Jean-Pierre Rosen
2009-02-24 16:52 ` Adam Beneschan
2009-02-24 18:30 ` Georg Bauhaus
2009-02-24 18:46 ` Adam Beneschan
2009-02-24 19:42 ` Hibou57 (Yannick Duchêne)
2009-02-24 19:59 ` Dmitry A. Kazakov
2009-02-24 20:08 ` Hibou57 (Yannick Duchêne)
2009-02-24 23:01 ` Georg Bauhaus
2009-02-24 23:47 ` Hibou57 (Yannick Duchêne)
2009-02-26 0:52 ` Georg Bauhaus
2009-02-26 3:33 ` Hibou57 (Yannick Duchêne)
2009-02-26 6:38 ` Hibou57 (Yannick Duchêne)
2009-02-25 22:15 ` Ivan Levashew
2009-02-24 19:29 ` Martin Krischik
2009-02-25 22:31 ` Ivan Levashew
2009-02-25 23:07 ` Jeffrey R. Carter
2009-02-26 0:44 ` Georg Bauhaus
2009-02-26 8:29 ` Dmitry A. Kazakov
2009-02-26 10:40 ` Jean-Pierre Rosen
2009-02-26 13:53 ` Ivan Levashew
2009-02-26 14:13 ` Jean-Pierre Rosen
2009-02-26 15:42 ` Peter Hermann
2009-02-26 16:37 ` Adam Beneschan
2009-02-26 17:57 ` Jean-Pierre Rosen
2009-02-26 14:20 ` Dmitry A. Kazakov
2009-02-26 17:44 ` Georg Bauhaus
2009-02-26 18:16 ` Adam Beneschan
2009-02-27 11:30 ` Georg Bauhaus
2009-02-27 17:33 ` Dmitry A. Kazakov
2009-02-27 23:31 ` Georg Bauhaus
2009-02-28 0:31 ` Jeffrey R. Carter
2009-02-28 5:26 ` Ivan Levashew
2009-02-28 6:27 ` Hibou57 (Yannick Duchêne)
2009-02-28 6:40 ` Jeffrey R. Carter
2009-02-28 7:01 ` Hibou57 (Yannick Duchêne)
2009-02-28 11:45 ` Georg Bauhaus
2009-03-03 14:16 ` Anders Wirzenius
2009-03-03 15:34 ` Dmitry A. Kazakov
2009-03-04 5:52 ` Anders Wirzenius
2009-03-04 9:19 ` Dmitry A. Kazakov
2009-03-04 13:31 ` Stuart [this message]
2009-03-04 13:20 ` Stuart
2009-03-04 13:46 ` Dmitry A. Kazakov
2009-03-04 18:41 ` Stuart
2009-03-04 20:46 ` Dmitry A. Kazakov
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox