如何高效处理大型文本文件？

Question

如何高效处理大型文本文件？

javafile-iotext-files

4

我有两个文件：
1- 有1400000行或记录 --- 14 MB
2- 有16000000 -- 170 MB的行或记录

我想查找文件1中的每个记录或行是否也在文件2中

我开发了一个Java应用程序，它执行以下操作：逐行读取文件，并将每行传递给遍历文件2的方法

这是我的代码：

public boolean hasIDin(String bioid) throws Exception {

    BufferedReader br = new BufferedReader(new FileReader("C://AllIDs.txt"));
    long bid = Long.parseLong(bioid);
    String thisLine;
    while((thisLine = br.readLine( )) != null)
    {
         if (Long.parseLong(thisLine) == bid)
            return true;

    }
        return false;
    }

public void getMBD() throws Exception{

     BufferedReader br = new BufferedReader(new FileReader("C://DIDs.txt"));
     OutputStream os = new FileOutputStream("C://MBD.txt");
     PrintWriter pr = new PrintWriter(os);
     String thisLine;
     int count=1;
     while ((thisLine = br.readLine( )) != null){
         String bioid = thisLine;
         System.out.println(count);
         if(! hasIDin(bioid))
                pr.println(bioid);
     count++;
     }
    pr.close();
}

当我运行它时，似乎需要超过1944.44444444444小时才能完成，因为每行处理需要5秒钟。大约需要三个月的时间！

是否有任何想法可以在更少的时间内完成。

提前致谢。

- Abu Muhammad

1

也许你可以把完成时间的估计值四舍五入一下。 ;) - Peter Lawrey

1

不要忘记关闭你的文件句柄 :) - dogbane

如果你在*nix上，你可以执行shell命令行"sort <file1> <file2> <file2> | uniq -u > <outputfile>" :) - patros

4个回答

4

170Mb + 14Mb并不是非常大的文件。

我的建议是将较小的文件加载到java.util.Map中，逐行（逐条记录）解析最大的文件，并检查当前行是否存在于该Map中。

P.S. 这个问题在关系型数据库方面似乎很琐碎 - 或许值得使用任何一个？

- Vadim

3

顺便提一下，关系型数据库管理系统（RDBMS）可以有效地做到你（和其他人）建议的事情。它被称为“哈希连接”。 - Michael Borgwardt

1

是的，但是那个解决方案需要：1安装数据库，2创建模式，3填充模式，4编写查询。将其重写为非N平方循环应该只需要15分钟。 - John Gardner

同意John的观点 - 对于简单的任务需要太多的操作（特别是如果这只需要做一次）。但我不确定是否可能实现比O(N)复杂度更低的方案，因为常规Map实现具有O(1)复杂度，而我们总共需要执行N个此类操作。 - Vadim

如果你只需要判断“它是否在文件中”，而不是行号或其他什么，你也可以使用Set<long>而不是map。 - John Gardner

2

如果每次迭代的时间非常长，那么你不能使用O(N^2)，这完全是不可接受的。如果你有足够的RAM，可以解析文件1，创建所有数字的映射，然后解析文件2并检查映射表。如果你没有足够的RAM，可以解析文件1，创建一个映射并将其存储到文件中，然后解析文件2并读取映射表。关键是要使映射表易于解析-使其成为二进制格式，可能带有二进制树或其他可以快速跳过和搜索的内容。(编辑：我必须添加Michael Borgwardt的Grace Hash Join链接，它展示了一种更好的方法：http://en.wikipedia.org/wiki/Hash_join#Grace_hash_join)如果你的文件大小有限，则选项1更容易实现-除非你处理的是大量GB的巨大文件，否则你肯定想这样做。

- EboMike

1

当你无法将一个文件/表保存在内存中时，有一种更好的方法来处理它：http://en.wikipedia.org/wiki/Hash_join#Grace_hash_join - Michael Borgwardt

1

通常，内存映射是读取大文件最有效的方法。您需要使用java.nio.MappedByteBuffer和java.io.RandomAccessFile。

但是，您的搜索算法才是真正的问题。建立某种索引或哈希表是您所需要的。

- OrangeDog

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Lawrey · Accepted Answer

为什么不把file2中的所有行读入一个集合中？使用集合是可行的，但使用TLongHashSet会更加高效。

对于第二个文件中的每一行，检查它是否在该集合中。

这里提供了一个经过优化的实现版本，并且只使用了小于64MB的内存。

Generating 1400000 ids to /tmp/DID.txt
Generating 16000000 ids to /tmp/AllIDs.txt
Reading ids in /tmp/DID.txt
Reading ids in /tmp/AllIDs.txt
Took 8794 ms to find 294330 valid ids

代码

public static void main(String... args) throws IOException {
    generateFile("/tmp/DID.txt", 1400000);
    generateFile("/tmp/AllIDs.txt", 16000000);

    long start = System.currentTimeMillis();
    TLongHashSet did = readLongs("/tmp/DID.txt");
    TLongHashSet validIDS = readLongsUnion("/tmp/AllIDs.txt",did);

    long time = System.currentTimeMillis() - start;
    System.out.println("Took "+ time+" ms to find "+ validIDS.size()+" valid ids");
}

private static TLongHashSet readLongs(String filename) throws IOException {
    System.out.println("Reading ids in "+filename);
    BufferedReader br = new BufferedReader(new FileReader(filename), 128*1024);
    TLongHashSet ids = new TLongHashSet();
    for(String line; (line = br.readLine())!=null;)
        ids.add(Long.parseLong(line));
    br.close();
    return ids;
}

private static TLongHashSet readLongsUnion(String filename, TLongHashSet validSet) throws IOException {
    System.out.println("Reading ids in "+filename);
    BufferedReader br = new BufferedReader(new FileReader(filename), 128*1024);
    TLongHashSet ids = new TLongHashSet();
    for(String line; (line = br.readLine())!=null;) {
        long val = Long.parseLong(line);
        if (validSet.contains(val))
            ids.add(val);
    }
    br.close();
    return ids;
}

private static void generateFile(String filename, int number) throws IOException {
    System.out.println("Generating "+number+" ids to "+filename);
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(filename), 128*1024));
    Random rand = new Random();
    for(int i=0;i<number;i++)
        pw.println(rand.nextInt(1<<26));
    pw.close();
}