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

jfondren at minimaltype.com jfondren at minimaltype.com
Wed Jun 26 17:39:43 AEST 2019


On 2019-06-25 11:58, jfondren at minimaltype.com wrote:
> Thanks. The very moment you mentioned a pair of lists, I remembered
> that this is a well-known technique :-/
> 
> I tried this zipper library, but for the life of me, in the 30 minutes
> I have to look at it now, I couldn't define game_in, game_out, etc.
> modes that work with the zipper insts and my code. It's likely this is
> due to bugs in my code, since I'd already watered game_di down to the
> equivalent of game_in.

zipper.m's competitive (new times from average of 10 runs):

| Part1 | Language | Variant          | Runtime  | MaxRSS   |
|-------|----------|------------------|----------|----------|
|    1x | Ada      |                  | 4.38 ms  | 3.5 MB   |
| 8.34x | Mercury  | circle.m         | 36.51 ms | 52.1 MB  |
| 5.02x | Mercury  | circular\_list.m | 21.98 ms | 43.8 MB  |
| 7.62x | Mercury  | zipper.m         | 33.38 ms | 51.5 MB  |
|-------|----------|------------------|----------|----------|
| Part2 | Language | Variant          | Runtime  | MaxRSS   |
|-------|----------|------------------|----------|----------|
|    1x | Ada      |                  | 306.5 ms | 200.7 MB |
| 8.92x | Mercury  | circle.m         | 2734 ms  | 546.3 MB |
| 1.35x | Mercury  | circular\_list.m | 416.4 ms | 265.6 MB |
| 5.28x | Mercury  | zipper.m         | 1619 ms  | 297.2 MB |

part 2 ends with a zipper of more than 6.5 million ints.

I also realize I asked questions about code without linking the code.
It's here: 
https://github.com/jrfondren/adventofcode/tree/master/2018/9/mercury

Cheers,
Julian


More information about the users mailing list