[m-users.] Efficient circular lists in pure Mercury?
mark at mercurylang.org
Thu Jun 27 13:37:52 AEST 2019
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
I mean one of these:
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
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
More information about the users