❌ About FreshRSS

Normal view

There are new articles available, click to refresh the page.
Before yesterdayAda Forum - Latest topics

Ada.Containers.Hash_Type'Size

βœ‡Ada Forum - Latest topics
By: JeremyGrosser
9 December 2022 at 23:51

I’ve been playing with optimizations for an instance of Ada.Containers.Hashed_Sets for the Advent of Code Day 9 puzzle.

RM A.18.1 The Package Containers says:

type Hash_Type is mod implementation-defined;

With the Implementation advice:

Hash_Type'Modulus should be at least 2**32.

The annotated RM expands upon this:

This is not a requirement so that these types can be declared properly on machines with native sizes that are not 32 bits. For instance, a 24-bit target could use 2**24 for Hash_Type'Modulus.

In GNAT’s a-contai.ads, the definition is simply:

type Hash_Type is mod 2**32;

Would it make sense to use System.Max_Binary_Modulus instead, so that 64-bit systems can benefit from a larger hash space?

type Hash_Type is mod System.Max_Binary_Modulus;

If we want to retain the minimum 32-bit size, a conditional could be added:

type Hash_Type is mod (if System.Max_Binary_Modulus >= 32 then System.Max_Binary_Modulus else 32);

1 post - 1 participant

Read full topic

2022 Day 9: Rope Bridge

βœ‡Ada Forum - Latest topics
By: JeremyGrosser
9 December 2022 at 06:32

I think the problem statement was intentionally difficult to parse this time. Those conditionals are a lot simpler than it makes them sound.

I kept the visited positions in a Hashed_Set and coming up with a good Hash function for a pair of Integers was new for me. I ended up making a lot of assumptions (Integer'Size = 32 and Hash_Type'Size = 64) and just shifted one of the integers left 32 bits. A cursory Google search turned up the Cantor Pairing function, but I wasn’t able to make this work with negative integers in a short amount of time. Clearly I need to do more reading.

Part 2 caught me off guard, I hadn’t anticipated I’d need to deal with more elements.

Note: I’m going to stop using the spoiler blur on the daily posts. If you’ve gotten this far, I assume you know that these posts contain spoilers.

13 posts - 8 participants

Read full topic

❌
❌