I've written a few functions that generate random numbers from an
arbitrary discrete distribution in O(log N) time, where N is the number
of possible values, using SortedRange.lowerBound(). It's similar to
dice() except that in exchange for O(N) auxiliary space and upfront
initialization cost you get O(log N) generation. I've attached the
code, which is fairly simple. Should this go in std.random, or is
needing this O(log N) performance on dice() niche enough that this
belongs in my dstats lib instead?
import std.range, std.array, std.traits, std.exception, std.random;
/**
Returns a delegate that generates random numbers similarly to $(D dice()) but
in $(BIGOH log N) time per number generated, where $(D N) is the number of
possible values. In exchange, it requires $(BIGOH N) auxiliary space and
$(BIGOH N) upfront initialization time.
*/
size_t delegate() fastDice(R)(R range)
if(isInputRange!R && isNumeric!(ElementType!R)) {
auto sorted = makeSortedSums(range);
size_t generate() {
return generateFastDice(rndGen, sorted);
}
return &generate;
}
/// Ditto
size_t delegate() fastDice(R, Random)(R range, Random gen)
if(isInputRange!R && isNumeric!(ElementType!R)) {
auto sorted = makeSortedSums(range);
size_t generate() {
return generateFastDice(gen, sorted);
}
return &generate;
}
private size_t generateFastDice(Random, R)(ref Random gen, R range) {
immutable point = uniform(0.0, cast(double) range.back, gen);
return range.lowerBound(point).length;
}
// Helper function to make the range of sums.
private auto makeSortedSums(R)(R range) {
auto sums = array(range);
foreach(i, ref elem; sums) {
enforce(elem >= 0, "Can't have negative probabilities for fastDice.");
elem += sums[i - 1];
}
return assumeSorted(sums);
}
unittest {
auto i = fastDice([0.0, 100.0])();
assert(i == 1);
i = fastDice([100.0, 0.0])();
assert(i == 0);
}
_______________________________________________
phobos mailing list
[email protected]
http://lists.puremagic.com/mailman/listinfo/phobos
