From: Lutz Donnerhacke <lutz@iks-jena.de>
Subject: Re: Implementing Memorize
Date: Wed, 22 Oct 2003 11:56:16 +0000 (UTC)
Date: 2003-10-22T11:56:16+00:00 [thread overview]
Message-ID: <slrnbpcs2v.oa.lutz@taranis.iks-jena.de> (raw)
In-Reply-To: slrnbpcqnf.oa.lutz@taranis.iks-jena.de
* Lutz Donnerhacke wrote:
> The following version does not the job:
Simple logic error:
> with Ada.Text_IO, Ada.Calendar;
>
>
> procedure t is
> package Fibs is
> type Direct is tagged null record;
>
> function Fib (c1 : Direct; c2 : Direct'Class; n : Natural) return Natural;
> end Fibs;
>
> package body Fibs is
> function Fib (c1 : Direct; c2 : Direct'Class; n : Natural) return Natural is
> begin
> case n is
> when 0 | 1 => return 1;
> when others => return Fib (c2, c2, n-1) + Fib (c2, c2, n-2);
> end case;
> end Fib;
> end Fibs;
>
> use Fibs;
>
> package Memorizes is
> type Memorize is new Fibs.Direct with null record;
> function Fib (c1 : Memorize; c2 : Fibs.Direct'Class; n : Natural) return Natural;
> end Memorizes;
>
> package body Memorizes is
> type Item is record
> value : Natural;
> valid : Boolean := False;
> end record;
>
> hash : array(0 .. 100) of Item;
>
> function Fib (c1 : Memorize; c2 : Fibs.Direct'Class; n : Natural) return Natural is
> begin
> if n not in hash'Range then
> return Fib(Direct(c1), c2, n);
> else
> declare
> x : Natural renames hash(n).value;
> begin
> if not hash(n).valid then
> x := Fib(Direct(c1), c2, n);
hash(n).valid := True;
> end if;
> return x;
> end;
> end if;
> end Fib;
> end Memorizes;
>
> use Memorizes;
>
> procedure Time_It (ctx : Direct'Class; n : Natural) is
> use Ada.Text_IO, Ada.Calendar;
> start, ende : Time;
> result : Natural;
> begin
> start := Clock;
> result := Fib (ctx, ctx, n);
> ende := Clock;
> Put_Line ("Result =" & Natural'Image(result) &
> " in" & Duration'Image(ende-start) & " seconds.");
> end Time_It;
>
> d : Direct;
> m : Memorize;
> begin
> Time_It (d, 30);
> Time_It (m, 30);
> end t;
Does the job.
next prev parent reply other threads:[~2003-10-22 11:56 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-10-22 9:28 Implementing Memorize christoph.grein
2003-10-22 10:32 ` Lutz Donnerhacke
2003-10-22 10:48 ` Marius Amado Alves
2003-10-22 11:07 ` Lutz Donnerhacke
2003-10-22 11:33 ` Lutz Donnerhacke
2003-10-22 11:56 ` Lutz Donnerhacke [this message]
2003-10-22 12:29 ` Marius Amado Alves
2003-10-22 12:52 ` Lutz Donnerhacke
2003-10-22 13:42 ` Marius Amado Alves
2003-10-22 12:08 ` Dmitry A. Kazakov
2003-10-22 12:10 ` Lutz Donnerhacke
2003-10-22 15:23 ` Dmitry A. Kazakov
2003-10-22 19:41 ` Lutz Donnerhacke
2003-10-23 14:36 ` Dmitry A. Kazakov
2003-10-22 19:29 ` Robert I. Eachus
2003-10-22 19:44 ` Lutz Donnerhacke
-- strict thread matches above, loose matches on Subject: below --
2003-10-22 8:52 Lutz Donnerhacke
2003-10-22 15:00 ` Frank J. Lhota
2003-10-22 17:03 ` tmoran
2003-10-23 0:25 ` Georg Bauhaus
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox