línea al azar en el archivo

Question

Esta pregunta me fue dada durante una entrevista. La entrevista es mucho más, pero todavía estoy pensando en un problema y su HTE me molesta:

Tiene un lenguaje que contiene las siguientes herramientas: una función rand(), while y for bucles, if declaraciones, y un método readline() (similar a python's readline()). Dadas estas herramientas, escribe un algoritmo que devuelve una línea aleatoria en el archivo. No conoce el tamaño del archivo y solo puede recorrer el contenido del archivo una vez.

Answer 1

no sé la respuesta deseada, pero mi solución sería la siguiente:

chosen_line = "" 
lines = 0 

while (current_line = readline()): 
    if (rand(0, lines) == 0): 
     chosen_line = current_line 

    lines++ 

return chosen_line 

Editar: Una buena explicación de por qué funciona este fue publicada en this comment.

Answer 2

Un método, garantizando una distribución uniforme:

(1) leer el archivo línea por línea en una matriz (o similar, por ejemplo pitón list)

(2) Usar rand() para seleccionar una número entre 0 y el índice más grande en la matriz.

Otro, no garantiza una distribución uniforme:

leer cada línea. En cada lectura, también llame a rand(). Si supera un umbral, devuelva la línea.

Answer 3

Aunque es similar a la tercera opción de Marcin, la implementación de Luc siempre devuelve la primera línea, al analizar todo el archivo.

Debería ser algo como:

chosen_line = "" 
treshold = 90 
max = 100 

while chosen_line == "": 
    current_line = readline() 
    if (rand(0, max) > treshold): 
     chosen_line = current_line 

print chosen_line 

También podría volver current_line en el caso se eligió ninguna línea y leer todo el archivo.