* memoization in Ada? Hash ADT?
@ 2023-07-22 3:50 Kenneth Wolcott
2023-07-22 5:30 ` Kenneth Wolcott
0 siblings, 1 reply; 7+ messages in thread
From: Kenneth Wolcott @ 2023-07-22 3:50 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: memoization in Ada? Hash ADT?
2023-07-22 3:50 memoization in Ada? Hash ADT? Kenneth Wolcott
@ 2023-07-22 5:30 ` Kenneth Wolcott
2023-07-24 21:18 ` Gautier write-only address
0 siblings, 1 reply; 7+ messages in thread
From: Kenneth Wolcott @ 2023-07-22 5:30 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: memoization in Ada? Hash ADT?
2023-07-22 5:30 ` Kenneth Wolcott
@ 2023-07-24 21:18 ` Gautier write-only address
2023-07-26 4:38 ` Kenneth Wolcott
0 siblings, 1 reply; 7+ messages in thread
From: Gautier write-only address @ 2023-07-24 21:18 UTC (permalink / raw)
> 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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: memoization in Ada? Hash ADT?
2023-07-24 21:18 ` Gautier write-only address
@ 2023-07-26 4:38 ` Kenneth Wolcott
2023-07-26 7:50 ` Simon Wright
2023-07-26 21:36 ` Gautier write-only address
0 siblings, 2 replies; 7+ messages in thread
From: Kenneth Wolcott @ 2023-07-26 4:38 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: memoization in Ada? Hash ADT?
2023-07-26 4:38 ` Kenneth Wolcott
@ 2023-07-26 7:50 ` Simon Wright
2023-07-26 21:36 ` Gautier write-only address
1 sibling, 0 replies; 7+ messages in thread
From: Simon Wright @ 2023-07-26 7:50 UTC (permalink / raw)
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!)
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: memoization in Ada? Hash ADT?
2023-07-26 4:38 ` Kenneth Wolcott
2023-07-26 7:50 ` Simon Wright
@ 2023-07-26 21:36 ` Gautier write-only address
2023-07-26 22:18 ` Kenneth Wolcott
1 sibling, 1 reply; 7+ messages in thread
From: Gautier write-only address @ 2023-07-26 21:36 UTC (permalink / raw)
> Regarding HAC, isn't that Windows-only?
Not at all :-)
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: memoization in Ada? Hash ADT?
2023-07-26 21:36 ` Gautier write-only address
@ 2023-07-26 22:18 ` Kenneth Wolcott
0 siblings, 0 replies; 7+ messages in thread
From: Kenneth Wolcott @ 2023-07-26 22:18 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2023-07-26 22:18 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-22 3:50 memoization in Ada? Hash ADT? Kenneth Wolcott
2023-07-22 5:30 ` Kenneth Wolcott
2023-07-24 21:18 ` Gautier write-only address
2023-07-26 4:38 ` Kenneth Wolcott
2023-07-26 7:50 ` Simon Wright
2023-07-26 21:36 ` Gautier write-only address
2023-07-26 22:18 ` Kenneth Wolcott
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox