Fastest and Almost Forgotten: Martin Rem's Union-Find in Go

by bugfix-66 • 4 years ago

4 2 4 years ago

metadat• 4 years ago

I love this! Clever idea.

Thank you bugfix-66!

bugfix-66• 4 years ago

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

with

  return i2

in the Find method.

Related Stories