4 ms·
Fastest and Almost Forgotten: Martin Rem's Union-Find in Go
- metadat 4y agoI love this! Clever idea. Thank you bugfix-66!
- bugfix-66 4y agoThis 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": https://seriouscomputerist.atariverse.com/media/pdf/book/Discipline%20of%20Programming.pdf https://seriouscomputerist.atariverse.com/media/pdf/book/Dis... 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.