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

Question

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

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

Answer 1

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

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

Это вариант выборка отклонения .

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

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

Answer 2

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

Идея проста: когда вы читаете первую строку, у вас есть 100% шанс быть выбранным в результате. Когда вы читаете 2-ю строку, у вас есть 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 3

Либо ты

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

2. использование отбор проб из резервуара

Answer 4

Если посмотреть на ответ Итая, похоже, что он читает файл тысячу раз после выборки одной строки кода, тогда как истинная выборка из резервуара должна проходить через «ленту» только один раз. Я разработал некоторый код для однократного прохождения кода с реальной выборкой из пласта, основываясь на 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. Я надеюсь, что это обеспечивает более эффективный код. Пожалуйста, дайте мне знать, если это не сработает для вас, потому что я буквально выбил его за полчаса.

Answer 5

Использовать RandomAccessFile :

1. Создание RandomAccessFile , файла
2. Получите длину этого файла, filelen , вызвав file.length ()
3. Генерирует случайное число, pos , между 0 и filelen
4. Вызовите file.seek (pos) для поиска случайной позиции
5. Вызовите file.readLine () , чтобы добраться до конца текущей строки
6. Прочитайте следующую строку, вызвав file.readLine () снова

Используя этот метод, я выбирал случайные строки из «Коричневого корпуса» и могу легко извлечь 1000 случайных выборок из случайно выбранных файлов за несколько секунд. Если бы я попытался сделать то же самое, прочитав каждый файл построчно, это заняло бы у меня намного больше времени.

Тот же принцип можно использовать для выбора случайных элементов из списка. Вместо того, чтобы читать список и останавливаться в произвольном месте, если вы генерируете случайное число в диапазоне от 0 до длины списка, вы можете напрямую внести в список индекс.

Answer 6

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