On Monday, 3 June 2013 at 17:35:22 UTC, Joseph Rushton Wakeling
wrote:
On 06/03/2013 07:00 PM, Diggory wrote:
Thanks for testing before dismissing completely :P The way it
returns results
can be improved a lot by pre-allocating a range of the
necessary size/using a
range passed in.
Surely. :-)
The complexity is O(N²) where N is the number of samples out
of M. The algorithm
is something I just thought of although I've possibly used it
before and I'm
sure someone else has thought of it too. It's quite simple, it
effectively says
"pick a value from the range except for this value"
recursively but instead of
dividing the range in two, it shifts the top part down first
to make a
contiguous range and then shifts the results which are past
the split up one
afterward.
It's an interesting little piece of invention. I'll have to
look around and see
if there's anything similar documented. I've not seen anything
in the
literature which has this particular property of O(N) random
variates plus
O(N^2) calculation.
The fact that it's not sequential might have been a bit of an
issue
historically, which maybe explains why I haven't come across
something like it.
I expect the phobos implementation to be something like O(M)
in which case my
method would be faster whenever N < sqrt(M) (with the
optimisations)
No, the Phobos implementation is O(N) -- I wrote it :-) See:
http://braingam.es/2012/07/sampling-d/
The API is Andrei's -- the original implementation used what
Knuth refers to as
Algorithm S [which is really simple and easy to implement and
check, but is
indeed O(M)], I updated it to use Algorithm D (which is
complicated:-).
So, since randomSample takes kN time where k is constant, your
algorithm will
probably win where N < k.
I found that the sampling time was about equal with N = 50 and
your algorithm as
it's currently written.
I'd guess that the heavy use of floating point arithmetic to
calculate the step sizes means that algorithm has a fairly large
constant overhead even though the complexity is smaller.
