memoization in Ada? Hash ADT?

memoization in Ada? Hash ADT?

[Kenneth Wolcott]

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?

[Kenneth Wolcott]

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?

[Gautier write-only address]

> 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?

[Kenneth Wolcott]

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?

[Simon Wright]

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?

[Gautier write-only address]

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

Not at all :-)

Re: memoization in Ada? Hash ADT?

[Kenneth Wolcott]

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