在Java中的已排序(内存映射？)文件中进行二进制搜索

Question

我正在努力将Perl程序移植到Java,并且随时学习Java.原始程序的核心组件是Perl模块,它使用二进制搜索在+500 GB排序文本文件中执行字符串前缀查找(实质上,"搜索"到文件中间的字节偏移,回溯到最近的换行,比较带有搜索字符串的行前缀,"seek"到那个字节偏移的一半/两倍,重复直到找到...)

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

或者,我不熟悉新的(？)Java I/O库,但它是一个内存映射500 GB文本文件的选项(我在64位机器上,内存备用)并做二进制文件搜索内存映射的字节数组？我很想知道你必须分享的关于这个和类似问题的任何经验.

Answer 1

我是一个很大的 Java的风扇MappedByteBuffers像这样的情况.它非常快.下面是我为你准备的一个片段,它将缓冲区映射到文件,向中间搜索,然后向后搜索换行符.这应该足以让你去？

我在自己的应用程序中有类似的代码(搜索,读取,重复直到完成),在生产环境中java.io对基准 流进行反对MappedByteBuffer,并将结果发布到我的博客(Geekomatic帖子标记为'java.nio')上,包含原始数据,图表和所有内容.

两个第二个总结？ 基于My MappedByteBuffer的实现速度提高了约275%. 因人而异.

为大于~2GB的文件工作,这是一个问题因为演员而且.position(int pos),我制作了由MappedByteBuffers 数组支持的分页算法.您需要在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);
    }
}