On Monday, 18 November 2013 at 03:10:22 UTC, bearophile wrote:
See also:
http://d.puremagic.com/issues/show_bug.cgi?id=5849
Bye,
bearophile
Nice one, bearophile. You called it.
I've done a bit of testing with the solution you've attached to
that bug report. It's 10-50% faster than my solution depending on
how many proportions are provided (I've tested as much as
500_000). Despite mine being O(log(n)) to find the next dice roll
and your solution being O(1), there really isn't that much of a
difference. Strangely (to me), your solution actually seems to
grow faster than mine as the number of proportions grow larger
despite the proof claiming it should grow slower (although
testing for > 500_000 seems pointless until actual data demands
it).
As far as integer proportions go, I think my solution might be
better overall because it's effectively equivalent to the current
dice implementation (meaning it could be used as a near drop-in
replacement and get precisely the same results, as long as the
proportions are floating point values) and the code is simpler
and avoids hiding any real bugs.
(That said, the original implementation has a bug that was easy
to spot on my second comb-through)
--- in popFront:
// Return the number of elements that are not strictly greater
than point
_front = _propCumSumSorted.length -
_propCumSumSorted.upperBound!pol(point).length;
---
On the other hand, a cumulative sum array approach (like mine and
the std.random.dice implementation) will likely suffer major
precision issues with floating point numbers. Especially if the
first proportions are very large and the later proportions are
very small. I haven't closely looked through the algorithm you're
using to see whether it fares better, but I can't imagine it
doing much worse.
