JuliaLang/DataStructures.jl — pull request #36 by wsliang (2014-05-26 17:25:17+00:00)
Title: Disjoint

The disjoint-set data structure seemed a bit slow, over 3x the speed of a C++ reference:
````
~/disjoint > ./disjoint
0.061481
~/disjoint > ./disjoint
0.061004
~/disjoint > ./disjoint
0.061247
````
````
~/.julia/v0.3/DataStructures/test > julia bench_disjoint_set.jl master=
elapsed time: 0.193454033 seconds (16006792 bytes allocated)
~/.julia/v0.3/DataStructures/test > julia bench_disjoint_set.jl master=
elapsed time: 0.192407743 seconds (16006856 bytes allocated)
~/.julia/v0.3/DataStructures/test > julia bench_disjoint_set.jl master=
elapsed time: 0.195339228 seconds (16006824 bytes allocated)
````

Making the type immutable (and replacing the mutable ``ngroups::Int`` type with a length 1 vector ``ngroups::Vector{Int}``) results in an almost 2x speed increase, as well as eliminating essentially all of the memory allocation. This is within 1.7x C++ speed.
````
~/.julia/v0.3/DataStructures/test > julia bench_disjoint_set.jl disjoint=
elapsed time: 0.103117607 seconds (6888 bytes allocated)
~/.julia/v0.3/DataStructures/test > julia bench_disjoint_set.jl disjoint=
elapsed time: 0.109216987 seconds (6888 bytes allocated)
~/.julia/v0.3/DataStructures/test > julia bench_disjoint_set.jl disjoint=
elapsed time: 0.103264055 seconds (6888 bytes allocated)
````