java - Java中排序(内存映射？)文件中的二进制搜索

Question

我正在努力将 Perl 程序移植到 Java，并在学习过程中学习 Java。原始程序的核心组件是 Perl module使用二进制搜索在 +500 GB 排序的文本文件中进行字符串前缀查找(本质上，“寻找”到文件中间的字节偏移，回溯到最近的换行符，将行前缀与搜索字符串进行比较，“寻找”到该字节偏移的一半/两倍，重复直到找到......)

我已经尝试了几种数据库解决方案，但发现对于这种大小的数据集，在绝对查找速度方面没有什么能比这更好的了。您知道任何现有的实现此类功能的 Java 库吗？如果做不到这一点，您能否指出一些在文本文件中进行随机访问读取的惯用示例代码？

另外，我不熟悉新的(？)Java I/O 库，但它是否可以选择对 500 GB 文本文件进行内存映射(我在 64 位机器上，有可用内存)并在内存映射字节数组上进行二进制搜索？我很想听听您分享有关此问题和类似问题的任何经验。

Answer 1

我是 Java MappedByteBuffers 的 大 粉丝 对于这种情况。它燃烧得很快。下面是我为您整理的一个片段，它将缓冲区映射到文件，寻找到中间，然后向后搜索到换行符。这应该足以让您继续前进？

我在自己的应用程序中有类似的代码(查找、阅读、重复直到完成)，经过基准测试java.io 在生产环境中针对 MappedByteBuffer 进行流式传输，并在我的博客 (Geekomatic posts tagged 'java.nio') 上发布结果以及原始数据、图表和所有内容。

两秒总结？ 我的基于 MappedByteBuffer 的实现快了大约 275%。 YMMV。

为了处理大于 ~2GB 的文件，这是由于 Actor 阵容和 .position(int pos) 造成的问题，我制作了由 MappedByteBuffer 数组支持的分页算法s。您需要在 64 位系统上工作才能处理大于 2-4GB 的文件，因为 MBB 使用操作系统的虚拟内存系统来发挥它们的魔力。

public class StusMagicLargeFileReader  {
    private static final long PAGE_SIZE = Integer.MAX_VALUE;
    private List<MappedByteBuffer> buffers = new ArrayList<MappedByteBuffer>();
    private final byte raw[] = new byte[1];

    public static void main(String[] args) throws IOException {
        File file = new File("/Users/stu/test.txt");
        FileChannel fc = (new FileInputStream(file)).getChannel(); 
        StusMagicLargeFileReader buffer = new StusMagicLargeFileReader(fc);
        long position = file.length() / 2;
        String candidate = buffer.getString(position--);
        while (position >=0 && !candidate.equals('\n')) 
            candidate = buffer.getString(position--);
        //have newline position or start of file...do other stuff    
    }
    StusMagicLargeFileReader(FileChannel channel) throws IOException {
        long start = 0, length = 0;
        for (long index = 0; start + length < channel.size(); index++) {
            if ((channel.size() / PAGE_SIZE) == index)
                length = (channel.size() - index *  PAGE_SIZE) ;
            else
                length = PAGE_SIZE;
            start = index * PAGE_SIZE;
            buffers.add(index, channel.map(READ_ONLY, start, length));
        }    
    }
    public String getString(long bytePosition) {
        int page  = (int) (bytePosition / PAGE_SIZE);
        int index = (int) (bytePosition % PAGE_SIZE);
        raw[0] = buffers.get(page).get(index);
        return new String(raw);
    }
}