One of n lines in a file
A method of choosing a line randomly from a file:
- Without reading the file more than once
- When substantial parts of the file cannot be held in memory
- Without knowing how many lines are in the file
You are encouraged to solve this task according to the task description, using any language you may know.
Is to:
- keep the first line of the file as a possible choice, then
- Read the second line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/2.
- Read the third line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/3.
- ...
- Read the Nth line of the file if possible and make it the possible choice if a uniform random value between zero and one is less than 1/N
- Return the computed possible choice when no further lines exist in the file.
- Task
- Create a function/method/routine called
one_of_n
that givenn
, the number of actual lines in a file, follows the algotrithm above to return an integer - the line number of the line chosen from the file.
The number returned can vary, randomly, in each run. - Use
one_of_n
in a simulation to find what woud be the chosen line of a 10 line file simulated 1,000,000 times. - Print and show how many times each of the 10 lines is chosen as a rough measure of how well the algorithm works.
Note: You may choose a smaller number of repetitions if necessary, but mention this up-front.
Ada
<lang Ada>with Ada.Text_IO, Ada.Numerics.Float_Random;
procedure One_Of_N is
Num_Of_Lines: constant Positive := 10;
package Rnd renames Ada.Numerics.Float_Random; Gen: Rnd.Generator; -- used globally
function Choose_One_Of_N(Last_Line_Number: Positive) return Natural is Current_Choice: Natural := 0; begin for Line_Number in 1 .. Last_Line_Number loop if (Rnd.Random(Gen) * Float(Line_Number) <= 1.0) then Current_Choice := Line_Number; end if; end loop; return Current_Choice; end Choose_One_Of_N;
Results: array(1 .. Num_Of_Lines) of Natural := (others => 0); Index: Integer range 1 .. Num_Of_Lines;
begin
Rnd.Reset(Gen); for I in 1 .. 1_000_000 loop -- compute results Index := Choose_One_Of_N(Num_Of_Lines); Results(Index) := Results(Index) + 1; end loop;
for R in Results'Range loop -- output results Ada.Text_IO.Put(Integer'Image(Results(R))); end loop;
end One_Of_N;</lang>
Example output:
100104 100075 99761 99851 100457 100315 100101 99557 99678 100101
C
<lang c>#include <stdio.h>
- include <stdlib.h>
inline int irand(int n) { int r, randmax = RAND_MAX/n * n; while ((r = rand()) >= randmax); return r / (randmax / n); }
inline int one_of_n(int n) { int i, r = 0; for (i = 1; i < n; i++) if (!irand(i + 1)) r = i; return r; }
int main(void) { int i, r[10] = {0};
for (i = 0; i < 1000000; i++, r[one_of_n(10)]++); for (i = 0; i < 10; i++) printf("%d%c", r[i], i == 9 ? '\n':' ');
return 0; }</lang>output<lang>100561 99814 99816 99721 99244 99772 100790 100072 99997 100213</lang>
Factor
random-line uses an input stream. "/etc/passwd" ascii [ random-line . ] with-file-reader
would print a random line from /etc/passwd.
<lang factor>! rosettacode/random-line/random-line.factor USING: io kernel locals math random ; IN: rosettacode.random-line
- random-line ( -- line )
readln :> choice! 1 :> count! [ readln dup ] [ count 1 + dup count! random zero? [ choice! ] [ drop ] if ] while drop choice ;</lang>
one-of-n wants to use the same algorithm. Factor has duck typing, so one-of-n creates a mock object that quacks like an input stream. This mock object only responds to stream-readln, not the other methods of stream protocol. This works because random-line only needs stream-readln. The mock response is a line number instead of a real line.
<lang factor>! rosettacode/one-of-n/one-of-n.factor USING: accessors io kernel math rosettacode.random-line ; IN: rosettacode.one-of-n
<PRIVATE TUPLE: mock-stream count last ;
- <mock-stream> ( n -- stream )
mock-stream new 0 >>count swap >>last ;
M: mock-stream stream-readln ! stream -- line
dup [ count>> ] [ last>> ] bi < [ [ 1 + ] change-count count>> ] [ drop f ] if ;
PRIVATE>
- one-of-n ( n -- line )
<mock-stream> [ random-line ] with-input-stream* ;
USING: assocs formatting locals sequences sorting ; <PRIVATE
- f>0 ( object/f -- object/0 )
dup [ drop 0 ] unless ;
- test-one-of-n ( -- )
H{ } clone :> chosen 1000000 [ 10 one-of-n chosen [ f>0 1 + ] change-at ] times chosen keys natural-sort [ dup chosen at "%d chosen %d times\n" printf ] each ;
PRIVATE> MAIN: test-one-of-n</lang>
$ ./factor -run=rosettacode.one-of-n Loading resource:work/rosettacode/one-of-n/one-of-n.factor Loading resource:work/rosettacode/random-line/random-line.factor Loading resource:basis/formatting/formatting.factor Loading resource:basis/formatting/formatting-docs.factor 1 chosen 100497 times 2 chosen 100157 times 3 chosen 100207 times 4 chosen 99448 times 5 chosen 100533 times 6 chosen 99774 times 7 chosen 99535 times 8 chosen 99826 times 9 chosen 100058 times 10 chosen 99965 times
Icon and Unicon
<lang Icon>procedure main() # one of n
one_of_n_test(10,1000000)
end
procedure one_of_n(n)
every i := 1 to n do choice := (?0 < 1. / i, i) return \choice | fail
end
procedure one_of_n_test(n,trials)
bins := table(0) every i := 1 to trials do bins[one_of_n(n)] +:= 1 every writes(bins[i := 1 to n]," ") return bins
end</lang>
Sample output:
99470 99806 99757 99921 100213 100001 99778 100385 100081 100588
OCaml
<lang ocaml>let one_of_n n =
let rec aux i r = if i >= n then r else if Random.int (i + 1) = 0 then aux (succ i) i else aux (succ i) r in aux 1 0
let test ~n ~trials =
let ar = Array.make n 0 in for i = 1 to trials do let d = one_of_n n in ar.(d) <- succ ar.(d) done; Array.iter (Printf.printf " %d") ar; print_newline ()
let () =
Random.self_init (); test ~n:10 ~trials:1_000_000</lang>
Executing:
$ ocamlopt -o one.opt one.ml $ ./one.opt 100620 99719 99928 99864 99760 100151 99553 100529 99800 100076
Perl 6
<lang perl6>sub one_of_n($n) {
my $choice; $choice = $_ if rand * $_ < 1 for 1 .. $n; $choice - 1;
}
sub one_of_n_test($n = 10, $trials = 1000000) {
my @bins; @bins[one_of_n($n)]++ for ^$trials; @bins;
}
say one_of_n_test();</lang> Output:
100288 100047 99660 99773 100256 99633 100161 100483 99789 99910
Python
<lang python>from random import randrange
def one_of_n(n):
# Zero based line numbers choice = 0 for i in range(1, n): if randrange(i+1) == 0: choice = i return choice
def one_of_n_test(n=10, trials=1000000):
bins = [0] * n if n: for i in range(trials): bins[one_of_n(n)] += 1 return bins
print(one_of_n_test())</lang>
- Sample output
[99833, 100303, 99902, 100132, 99608, 100117, 99531, 100017, 99795, 100762]
Ruby
<lang ruby># Returns a random line from _io_, or nil if _io_ has no lines.
- # Get a random line from /etc/passwd
- line = open("/etc/passwd") {|f| random_line(f) }
def random_line(io)
choice = io.gets; count = 1 while line = io.gets rand(count += 1).zero? and choice = line end choice
end
def one_of_n(n)
# Create a mock IO that provides line numbers instead of lines. # Assumes that #random_line calls #gets. (mock_io = Object.new).instance_eval do @count = 0 @last = n def self.gets (@count < @last) ? (@count += 1) : nil end end random_line(mock_io)
end
chosen = Hash.new(0) 1_000_000.times { chosen[one_of_n(10)] += 1 } chosen.keys.sort.each do |key|
puts "#{key} chosen #{chosen[key]} times"
end</lang>
$ ruby one-of-n.rb 1 chosen 100470 times 2 chosen 100172 times 3 chosen 100473 times 4 chosen 99725 times 5 chosen 100600 times 6 chosen 99126 times 7 chosen 100297 times 8 chosen 99606 times 9 chosen 100039 times 10 chosen 99492 times
Tcl
<lang tcl>package require Tcl 8.5 proc 1ofN {n} {
for {set line 1} {$line <= $n} {incr line} {
if {rand() < 1.0/[incr fraction]} { set result $line }
} return $result
}
for {set i 0} {$i < 1000000} {incr i} {
incr count([1ofN 10])
} parray count; # Alphabetic order, but convenient</lang> Sample output:
count(1) = 99862 count(10) = 100517 count(2) = 100545 count(3) = 100339 count(4) = 99636 count(5) = 99920 count(6) = 99263 count(7) = 100283 count(8) = 99871 count(9) = 99764