Rocksolid Light

Welcome to RetroBBS

mail  files  register  newsreader  groups  login

Message-ID:  

Never trust a computer you can't repair yourself.

devel / comp.lang.ada / Re: memoization in Ada? Hash ADT?

SubjectAuthor
* memoization in Ada? Hash ADT?Kenneth Wolcott
`* Re: memoization in Ada? Hash ADT?Kenneth Wolcott
 `* Re: memoization in Ada? Hash ADT?Gautier write-only address
  `* Re: memoization in Ada? Hash ADT?Kenneth Wolcott
   +- Re: memoization in Ada? Hash ADT?Simon Wright
   `* Re: memoization in Ada? Hash ADT?Gautier write-only address
    `- Re: memoization in Ada? Hash ADT?Kenneth Wolcott

1
memoization in Ada? Hash ADT?

<1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9846&group=comp.lang.ada#9846

  copy link   Newsgroups: comp.lang.ada
X-Received: by 2002:a05:6214:17c8:b0:635:dff8:e60d with SMTP id cu8-20020a05621417c800b00635dff8e60dmr6919qvb.0.1689997805352;
Fri, 21 Jul 2023 20:50:05 -0700 (PDT)
X-Received: by 2002:a05:6830:10d8:b0:6b8:8894:e4ac with SMTP id
z24-20020a05683010d800b006b88894e4acmr2352384oto.3.1689997805151; Fri, 21 Jul
2023 20:50:05 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!feeder.erje.net!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Fri, 21 Jul 2023 20:50:04 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=98.59.238.112; posting-account=oHOvdQoAAACYgyEBjgPNvKFOGxg8pNns
NNTP-Posting-Host: 98.59.238.112
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
Subject: memoization in Ada? Hash ADT?
From: kennethwolcott@gmail.com (Kenneth Wolcott)
Injection-Date: Sat, 22 Jul 2023 03:50:05 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1591
 by: Kenneth Wolcott - Sat, 22 Jul 2023 03:50 UTC

Hi;

I'm working on the Rosetta Code task:

"Stirling numbers of the second kind"

I have a working recursive solution written in Ada but I'd like to memoize it to cut down on the redundant and duplicative calls (similar to a recursive solution to calculating the Fibonacci sequence).

So I think I need a hash ADT (which I've used in Perl) but I've never used in Ada.

So I want to preserve the calculation of the Stirling2 for each N and K so I can do a lookup. If this were based on a single unsigned integer, an array would suffice. Maybe a 2d array would suffice?

Thanks,
Ken Wolcott

Re: memoization in Ada? Hash ADT?

<b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9847&group=comp.lang.ada#9847

  copy link   Newsgroups: comp.lang.ada
X-Received: by 2002:a37:2c45:0:b0:767:f1e8:d2d2 with SMTP id s66-20020a372c45000000b00767f1e8d2d2mr6264qkh.5.1690003845201;
Fri, 21 Jul 2023 22:30:45 -0700 (PDT)
X-Received: by 2002:a05:6808:2381:b0:3a3:c78e:d863 with SMTP id
bp1-20020a056808238100b003a3c78ed863mr8907598oib.0.1690003844898; Fri, 21 Jul
2023 22:30:44 -0700 (PDT)
Path: i2pn2.org!i2pn.org!news.1d4.us!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Fri, 21 Jul 2023 22:30:44 -0700 (PDT)
In-Reply-To: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=98.59.238.112; posting-account=oHOvdQoAAACYgyEBjgPNvKFOGxg8pNns
NNTP-Posting-Host: 98.59.238.112
References: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com>
Subject: Re: memoization in Ada? Hash ADT?
From: kennethwolcott@gmail.com (Kenneth Wolcott)
Injection-Date: Sat, 22 Jul 2023 05:30:45 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2265
 by: Kenneth Wolcott - Sat, 22 Jul 2023 05:30 UTC

On Friday, July 21, 2023 at 8:50:06 PM UTC-7, Kenneth Wolcott wrote:
> Hi;
>
> I'm working on the Rosetta Code task:
>
> "Stirling numbers of the second kind"
>
> I have a working recursive solution written in Ada but I'd like to memoize it to cut down on the redundant and duplicative calls (similar to a recursive solution to calculating the Fibonacci sequence).
>
> So I think I need a hash ADT (which I've used in Perl) but I've never used in Ada.
>
> So I want to preserve the calculation of the Stirling2 for each N and K so I can do a lookup. If this were based on a single unsigned integer, an array would suffice. Maybe a 2d array would suffice?
>
> Thanks,
> Ken Wolcott

I solved the specific problem using a 2d array for caching. This is not memoization, per se, but this works very well. The recursive calls are now very fast as there is a maximum of one calculation per recursive call.

So, any resources on how to write Ada programs that take advantage of memoization?

Thanks,
Ken

Re: memoization in Ada? Hash ADT?

<a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9848&group=comp.lang.ada#9848

  copy link   Newsgroups: comp.lang.ada
X-Received: by 2002:ad4:4e4f:0:b0:63c:fbf9:b5d0 with SMTP id eb15-20020ad44e4f000000b0063cfbf9b5d0mr2188qvb.9.1690233506722;
Mon, 24 Jul 2023 14:18:26 -0700 (PDT)
X-Received: by 2002:a05:6808:13d3:b0:3a3:e17e:d2ea with SMTP id
d19-20020a05680813d300b003a3e17ed2eamr21465699oiw.8.1690233506251; Mon, 24
Jul 2023 14:18:26 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Mon, 24 Jul 2023 14:18:25 -0700 (PDT)
In-Reply-To: <b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2a02:1210:2e90:8100:82d:f5ad:d273:1b8;
posting-account=gRqrnQkAAAAC_02ynnhqGk1VRQlve6ZG
NNTP-Posting-Host: 2a02:1210:2e90:8100:82d:f5ad:d273:1b8
References: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com> <b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>
Subject: Re: memoization in Ada? Hash ADT?
From: gautier_niouzes@hotmail.com (Gautier write-only address)
Injection-Date: Mon, 24 Jul 2023 21:18:26 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Gautier write-only a - Mon, 24 Jul 2023 21:18 UTC

> So, any resources on how to write Ada programs that take advantage of memoization?

Look here https://forum.ada-lang.io/ for discussions about Advent of Code puzzles. Some solutions use (and need, for completing in a reasonable time) memoization.
You find with HAC ( https://hacadacompiler.sourceforge.io/ ) a set of solutions (search "memoiz*" or "cache"), mostly compiling with the HAC subset.

Re: memoization in Ada? Hash ADT?

<c23d043b-13e3-4c0d-93ec-c48c00918cffn@googlegroups.com>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9849&group=comp.lang.ada#9849

  copy link   Newsgroups: comp.lang.ada
X-Received: by 2002:a05:622a:1a27:b0:404:eea2:dc37 with SMTP id f39-20020a05622a1a2700b00404eea2dc37mr3066qtb.2.1690346283389;
Tue, 25 Jul 2023 21:38:03 -0700 (PDT)
X-Received: by 2002:a05:6870:769c:b0:1bb:b8f0:5878 with SMTP id
dx28-20020a056870769c00b001bbb8f05878mr1294802oab.5.1690346282925; Tue, 25
Jul 2023 21:38:02 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Tue, 25 Jul 2023 21:38:02 -0700 (PDT)
In-Reply-To: <a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=98.59.238.112; posting-account=oHOvdQoAAACYgyEBjgPNvKFOGxg8pNns
NNTP-Posting-Host: 98.59.238.112
References: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
<b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com> <a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c23d043b-13e3-4c0d-93ec-c48c00918cffn@googlegroups.com>
Subject: Re: memoization in Ada? Hash ADT?
From: kennethwolcott@gmail.com (Kenneth Wolcott)
Injection-Date: Wed, 26 Jul 2023 04:38:03 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: Kenneth Wolcott - Wed, 26 Jul 2023 04:38 UTC

On Monday, July 24, 2023 at 2:18:28 PM UTC-7, Gautier write-only address wrote:
> > So, any resources on how to write Ada programs that take advantage of memoization?
> Look here https://forum.ada-lang.io/ for discussions about Advent of Code puzzles. Some solutions use (and need, for completing in a reasonable time) memoization.
> You find with HAC ( https://hacadacompiler.sourceforge.io/ ) a set of solutions (search "memoiz*" or "cache"), mostly compiling with the HAC subset.

Thanks for the pointer to the forum.

Regarding HAC, isn't that Windows-only? I'm on a Mac (M1 chip). I'll look again at HAC.

Ken

Re: memoization in Ada? Hash ADT?

<lyh6pr9knq.fsf@pushface.org>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9851&group=comp.lang.ada#9851

  copy link   Newsgroups: comp.lang.ada
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: simon@pushface.org (Simon Wright)
Newsgroups: comp.lang.ada
Subject: Re: memoization in Ada? Hash ADT?
Date: Wed, 26 Jul 2023 08:50:01 +0100
Organization: A noiseless patient Spider
Lines: 6
Message-ID: <lyh6pr9knq.fsf@pushface.org>
References: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
<b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com>
<a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>
<c23d043b-13e3-4c0d-93ec-c48c00918cffn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: dont-email.me; posting-host="66580e7d2c10e4acedc7c20ba599c99e";
logging-data="1522969"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18AHrHeRbewBQ7Brtx4YhaY/Cbhz5snaJY="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (darwin)
Cancel-Lock: sha1:w839skPBDC/MqSIrmBF8WIMppzI=
sha1:K4uakEws5Q/oOzvVJ2lsK99K2bg=
 by: Simon Wright - Wed, 26 Jul 2023 07:50 UTC

Kenneth Wolcott <kennethwolcott@gmail.com> writes:

> Regarding HAC, isn't that Windows-only? I'm on a Mac (M1 chip). I'll
> look again at HAC.

It worked well enough for me to find a failing test case (now fixed!)

Re: memoization in Ada? Hash ADT?

<b19f3e0a-2874-4a55-8d56-5bec329c5d0an@googlegroups.com>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9855&group=comp.lang.ada#9855

  copy link   Newsgroups: comp.lang.ada
X-Received: by 2002:ac8:5703:0:b0:405:4376:fed5 with SMTP id 3-20020ac85703000000b004054376fed5mr9253qtw.3.1690407376033;
Wed, 26 Jul 2023 14:36:16 -0700 (PDT)
X-Received: by 2002:a05:6870:5b25:b0:1ba:8b51:f4ec with SMTP id
ds37-20020a0568705b2500b001ba8b51f4ecmr1055156oab.6.1690407375888; Wed, 26
Jul 2023 14:36:15 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Wed, 26 Jul 2023 14:36:15 -0700 (PDT)
In-Reply-To: <c23d043b-13e3-4c0d-93ec-c48c00918cffn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2a02:1210:2e90:8100:8069:6907:a0cb:6f73;
posting-account=gRqrnQkAAAAC_02ynnhqGk1VRQlve6ZG
NNTP-Posting-Host: 2a02:1210:2e90:8100:8069:6907:a0cb:6f73
References: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
<b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com> <a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>
<c23d043b-13e3-4c0d-93ec-c48c00918cffn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <b19f3e0a-2874-4a55-8d56-5bec329c5d0an@googlegroups.com>
Subject: Re: memoization in Ada? Hash ADT?
From: gautier_niouzes@hotmail.com (Gautier write-only address)
Injection-Date: Wed, 26 Jul 2023 21:36:16 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1428
 by: Gautier write-only a - Wed, 26 Jul 2023 21:36 UTC

> Regarding HAC, isn't that Windows-only?

Not at all :-)

Re: memoization in Ada? Hash ADT?

<22387dba-52e2-4d67-8f7c-55c0b3d8c2ban@googlegroups.com>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=9856&group=comp.lang.ada#9856

  copy link   Newsgroups: comp.lang.ada
X-Received: by 2002:a05:620a:25c:b0:76c:69ac:a0f0 with SMTP id q28-20020a05620a025c00b0076c69aca0f0mr2817qkn.4.1690409932682;
Wed, 26 Jul 2023 15:18:52 -0700 (PDT)
X-Received: by 2002:a05:6808:2129:b0:3a5:a925:826b with SMTP id
r41-20020a056808212900b003a5a925826bmr1999194oiw.2.1690409932369; Wed, 26 Jul
2023 15:18:52 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Wed, 26 Jul 2023 15:18:51 -0700 (PDT)
In-Reply-To: <b19f3e0a-2874-4a55-8d56-5bec329c5d0an@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=98.59.238.112; posting-account=oHOvdQoAAACYgyEBjgPNvKFOGxg8pNns
NNTP-Posting-Host: 98.59.238.112
References: <1f6ad7f7-3bd3-4094-b037-eac7d352d68dn@googlegroups.com>
<b1a023f7-c8a4-423d-8f55-c94cc9260b75n@googlegroups.com> <a92e5e66-d185-47e8-b3f4-5470eef7dbfcn@googlegroups.com>
<c23d043b-13e3-4c0d-93ec-c48c00918cffn@googlegroups.com> <b19f3e0a-2874-4a55-8d56-5bec329c5d0an@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <22387dba-52e2-4d67-8f7c-55c0b3d8c2ban@googlegroups.com>
Subject: Re: memoization in Ada? Hash ADT?
From: kennethwolcott@gmail.com (Kenneth Wolcott)
Injection-Date: Wed, 26 Jul 2023 22:18:52 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 1655
 by: Kenneth Wolcott - Wed, 26 Jul 2023 22:18 UTC

On Wednesday, July 26, 2023 at 2:36:17 PM UTC-7, Gautier write-only address wrote:
> > Regarding HAC, isn't that Windows-only?
> Not at all :-)

Downloaded and ran demo. Will experiment further as time permits. Nice!

Thanks,
Ken

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor