Knuth's algorithm S: Difference between revisions
Content added Content deleted
(Updated D code) |
|||
| Line 53: | Line 53: | ||
int[] sample; |
int[] sample; |
||
int i; |
int i; |
||
auto s_of_n(in int item) { |
|||
i++; |
i++; |
||
if (i <= n) { |
if (i <= n) { |
||
// Keep first n items |
|||
sample ~= item; |
sample ~= item; |
||
} else if (uniform(0.0, 1.0) < (cast(double)n / i)) { |
} else if (uniform(0.0, 1.0) < (cast(double)n / i)) { |
||
// Keep item |
|||
sample = remove(sample, uniform(0, n)); |
sample = remove(sample, uniform(0, n)); |
||
sample ~= item; |
sample ~= item; |
||
| Line 78: | Line 76: | ||
} |
} |
||
enum nruns = |
enum nruns = 100_000; |
||
foreach (trial; 0 .. nruns) { |
foreach (trial; 0 .. nruns) { |
||
auto s_of_n2 = s_of_n_creator(3); |
auto s_of_n2 = s_of_n_creator(3); |
||
| Line 88: | Line 86: | ||
} |
} |
||
writefln("\nTest item frequencies for %d runs:", nruns); |
writefln("\nTest item frequencies for %d runs:", nruns); |
||
foreach ( |
foreach (d; bin) |
||
write(d, " "); |
|||
}</lang> |
}</lang> |
||
Example output: |
Example output: |
||
| Line 96: | Line 94: | ||
Item: 1 -> sample: [0, 1] |
Item: 1 -> sample: [0, 1] |
||
Item: 2 -> sample: [0, 1, 2] |
Item: 2 -> sample: [0, 1, 2] |
||
Item: 3 -> sample: [ |
Item: 3 -> sample: [1, 2, 3] |
||
Item: 4 -> sample: [ |
Item: 4 -> sample: [1, 3, 4] |
||
Item: 5 -> sample: [ |
Item: 5 -> sample: [1, 3, 4] |
||
Item: 6 -> sample: [1, |
Item: 6 -> sample: [1, 3, 4] |
||
Item: 7 -> sample: [1, |
Item: 7 -> sample: [1, 3, 7] |
||
Item: 8 -> sample: [ |
Item: 8 -> sample: [1, 7, 8] |
||
Item: 9 -> sample: [ |
Item: 9 -> sample: [1, 7, 8] |
||
Test item frequencies for |
Test item frequencies for 100000 runs: |
||
29926 30033 30145 30172 29882 30104 29773 30071 29858 30036</pre> |
|||
0: 300033 |
|||
1: 299914 |
|||
2: 299505 |
|||
3: 300033 |
|||
4: 299704 |
|||
5: 299893 |
|||
6: 299871 |
|||
7: 300297 |
|||
8: 300292 |
|||
9: 300458</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||