One of n lines in a file: Difference between revisions

Line 1:

A method of choosing a line randomly from a file:

* Without reading the file more than once

::* Without reading the file more than once

* When substantial parts of the file cannot be held in memory

::* When substantial parts of the file cannot be held in memory

* Without knowing how many lines are in the file

::* Without knowing how many lines are in the file

Is to:

:* keep the first line of the file as a possible choice, then

::* 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 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 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

::* 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.

:* Return the computed possible choice when no further lines exist in the file.

;Task:

Line 17:

Line 18:

# Use <code>one_of_n</code> 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.

=={{header|Ada}}==