Hacker News new | past | comments | ask | show | jobs | submit login
Fastest and Almost Forgotten: Martin Rem's Union-Find in Go (bugfix-66.com)
4 points by bugfix-66 on Oct 4, 2022 | hide | past | favorite | 2 comments

This algorithm (by far the fastest union-find algorithm, in practice) was almost forgotten.

Eventually found in 2010 by Mostofa Ali Patwary et al., Rem's algorithm was buried in Chapter 23 of Dijkstra's book "A Discipline of Programming":


We present a simplified and more efficient variation on the algorithm. To fix the bug, replace the second

  return i1

  return i2
in the Find method.

I love this! Clever idea.

Thank you bugfix-66!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact