seq optimisation: investigate using sample_iter instead of sample_indicies_inplace

[vitiral]

I would like to measure performance between these methods, especially for amount < length/10. I have a feeling that sample_indicies_inplace will beat sample_inplace since they both require at least one pass of the whole array (for sample_indicies_inplace, it requires it to construct the indices).

[dhardy]

No, doesn't look like it's ever a good option (at least now we have Floyd's alg too):

test misc_sample_iter_100_of_1M      ... bench:   9,264,560 ns/iter (+/- 118,774)
test misc_sample_iter_100_of_1k      ... bench:      10,005 ns/iter (+/- 398)
test misc_sample_iter_10_of_100      ... bench:       1,066 ns/iter (+/- 27)
test misc_sample_iter_10_of_1k       ... bench:       9,432 ns/iter (+/- 572)
test misc_sample_iter_10_of_20       ... bench:         164 ns/iter (+/- 4)
test misc_sample_iter_1_of_1         ... bench:          30 ns/iter (+/- 0)
test misc_sample_iter_1_of_10        ... bench:         149 ns/iter (+/- 9)

Compare to these results which are fully shuffled (above are not):

test misc_sample_indices_100_of_1G   ... bench:       2,699 ns/iter (+/- 31)
test misc_sample_indices_100_of_1M   ... bench:       2,694 ns/iter (+/- 45)
test misc_sample_indices_100_of_1k   ... bench:         508 ns/iter (+/- 1)
test misc_sample_indices_10_of_1k    ... bench:          71 ns/iter (+/- 0)
test misc_sample_indices_1_of_1k     ... bench:          28 ns/iter (+/- 0)
test misc_sample_indices_400_of_1G   ... bench:      27,095 ns/iter (+/- 1,254)
test misc_sample_indices_500_of_1G   ... bench:      28,048 ns/iter (+/- 3,225)