Как получить случайную строку текстового файла в Java?

Question

Скажите, что файл слишком большой, чтобы его можно было поместить в память. Как я могу получить от него случайную строку? Благодарю.

Обновление: Я хочу, чтобы вероятность получения каждой линии была равной.

Answer 1

Вот решение. Взгляните на метод select(), который делает реальную вещь (метод main() неоднократно выполняет функцию choose(), чтобы показать, что распределение действительно довольно однородно).

Идея проста: когда вы читаете первую строчку, у нее есть 100% шанс быть выбранным в качестве результата. Когда вы читаете вторую строчку, у нее есть 50% шанс заменить первую строку в качестве результата. Когда вы читаете 3-ю строчку, у нее есть 33% шанс стать результатом. Четвертая строка имеет 25% и т. Д.

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

Используйте BufferedReader и прочитайте строку мудрым. Используйте объект java.util.Random, чтобы остановить случайным образом;)

Answer 3

Либо вы

1. читать файл дважды - один раз, чтобы подсчитать количество строк, во второй раз, чтобы извлечь случайную строку или

2. использование reservoir sampling

Answer 4

Чтение всего файла, если вы хотите, чтобы только одна строка выглядела несколько чрезмерно. Следующие должны быть более эффективными:

1. Используйте RandomAccessFile для поиска случайной позиции байта в файле.
2. Ищите влево и вправо до следующего терминатора линии. Пусть L - прямая между ними.
3. С вероятностью (MIN_LINE_LENGTH/L.length) возвращают L. В противном случае, начать все сначала на шаге 1.

Это вариант rejection sampling.

Длина линии включает символ окончания строки, поэтому MIN_LINE_LENGTH> = 1. (Все лучше, если вы знаете более жесткую привязку длины строки).

Следует отметить, что время выполнения этого алгоритма не зависит от размера файла, а только от длины строки, то есть оно масштабируется намного лучше, чем чтение всего файла.

Answer 5

Оглядываясь на ответ Итай, он выглядит так, как будто он читает файл тысячу раз после отбора одной строки кода, тогда как истинная выборка коллектора должна проходить только по «ленте» один раз. Я разработал некоторый код для перебора кода один раз с реальной выборкой коллектора на основе this и различных описаний в Интернете.

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

Основной предпосылкой является то, что вы заполните резервуар, а затем вернуться к нему и заполнить случайных линий с шансом 1/ReservoirSize. Надеюсь, это обеспечит более эффективный код. Пожалуйста, дайте мне знать, если это не сработает для вас, поскольку я буквально сбил его через полчаса.