|START Conference Manager|
This paper presents an implementation of equal? that performs well on a wide range of inputs both large and small, cyclic and acyclic by incurring most of the overhead only when necessary. The algorithm is presented as a sequence of incremental improvements to the straightforward implementation of equal? that works only for acyclic inputs. The final result is an implementation that guarantees termination while never being more than a small factor slower than whichever of the acyclic or union-find algorithms would have been fastest.
START Conference Manager (V2.54.6)