One of n lines in a file: Difference between revisions

;Task:

# Create a function/method/routine called <code>one_of_n</code> that given <code>n</code>, the number of actual lines in a file, follows the algorithm above to return an integer - the line number of the line chosen from the file. <br>The number returned can vary, randomly, in each run.

# Print and show how many times each of the 10 lines is chosen as a rough measure of how well the algorithm works.

 

Note: This is a specific version of a Reservoir Sampling algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling

<br><br>

 

=={{header|Ada}}==

 

procedure One_Of_N is

Ada.Text_IO.Put(Integer'Image(Results(R)));

end loop;

 

Example output:<pre> 100104 100075 99761 99851 100457 100315 100101 99557 99678 100101</pre>

 

=={{header|Aime}}==

{

integer i, r;

 

0;

{{Out}}

<pre> 99804 100236 99846 100484 99888 99639 99886 99810 99923 100484</pre>

 

=={{header|ALGOL 68}}==

INT max lines = 10; CO Should be read from a file. CO

[max lines]INT stats;

print (("Line Number times chosen", newline));

FOR i TO max lines DO printf (($g(0)7xg(0)l$, i, stats[i])) OD

{{out}}

<pre>

=={{header|Applesoft BASIC}}==

A million iterations will take a very very long time to run. I suggest cranking the end value of J down to 1000 or less in line 20, and run this at full speed in a modern Apple II emulator. Initializing with RND(0) in line 10, seeds the RND function to be random, otherwise you may see the same results every time.

 

20 FOR J = 1 TO 1000000 : REMMAYBE TRY 100 ON A 1MHZ APPLE II

120 IF INT(RND(1) * I) = 0 THEN C = I

130 NEXT I

 

=={{header|AutoHotkey}}==

{{trans|Python}}

This simulation is for 100,000 repetitions.

; One based line numbers

choice = 1

Loop 10

out .= A_Index ": " b[A_Index] "`n"

Output:

<pre>---------------------------

 

=={{header|AWK}}==

#

# Usage:

END {

print line;

 

Test randomness

for i in `seq 1 10000`; do seq 1 10 | awk -v Seed=$RANDOM -f one_of_n_lines_in_a_file.awk; done |sort|uniq -c

 

<pre>

{{works with|QBasic}}

 

 

DIM L0 AS LONG, c AS LONG

NEXT

oneofN& = choice

 

Sample output:

 

'''Batch file to call one_of_n'''

@echo off

 

del output.txt

pause>nul

 

 

'''one_of_n'''

setlocal enabledelayedexpansion

 

endlocal

exit /b

 

 

 

=={{header|BBC BASIC}}==

DIM cnt%(10)

FOR test% = 1 TO 1000000

IF RND(1) <= 1/i% l% = i%

NEXT

'''Output:'''

<pre>

 

=={{header|C}}==

#include <stdlib.h>

 

 

return 0;

<pre>100561 99814 99816 99721 99244 99772 100790 100072 99997 100213</pre>

 

=={{header|C sharp|C#}}==

 

class Program

{

}

}

<pre>

1 99777

=={{header|C++}}==

{{works with|C++11}}

#include <iostream>

#include <iterator>

cout << '\n';

}

<pre>99981 99806 100190 99831 99833 100291 99356 100165 100279 100268</pre>

 

=={{header|Chapel}}==

 

 

proc one_of_n(n) {

 

return keep;

 

=={{header|Clojure}}==

The function ''rand-seq-elem'' actually implements the algorithm; ''one-of-n'' uses it to select a random element from the sequence (1 ... n). (Though they weren't automatically highlighted when I wrote this, ''rand-int'', ''second'', and ''frequencies'' and ''println'' are also standard functions)

(let [f (fn [[k old] new]

[(inc k) (if (zero? (rand-int k)) new old)])]

(let [countmap (frequencies (repeatedly 1000000 #(one-of-n 10)))]

(doseq [[n cnt] (sort countmap)]

 

Sample output

2 99933

3 99820

8 100020

9 100342

 

To actually get a randomly selected line from a file:

 

(defn rand-line [filename]

(with-open [reader (io/reader filename)]

 

=={{header|Common Lisp}}==

Great place to use closures.

(let ((cur 0) (sel nil))

#'(lambda (v)

(let* ((sel (funcall fnt 9)))

(setf (aref counts sel) (+ 1 (aref counts sel)))))))

Output:

 

=={{header|D}}==

 

// Zero-based line numbers.

bins.writeln;

writeln("Total of bins: ", bins[].sum);

{{out}}

<pre>[100091, 99940, 100696, 99799, 100234, 99419, 100225, 99716, 99942, 99938]

Total of bins: 1000000</pre>

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

class

ONE_OF_N_LINES

 

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def task do

dict = Enum.reduce(1..1000000, %{}, fn _,acc ->

end

 

 

{{out}}

 

=={{header|Erlang}}==

-module( one_of_n_lines_in_file ).

 

 

update_counter( _N, Dict ) -> dict:update_counter( one_of_n(10), 1, Dict ).

{{out}}

<pre>

 

=={{header|ERRE}}==

PROGRAM ONE_OF_N

 

PRINT

END PROGRAM

{{out}}

<pre>

 

=={{header|Euphoria}}==

include std/rand.e

include std/math.e

 

main()

Sample Output:

<pre>

 

=={{header|F_Sharp|F#}}==

 

[<EntryPoint>]

test 10 1000000

Output

<pre>99721 100325 99939 99579 100174 100296 99858 99910 100192 100006</pre>

''random-line'' uses an input stream. <code>"/etc/passwd" ascii [ random-line . ] with-file-reader</code> would print a random line from /etc/passwd.

 

USING: io kernel locals math random ;

IN: rosettacode.random-line

[ choice! ] [ drop ] if

] while drop

 

''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.

 

USING: accessors io kernel math rosettacode.random-line ;

IN: rosettacode.one-of-n

] each ;

PRIVATE>

 

<pre>$ ./factor -run=rosettacode.one-of-n

=={{header|Forth}}==

{{works with|GNU Forth}}for random.fs and 1/f

 

: frnd

: .hist cr 10 0 do i 1+ 2 .r ." : " i hist @ . cr loop ;

 

{{out}}

<pre>&gt; gforthamd64 rosetta_one_of_n.fs

9: 100309

10: 100452</pre>

 

=={{header|Go}}==

 

import (

// task item 3. show frequencies.

fmt.Println(freq)

Output:

<pre>

The function selItem will operate on any list, whether a lazy list of strings from a file or a list of numbers, as in the test.

 

import System.Random

import Data.List

else putStrLn.(\(l, n, _, _) -> "Line " ++

show n ++ ": " ++ l)

 

Running without any args runs the test:

=={{header|Icon}} and {{header|Unicon}}==

{{trans|Python}}

one_of_n_test(10,1000000)

end

every writes(bins[i := 1 to n]," ")

return bins

 

Sample output:<pre>99470 99806 99757 99921 100213 100001 99778 100385 100081 100588</pre>

This implementation also implements line buffering, since the built-in line handling does not work quite how I want it to work. That said, if a line is too large (many gigabytes, for example), the system will crawl to a halt when the line is read.

 

file=. boxopen y

r=. ''

end.

r

 

Usage: randLineBig 'filename'

Testing:

 

20

(#;~.)/.~ /:~ <@randLineBig"0]1e6#<'seq.txt'

├──────┼───┤

│99583 │9 │

 

=={{header|Java}}==

{{trans|Python}}

import java.util.Random;

 

}

}

 

Sample output:

<pre>[99832, 99958, 100281, 99601, 99568, 99689, 100118, 99753, 100659, 100541]</pre>

 

=={{header|Julia}}==

const N = 10

const GOAL = 10^6

println(@sprintf " %2d => %6d" i nhist[i])

end

 

{{out}}

 

=={{header|Kotlin}}==

 

import java.util.Random

}

for (i in 1..n) println("Line ${"%-2d".format(i)} = ${freqs[i - 1]}")

 

Sample output:

 

=={{header|Liberty BASIC}}==

DIM chosen(10)

 

NEXT

END FUNCTION

{{Out}}

<pre>

 

=={{header|Lua}}==

math.randomseed(os.time())

 

print(k,v)

end

{{Out}}

<pre>

 

=={{header|Maple}}==

with(RandomTools[MersenneTwister]);

one_of_n_lines_in_a_file := proc(fn)

return(n);

end proc;

 

rec = selected = Read[strm];

While[rec =!= EndOfFile,

If[RandomReal[] < 1/n, selected = rec]];

Close[strm];

 

=={{header|MATLAB}} / {{header|Octave}}==

 

fid = fopen(fn,'r');

if fid<0, return; end;

end;

end

test

for k = 1:1e6;

n = one_of_n_lines_in_a_file('f1');

x(n) = x(n) + 1;

end;

<pre> 1 2 3 4 5 6 7 8 9 10

105973 105715 106182 106213 105443 105255 106048 105999 105366 106070</pre>

 

=={{header|Nim}}==

randomize()

 

proc oneOfN(n: int): int =

result = 0

result = x

 

inc result[oneOfN(n)]

 

 

=={{header|OCaml}}==

let rec aux i r =

if i >= n then r else

let () =

Random.self_init ();

 

Executing:

=={{header|PARI/GP}}==

gp can't read individual lines from a file (PARI would be needed for that) but it can do the simulation easily. The <code>random()</code> function produces high-quality pseudorandom numbers (via Brent's [http://maths-people.anu.edu.au/~brent/pub/pub224.html XORGEN]) so the output passes a chi-square test easily (p = 0.848).

my(chosen=1);

for(k=2,n,

chosen;

}

{{out}}

<pre>%1 = [99933, 100021, 100125, 100071, 99876, 99485, 100108, 100183, 99861, 100337]</pre>

=={{header|Pascal}}==

{{works with|Free_Pascal}}

 

function one_of_n(n: longint): longint;

i: integer;

begin

for i := low(a) to high(a) do

end;

 

writeln('Number of times line ', i, ' was selected: ', lines[i]);

writeln('Total number selected: ', sum(lines));

Output:

<pre>% ./OneOfNLines

===using int-random===

int-random needn't the calculation of (1.0 /i).That is 3-times faster.I implemented the use of reading a random line of a textfile as discribed.In that case, there is no need to use the functoin one_of_n .

Program OneOfNLines(InPut,Output);

{$h+} //use Ansistring

inc(LnCnt,cntLns[i]);

writeln('Total number selected: ', LnCnt);

;Output:

<pre>

=={{header|Perl}}==

 

use warnings;

use strict;

my @freq;

++$freq[ one_of_n($size) - 1 ] for 1 .. $repeat;

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(let R 1

(for I N

(do 1000000

(inc (nth L (one-of-n 10))) )

Output:

<pre>-> (99893 100145 99532 100400 100263 100229 99732 100116 99709 99981)</pre>

=={{header|PowerShell}}==

'''Translation''' of: '''C#'''

function Get-OneOfN ([int]$Number)

{

 

[PSCustomObject]$table

{{Out}}

<pre>

</pre>

The above version runs in ~650 seconds, because of the large overhead of calling PowerShell functions and binding their parameters. With a small change to move the function into a class method, the parameter binding becomes faster, and swapping Get-Random for System.Random, the overall code runtime drops to ~20 seconds. Changing the ordered hashtable to a Generic Dictionary reduces it again to ~15 seconds:

[System.Random]$rng

 

}

 

=={{header|PureBasic}}==

ProcedureReturn Random(1000000) / 1000000

EndProcedure

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

Sample output:

<pre>99959 100011 100682 100060 99834 99632 100083 99817 99824 100098</pre>

=={{header|Python}}==

To be more in line with the spirit of the problem, <code>one_of_n</code> will take the "lines" as an iterator, guaranteeing that it only traverses the lines one time, and does not know the length until the end.

try:

range = xrange

return bins

 

 

;Sample output:

 

=={{header|R}}==

{

choice <- 1L

}

 

 

Sample output:

 

=={{header|Racket}}==

#lang racket

 

 

|#

 

=={{header|Raku}}==

(formerly Perl 6)

{{trans|Python}}

my $choice;

$choice = $_ if .rand < 1 for 1 .. $n;

}

 

Output:

<pre>100288 100047 99660 99773 100256 99633 100161 100483 99789 99910</pre>

 

=={{header|REXX}}==

N= 10 /*the number of lines in pseudo-file. */

@.= 0 /*zero all the (ten) "buckets". */

do j=1 for N /*display randomness counts (buckets). */

say "number of times line" right(j, 2) "was selected:" right(@.j, 9)

{{out|output|text=&nbsp; when using the internal default input:}}

<pre>

 

=={{header|Ring}}==

cnt = list(10)

for nr = 1 to 10000

next

return d

<pre>

1 : 15

 

=={{header|Ruby}}==

# # Get a random line from /etc/passwd

# line = open("/etc/passwd") {|f| random_line(f) }

chosen.keys.sort.each do |key|

puts "#{key} chosen #{chosen[key]} times"

 

<pre>$ ruby one-of-n.rb

 

=={{header|Run BASIC}}==

c = oneOfN(10)

chosen(c) = chosen(c) + 1

next

oneOfN = choice

<pre>1 99034

2 98462

{{libheader|rand}}

You could also use `rand::seq::sample_iter` which uses a more general version of this problem, Reservoir Sampling: https://en.wikipedia.org/wiki/Reservoir_sampling.

 

use rand::{Rng, thread_rng};

println!("{:?}", dist);

}

{{out}}

<pre>

 

=={{header|Scala}}==

if (n < 1) i else one_of_n(n - 1, if (scala.util.Random.nextInt(j) == 0) n else i, j + 1)

 

}

 

{{out}}

<pre>100014

 

=={{header|Seed7}}==

 

const func integer: one_of_n (in integer: n) is func

end for;

writeln;

 

Output:

=={{header|Sidef}}==

{{trans|Raku}}

var choice

n.times { |i|

}

 

 

{{out}}

 

=={{header|Swift}}==

var result = 1

for i in 2...n {

}

 

{{Output|Sample Output}}

 

=={{header|Tcl}}==

proc 1ofN {n} {

for {set line 1} {$line <= $n} {incr line} {

incr count([1ofN 10])

}

Sample output:

<pre>

 

=={{header|VBScript}}==

Dim chosen(10)

 

Next

End Function

 

{{Out}}

10. 99895

</pre>

 

=={{header|zkl}}==

{{trans|Python}}

#if 0 // iterative

choice:=Void;

}

 

A Ref is a strong reference to a value, Ref.set(value) sets the Ref, Ref.value gets the value. A pump pumps data through a list of functions into a sink, Void.Skip skips this value (ie same as continue in a loop).

{{out}}