如何在Java中从文本文件中获取随机一行？

Question

假设有一个文件太大而无法放入内存，那么我该如何从中获取一行随机数据？谢谢。

更新： 我希望各行被选中的概率相等。

- Fluffy

Answer 1

如果您只想获取一行内容，读取整个文件似乎有点过度了。以下方法应该更有效:

1. 使用RandomAccessFile寻找文件中的随机字节位置。
2. 向左和向右搜索下一个行终止符。令L为它们之间的行。
3. 以概率(MIN_LINE_LENGTH / L.length)返回L。否则，请重新从步骤1开始。

这是拒绝抽样的一种变体。

行长度包括行终止字符，因此MIN_LINE_LENGTH >= 1。(如果您知道行长度的更紧密限制，那就更好了)。

值得注意的是，这个算法的运行时间不取决于文件大小，只取决于行长度，即它比读取整个文件的效率要高出很多。

- meriton

---

太好了！如果文件将被重复采样，请使用单次通过收集偏移量的 List<Integer>，然后可以通过 Collections.shuffle() 进行随机化。 - trashgod

这应该是最好的答案。 - akuz

Answer 2

这里有一个解决方案。看一下choose()方法，它执行了真正的操作（main()方法反复运行choose()方法，以显示分布确实非常均匀）。

思路很简单：当你读第一行时，它被选为结果的概率为100%。当你读第二行时，它有50%的几率替换第一行成为结果。当你读第三行时，它有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;      
  }
}

- Itay Maman

---

水塘抽样的一种实现方式。 - Will

太神奇了，从未听说过蓄水池抽样。如果我的文件有几MB呢？会有性能问题吗？如果有的话，是否有其他替代方案可以避免完全扫描文件？ - lorenzo-s

我是否正确地假设这是针对一个固定的n=1，其中n是“样本”的数量？有没有办法一次选择多个？目前情况下，您会多次“循环遍历磁带”，或者至少在尝试中如此，这似乎效率低下。 - AncientSwordRage

Answer 3

你可以采用以下两种方法从文件中随机抽取一行：

1. 读取文件两次——第一次计算行数，第二次抽取随机行；或者

2. 使用蓄水池抽样算法。

- Will

Answer 4

看了Itay的答案，似乎在抽取一行代码后，读取文件的次数达到了一千次之多，而真正的蓄水池采样应该只需要遍历“带子”一次。我已经设计出了一些代码，使用真正的蓄水池采样方法，只需要一次遍历即可。这个方法基于这个链接和网上的各种描述。

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/水库大小的概率填写行。我希望这样能提供更高效的代码。如果这在您那里不起作用，请告诉我，因为我只花了半小时就完成了。

- AncientSwordRage

---

我已经将这个程序放在审核中。 - AncientSwordRage

Answer 5

使用 RandomAccessFile：

1. 构造一个 RandomAccessFile，名为 file
2. 通过调用 file.length() 获取文件长度 filelen
3. 生成一个介于 0 和 filelen 之间的随机数 pos
4. 调用 file.seek(pos) 将指针定位到随机位置
5. 调用 file.readLine() 定位到当前行的末尾
6. 再次调用 file.readLine() 读取下一行

使用这种方法，我已经可以在几秒钟内从随机选择的文件中随机取样 Brown Corpus 中的行，并轻松检索 1000 个随机样本。如果我尝试通过逐行阅读每个文件来完成相同的操作，那么需要更长的时间。

选择列表中的随机元素时可以使用相同的原理。与其逐行阅读列表并在随机位置停止，不如生成介于 0 和列表长度之间的随机数，然后直接索引列表。

- NBCurrieLL

Answer 6

在Java中从文件中读取随机行：

public String getRandomLineFromTheFile(String filePathWithFileName) throws Exception {

        File file = new File(filePathWithFileName); 
        final RandomAccessFile f = new RandomAccessFile(file, "r");
        final long randomLocation = (long) (Math.random() * f.length());
        f.seek(randomLocation);
        f.readLine();
        String randomLine = f.readLine();
        f.close();
        return randomLine;
    }

- Shiv Yadav

Answer 7

使用 BufferedReader 逐行读取。使用 java.util.Random 对象随机停止 ;)

- ZeissS

---

如何确保在我想停止时文件不会过大？也就是说，如何知道文件有多少行？ - Fluffy

另外，我希望每一行的概率相等。 - Fluffy

@Dinuk，如果文件比其他文件小，那么我会经常得到最后一行，如果文件较大，则很少得到它。 - Fluffy

然后您需要两次读取文件，或者如果所有行的长度相等，您可以从文件大小计算行数。 - ZeissS