1. Forum
  2. Usenet
  3. COMP.LANG.ADA

  • memoization in Ada? Hash ADT?

    From Kenneth Wolcott@21:1/5 to All on Fri Jul 21 20:50:04 2023
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kenneth Wolcott@21:1/5 to Kenneth Wolcott on Fri Jul 21 22:30:44 2023
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Gautier write-only address@21:1/5 to All on Mon Jul 24 14:18:25 2023
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kenneth Wolcott@21:1/5 to Gautier on Tue Jul 25 21:38:02 2023
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Simon Wright@21:1/5 to Kenneth Wolcott on Wed Jul 26 08:50:01 2023
    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!)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Gautier write-only address@21:1/5 to All on Wed Jul 26 14:36:15 2023
    Regarding HAC, isn't that Windows-only?

    Not at all :-)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kenneth Wolcott@21:1/5 to Gautier on Wed Jul 26 15:18:51 2023
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)