[m-users.] Efficient circular lists in pure Mercury?

[Mark Brown]

Hi Julian,

On Thu, Jun 27, 2019 at 9:02 AM Julian Fondren <jfondren at minimaltype.com> wrote:
>
> On 2019-06-26 14:45, Mark Brown wrote:
> >
> > Since you know the size of the problem in advance there's no need to
> > go for a dynamic data structure. You could just use a circular buffer.
>
> This boils down to my original solution with a large enough initial
> array.

I mean one of these:

https://en.wikipedia.org/wiki/Circular_buffer

This is a kind of deque, and with one of these it is easy to implement
step, insert and remove operations for a "circular list".

>  You skip unneeded steps for part1, or do something that's "good
> enough" for part1, and then part2 is revealed and you might have some
> radical redesigning to do.

Right, I see why you might not want to assume a fixed size. Now that I
think of it, though, it wouldn't be difficult to make the circular
buffer growable.

For something closer to your original solution, you could try

 - an array(int) that maps each marble in the circle to the one on its
left, or garbage if it's not in the circle
 - a similar array(int) that maps to the right
 - the current marble

The traversal and updating operations are analogous to those for
pointers. I expect this would be significantly faster than your
original solution, since it avoids a lot of intermediate data
structures (and you generally want to avoid those if you are concerned
with performance).

Mark