D-Programming-Language/phobos — pull request #1716 by Zshazz (2013-11-25 01:11:53+00:00)
Title: Fix issue 11597 - Speed up std.random.dice

See also:
https://d.puremagic.com/issues/show_bug.cgi?id=11597
Pull request #1702 (which this based off of)

This changes the way that diceImpl works by allocating and producing a cumulative sum array and then binary searching on it to find where the uniformly chosen point lies on the array. This slightly improves performance and will allow dice to perform better when the number of proportions is large.

Additionally, this change allows for a relaxing of the range constraint. The new way does not need .save() on proportions, so it is possible to use an InputRange. Therefore, the new constraint reflects this capability.

One thing to note about this implementation is that it allocates whereas the original diceImpl does not. This may also be seen as a disadvantage, so take note of that.