Anonymous user
Knuth's algorithm S: Difference between revisions
→{{header|Ada}}: Ada solution added
(→{{header|Perl 6}}: new entry) |
(→{{header|Ada}}: Ada solution added) |
||
Line 24:
* [[Accumulator factory]]
=={{header|
Instead of defining a function S_of_N_Creator, we define a generic packgage with that name. The generic parameters are N (=Sample_Size) and the type of the items to be sampled:
<lang Ada>generic
Sample_Size: Positive;
type Item_Type is private;
package S_Of_N_Creator is
subtype Index_Type is Positive range 1 .. Sample_Size;
type Item_Array is array (Index_Type) of Item_Type;
procedure Update(New_Item: Item_Type);
function Result return Item_Array;
end S_Of_N_Creator;</lang>
Here is the implementation of that package:
<lang Ada>with Ada.Numerics.Float_Random, Ada.Numerics.Discrete_Random;
package body S_Of_N_Creator is
package F_Rnd renames Ada.Numerics.Float_Random;
F_Gen: F_Rnd.Generator;
package D_Rnd is new Ada.Numerics.Discrete_Random(Index_Type);
D_Gen: D_Rnd.Generator;
Item_Count: Natural := 0; -- this is a global counter
Sample: Item_Array; -- also used globally
procedure Update(New_Item: Item_Type) is
begin
Item_Count := Item_Count + 1;
if Item_Count <= Sample_Size then
-- select the first Sample_Size items as the sample
Sample(Item_Count) := New_Item;
else
-- for I-th item, I > Sample_Size: Sample_Size/I chance of keeping it
if (Float(Sample_Size)/Float(Item_Count)) > F_Rnd.Random(F_Gen) then
-- randomly (1/Sample_Size) replace one of the items of the sample
Sample(D_Rnd.Random(D_Gen)) := New_Item;
end if;
end if;
end Update;
function Result return Item_Array is
begin
Item_Count := 0; -- ready to start another run
return Sample;
end Result;
begin
D_Rnd.Reset(D_Gen); -- at package instantiation, initialize rnd-generators
F_Rnd.Reset(F_Gen);
end S_Of_N_Creator;</lang>
The main program:
<lang Ada>with S_Of_N_Creator, Ada.Text_IO;
procedure Test_S_Of_N is
Repetitions: constant Positive := 100_000;
type D_10 is range 0 .. 9;
package S_Of_3 is new S_Of_N_Creator(Sample_Size => 3, Item_Type => D_10);
Sample: S_Of_3.Item_Array;
Result: array(D_10) of Natural := (others => 0);
begin
for J in 1 .. Repetitions loop
-- get Sample
for Dig in D_10 loop
S_Of_3.Update(Dig);
end loop;
Sample := S_Of_3.Result;
-- update current Result
for Item in Sample'Range loop
Result(Sample(Item)) := Result(Sample(Item)) + 1;
end loop;
end loop;
-- finally: output Result
for Dig in Result'Range loop
Ada.Text_IO.Put(D_10'Image(Dig) & ":"
& Natural'Image(Result(Dig)) & "; ");
end loop;
end Test_S_Of_N;</lang>
A sample output:
<pre> 0: 30008; 1: 30056; 2: 30080; 3: 29633; 4: 29910; 5: 30293; 6: 30105; 7: 29924; 8: 29871; 9: 30120; </pre>
=={{header|C}}==
Instead of returning a closure we set the environment in a structure:
| |||