Anonymous user
Knuth's algorithm S: Difference between revisions
Updated both D entries
m (Corrected two errors (pointed to by Sean Kanaley)) |
(Updated both D entries) |
||
Line 499:
if (i <= n)
sample ~= item;
else if (uniform(0.0, 1.0) <
sample[uniform(0, n)] = item;
return sample;
Line 509:
size_t[10] bin;
foreach (immutable trial; 0 .. nRuns) {
int[] sample;
foreach (immutable item; 0 .. bin.length)
sample = sofn(item);
foreach (immutable s; sample)
bin[s]++;
}
Line 522:
<pre>Item counts for 100000 runs:
[30191, 29886, 29988, 30149, 30251, 29997, 29748, 29909, 30041, 29840]</pre>
===Faster Version===
<lang d>import std.stdio, std.random, std.algorithm;
double random01(ref Xorshift rng) {
immutable r = rng.front /
rng.popFront;
return r;
Line 539 ⟶ 540:
if (i <= n)
sample[i - 1] = item;
else if (rng.random01 <
sample[uniform(0, n, rng)] = item;
return sample[0 .. min(i, $)];
|