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.

 

{{trans|Python}}

 

V choice = 0

L(line) lines

R bins

 

 

;Sample output:

 

=={{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]

=={{header|Delphi}}==

See [https://rosettacode.org/wiki/One_of_n_lines_in_a_file#Pascal Pascal].

=={{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

10: 100452</pre>

 

Task description is contradictory in that it states number of lines

in file is unknown, and then that it is passed in as "n", and exercise

(at least when using Fortran, even on an old laptop) it only takes a

few seconds to run the 1 000 000, cases so actually ran them.

!> read lines one at a time and randomly choose one

!! using a Reservoir Sampling algorithm:

end subroutine one_of_n

end program reservoir_sample

{{out}}

<pre>

sys 0m1.465s

</pre>

 

'asume que la primera línea es 1

Next L0

 

 

 

=={{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:

of entropy such as /dev/random. The output shown below

is from a run of the following:

export LC_ALL=C

< /dev/random tr -cd '0-9' | fold -w 4 | jq -Mnr -f program.jq

 

'''program.jq'''

# of 4-digit PRNs uniformly distributed on [0-9999]

def oneOfN:

(n|oneOfN) as $num

| .[$num-1] += 1 )) as $freqs

{{out}}

<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;

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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()

 

inc result[oneOfN(n)]

 

 

{{out}}

 

=={{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}}

 

{$IFDEF FPC}

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}}

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

 

var rand = Random.new()

freqs[num-1] = freqs[num-1] + 1

}

 

{{out}}

</pre>

 

 

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

dim elegido(10)

 

next L0

 

 

=={{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}}