¿Cómo puedo devolver una línea aleatoria desde un archivo? Pregunta de entrevista

Question

Me estoy preparando para una entrevista telefónica. Me encontré con estas preguntas en internet. ¿Alguien puede decirme algunas buenas respuestas para estos?

1. suponga que le importa un archivo de texto y pido un escribir un programa que devolverá una línea al azar a partir del archivo (todas las líneas deben tener la misma probabilidad de ser devuelto)

2. mismo como parte 1, excepto que esta vez el archivo de texto completo no puede caber en la memoria principal

3. Igual que en la parte 2, excepto que ahora tiene una transmisión en lugar de un archivo.

Por favor ayuda.

Ok ... @ Todos, realmente tenía algunas ideas en mi mente antes de preguntar esto ... Viendo el ataque implacable de mis compañeros SOers, estoy publicando mis respuestas. Por favor, siéntase libre de atacarlos también ...

1: Cuente el número de '\ n' en el archivo. Genere un número aleatorio entre 1 y el número y devuelva la línea después del número 1 '\ n'.

2: Traiga el archivo a la memoria principal parte por parte y siga el procedimiento anterior.

3: No tengo mucha idea sobre esto y agradecería cualquier información.

Su maravilloso que ustedes realmente dan una inspiración para seguir adelante .....

Answer 1

Re 1: Uso solución al 2

Re 2: Usted quiere escanear todo el archivo utilizando un RandomAccessFile acceso para contar el número de líneas y (posiblemente) almacenar en caché los punteros de archivo para cada inicio de línea. Luego puede elegir uno al azar (supongo que esta pregunta no se trata de cómo generar números aleatorios) y regresar a ese punto de inicio, leer la línea y devolverla. Si lo quiere rápido, asegúrese de que está guardando en búfer las lecturas (si no, raf es lento).

Re 3: Si la transmisión no cabe en la memoria (es decir, no se puede almacenar en caché por completo) y no sabe cuántas líneas hay en la secuencia sin leer toda la secuencia (suponiendo que solo llega a leer una vez) entonces no puedo ver una solución. Yo también espero las respuestas ...

Answer 2

1. Lea todas las líneas en una matriz, devuelva una línea aleatoria en el rango de 1 y la cantidad de líneas.

2. Más simple: Cuente las líneas, elija un número de línea al azar, revise el archivo una segunda vez y devuélvalo.

3. Solo tiene que recordar una línea. Cada nueva línea tiene una probabilidad de 1/N (N son líneas leídas).

   Pseudocódigo:

   i = 1 
   chosen_line = "" 
   for line in lines: 
       if random() < 1/i: # random returns a uniform random number in [0,1) 
        chosen_line = line 
       i += 1 
   return chosen_line 
   

Algoritmo número 3 podría ser utilizado para 1 y 2 también.

Answer 3

# 3: escriba la secuencia en un archivo en el disco y use la solución 2. No es la solución más eficiente, por supuesto, pero es muy simple.

Answer 4

Puede hacerlo sin tener que leer todas las líneas en la memoria, por lo que funciona bien para archivos de gran tamaño. Pseudocódigo:

linenum := 0 
ret := '' 
while more lines to read: 
    line := readline() 
    linenum := linenum + 1 
    r := uniform_random(0, linenum) 
    if r < 1: 
     ret := line 

return ret 

Prueba: Comenzamos señalando que siempre guardamos la primera línea en ret. Si el archivo tiene una línea, la va a elegir y listo.

Para el archivo de dos líneas, ret guardará la primera línea el 100% de las veces, y la segunda línea se guardará en ret el 50% del tiempo durante la segunda iteración del ciclo. Por lo tanto, cada línea tiene una probabilidad de 0.5 de ser seleccionado.

Supongamos que este método funciona para archivos de ≤ N líneas. Para demostrar que esto significa que funciona para N+1, en la iteración (N+1) del ciclo, existe una probabilidad de 1/(N+1) de que se seleccione la última línea (random(0, N+1) < 1 tiene esa probabilidad). Por lo tanto, la última línea tiene 1/(N+1) probabilidad de ser seleccionado. La probabilidad de que todas las demás líneas sean seleccionadas seguirá siendo igual entre sí, llamémoslo x. Luego, N*x + 1/(N+1) == 1, lo que significa que x = 1/(N+1).

La prueba por inducción está completa.

Editar: Vaya, no vi el tercer método de la primera respuesta antes de responder. Aún así, mantendré esta publicación aquí solo para la prueba y la oportunidad para que otras personas la corrijan si hay algún error en ella.