¿Cómo obtener una línea aleatoria de un archivo de texto en Java?

Question

Digamos que hay un archivo demasiado grande para ponerlo en la memoria. ¿Cómo puedo obtener una línea aleatoria de ella? Gracias.

Actualización: Quiero las probabilidades de que cada línea sea igual.

Answer 1

he aquí una solución. Eche un vistazo al método choose() que hace lo real (el método main() ejerce repetidamente choose(), para mostrar que la distribución es de hecho bastante uniforme).

La idea es simple: cuando lee la primera línea tiene un 100% de posibilidades de ser elegido como resultado. Cuando lee la 2da línea tiene un 50% de posibilidades de reemplazar la primera línea como resultado. Cuando lee la tercera línea, tiene un 33% de posibilidades de convertirse en el resultado. La cuarta línea tiene un 25%, y así sucesivamente ....

import java.io.*; 
import java.util.*; 

public class B { 

    public static void main(String[] args) throws FileNotFoundException { 
    Map<String,Integer> map = new HashMap<String,Integer>(); 
    for(int i = 0; i < 1000; ++i) 
    { 
     String s = choose(new File("g:/temp/a.txt")); 
     if(!map.containsKey(s)) 
      map.put(s, 0); 
     map.put(s, map.get(s) + 1); 
    } 

    System.out.println(map); 
    } 

    public static String choose(File f) throws FileNotFoundException 
    { 
    String result = null; 
    Random rand = new Random(); 
    int n = 0; 
    for(Scanner sc = new Scanner(f); sc.hasNext();) 
    { 
     ++n; 
     String line = sc.nextLine(); 
     if(rand.nextInt(n) == 0) 
      result = line;   
    } 

    return result;  
    } 
} 

Answer 2

Use un BufferedReader y lea en línea. Utilice el objeto java.util.Random para detener al azar;)

Answer 3

O se

1. lee el archivo dos veces - una vez para contar el número de líneas, la segunda vez para extraer una línea al azar, o

2. uso reservoir sampling

Answer 4

Leer el archivo completo si solo desea una línea parece un poco excesivo. Lo siguiente debe ser más eficiente:

1. Utilice RandomAccessFile para buscar una posición de byte aleatorio en el archivo.
2. Busque a la izquierda y derecha en el siguiente terminador de línea. Deje L la línea entre ellos.
3. con probabilidad (MIN_LINE_LENGTH/L.length) RETURN L. De lo contrario, comenzar de nuevo en el paso 1.

Esta es una variante de rejection sampling.

Las longitudes de línea incluyen el (los) carácter (es) terminador (es) de línea, por lo tanto MIN_LINE_LENGTH> = 1. (Tanto mejor si conoce un límite más estricto en la longitud de línea).

Vale la pena señalar que el tiempo de ejecución de este algoritmo no depende del tamaño del archivo, solo en la longitud de línea, es decir, escala mucho mejor que la lectura del archivo completo.

Answer 5

Mirando la respuesta de Itay, parece que lee el archivo una y mil veces después de muestrear una línea del código, mientras que el muestreo del depósito real solo debería pasar por la 'cinta' una vez. He ideado un código para revisar el código una vez con muestreo de yacimiento real, basado en this y las diversas descripciones en la web.

import java.io.FileNotFoundException; 
import java.io.IOException; 
import java.util.List; 

public class reservoirSampling { 

    public static void main(String[] args) throws FileNotFoundException, IOException{ 
     Sampler mySampler = new Sampler(); 
     List<String> myList = mySampler.sampler(10); 
     for(int index = 0;index<myList.size();index++){ 
      System.out.println(myList.get(index)); 
     } 
    } 
} 

import java.io.File; 
import java.io.FileNotFoundException; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.List; 
import java.util.Random; 
import java.util.Scanner; 

public class Sampler { 

    public Sampler(){} 
    public List<String> sampler (int reservoirSize) throws FileNotFoundException, IOException 
    { 
     String currentLine=null; 
     //reservoirList is where our selected lines stored 
     List <String> reservoirList= new ArrayList<String>(reservoirSize); 
     // we will use this counter to count the current line number while iterating 
     int count=0; 

     Random ra = new Random(); 
     int randomNumber = 0; 
     Scanner sc = new Scanner(new File("Open_source.html")).useDelimiter("\n"); 
     while (sc.hasNext()) 
     { 
      currentLine = sc.next(); 
      count ++; 
      if (count<=reservoirSize) 
      { 
       reservoirList.add(currentLine); 
      } 
      else if ((randomNumber = (int) ra.nextInt(count))<reservoirSize) 
      { 
       reservoirList.set(randomNumber, currentLine); 
      } 
     } 
     return reservoirList; 
    } 
} 

La premisa básica es que llenar el depósito, y luego volver a la misma y rellenar líneas al azar con una probabilidad de 1/ReservoirSize. Espero que esto proporcione un código más eficiente. Por favor, avíseme si esto no funciona para usted, ya que literalmente lo detuve en media hora.