lemire/Code-used-on-Daniel-Lemire-s-blog — pull request #4 by pbannister (2013-08-17 19:47:51+00:00)
Title: Update UniformDistinct.java - if you want. :)

Refactored. Added comparable and pre-allocated shufflers.

(Really need to refactor the other example algorithms to re-use a pre-allocated array. Which is what you would do if you needed to run this often enough that time mattered.)

Output from running on my latop.

reporting speed Max: 1048576
hash hash/neg hybrid reservoir tree shuffle shuffle2
4096 0.11 0.12 0.14 0.01 0.17 0.04 4.60
2048 3.09 4.49 4.71 0.02 0.72 0.12 4.36
1024 5.40 5.33 0.67 0.04 1.80 0.27 8.41
512 4.53 4.81 9.84 0.09 1.71 0.52 8.26
256 5.92 5.75 15.37 0.19 4.05 1.07 11.40
128 5.57 5.64 20.66 0.36 4.59 2.08 11.61
64 4.55 4.52 21.56 0.71 3.64 3.93 19.17
32 5.09 5.05 25.75 1.34 3.71 7.59 18.92
16 4.70 4.83 27.15 2.40 3.02 9.93 21.46
8 3.25 3.58 27.36 4.05 2.25 16.87 22.55
4 2.59 2.49 25.08 6.34 1.43 20.52 22.06
2 2.03 1.80 21.04 10.15 0.88 23.17 24.32
4096 4.89 6.50 5.89 0.01 6.62 0.08 7.69
2048 5.53 6.66 6.65 0.02 6.55 0.04 7.16
1024 5.53 6.35 9.30 0.05 6.08 0.33 8.45
512 5.56 5.75 13.76 0.09 5.27 0.66 7.63
256 5.92 6.02 14.85 0.18 4.94 1.27 10.26
128 5.66 5.61 19.66 0.36 4.57 2.38 14.29
64 5.18 5.21 22.18 0.69 4.17 4.32 15.62
32 5.24 5.13 25.91 1.32 3.75 7.54 20.27
16 4.66 4.86 27.55 2.40 3.06 11.64 22.08
8 3.59 3.60 26.75 4.06 2.19 10.68 23.25
4 2.60 2.55 25.67 6.46 1.41 20.59 23.75
2 2.02 2.03 20.62 10.20 0.88 23.08 22.53
4096 5.27 6.14 6.07 0.01 6.33 0.08 7.59
2048 5.81 6.57 6.10 0.02 6.52 0.17 7.83
1024 5.66 5.97 9.07 0.05 6.14 0.31 7.95
512 5.41 5.77 12.76 0.09 5.64 0.63 9.07
256 5.96 5.67 17.20 0.19 4.97 1.24 10.99
128 5.67 5.71 19.72 0.37 4.59 2.40 13.92
64 5.44 5.56 22.67 0.71 4.22 4.33 17.66
32 5.23 5.12 25.87 1.34 3.78 7.65 20.34
16 4.80 4.88 27.01 2.30 3.20 12.43 22.07
8 3.47 3.47 27.39 4.08 2.26 17.15 22.83
4 2.61 2.60 24.89 6.00 1.38 20.61 22.57
2 2.02 2.01 21.17 10.44 0.89 22.75 24.24
reporting speed Max: 65536
hash hash/neg hybrid reservoir tree shuffle shuffle2
4096 2.65 3.52 3.51 0.01 3.27 0.13 7.61
2048 3.85 4.51 4.36 0.02 5.13 0.24 8.33
1024 4.86 5.42 8.45 0.05 5.64 0.48 9.06
512 5.63 6.39 12.71 0.09 6.16 0.92 10.61
256 6.15 6.74 17.58 0.19 6.10 1.72 13.37
128 6.35 6.47 21.54 0.37 6.54 2.71 13.24
64 5.96 5.92 22.18 0.72 6.08 7.46 22.76
32 5.73 6.21 28.35 1.39 5.28 11.21 28.63
16 5.72 6.02 29.08 2.55 4.97 15.65 32.50
8 5.47 5.98 27.70 4.47 4.38 26.13 37.07
4 5.71 5.72 26.56 7.41 3.78 30.53 37.07
2 5.44 5.57 22.86 12.21 2.79 34.75 38.94
4096 2.58 3.28 3.35 0.01 3.46 0.13 8.30
2048 3.83 4.25 4.47 0.02 4.98 0.26 6.21
1024 4.87 5.37 8.60 0.05 6.02 0.47 8.38
512 5.63 6.45 13.12 0.09 6.70 0.86 10.53
256 6.08 6.27 16.36 0.18 6.67 1.77 13.61
128 6.32 6.36 21.36 0.37 6.52 3.25 12.45
64 5.79 5.90 23.19 0.71 5.68 7.19 22.98
32 5.92 6.29 28.25 1.38 5.42 11.66 29.27
16 5.40 5.56 25.90 2.58 4.85 17.15 31.54
8 5.73 5.78 27.23 4.45 4.24 27.44 36.95
4 5.51 5.69 28.63 7.40 3.69 32.48 38.29
2 5.46 5.54 22.98 12.28 2.91 36.12 38.51
4096 2.92 3.68 3.70 0.01 3.64 0.12 9.24
2048 4.57 5.04 5.08 0.02 4.90 0.26 8.01
1024 5.45 5.84 8.74 0.05 6.22 0.50 9.15
512 5.99 6.06 13.07 0.09 6.44 1.07 10.31
256 6.44 7.07 17.72 0.19 6.21 1.99 13.03
128 6.62 6.93 21.50 0.37 6.52 3.40 15.55
64 6.51 6.30 22.45 0.73 6.01 6.12 20.40
32 6.03 6.32 28.30 1.39 5.50 8.80 23.60
16 5.72 6.17 29.97 2.59 4.76 16.71 32.88
8 5.88 5.98 27.62 4.54 4.03 27.08 37.26
4 5.79 5.89 26.89 7.46 3.59 31.67 38.46
2 5.57 5.61 22.94 12.10 2.91 36.02 38.44