Java 内存映射二分查找

Question

我目前正在尝试找到在 java 内搜索 2GB 二进制文件的最快方法。这与我的正常问题不同，因为此文件已经使用 mmap.

内存映射到 Linux 文件系统中

问题文件是一个二进制文件，我需要在其中搜索一个固定的四字节字符串； AXL0

通常，对于较小的文件，我只是对其进行缓冲，将其转换为字符串，然后对其进行正则表达式。然而，由于这个文件已经是内存映射的，而且相当大，重新缓冲的想法似乎是错误的，并且将其转换为 2GB 的字符串似乎更错误...

经过一些阅读，我遇到了 Java NIO 包以及 FileChannels 和 MappedByteBuffers，但我不完全确定如何设置他们起来。

我只需要扫描文件，从零到文件中的最后一个字节并找到四字节字符串的每个实例。

如果有人可以提供一些建议或意见，我将不胜感激。

谢谢。

Answer 1

抽象地看任务，没有比线性搜索更好的了。

从这里开始，您使用哪个 API 来实际执行搜索可能并不重要，为简单起见，我将简单地使用缓冲的 InputStream，它可以在与实际数据源无关的情况下实现并且没有阻止它处理大于 2GB 的文件的固有限制。

只要您选择合理的缓冲区大小（阅读：不要太小），您应该获得合理的性能（接近实际 I/O 速度限制，SSD 可能除外，因为您的扫描可能在这种情况下比实际 I/O 花费的时间更长。

编辑：在 KISS 之后，您会得到几行代码，应该可以正常工作

public class ScanForByteCombo {

    public static List<Long> scanFor(InputStream is, int needle) throws IOException {
        List<Long> foundOffsets = new ArrayList<>();
        InputStream bs = new BufferedInputStream(is, 0x10000);
        int data = 0;
        int b;
        long offset = 0;
        while ((b = bs.read()) != -1) {
            data = (data << 8) | b;
            if (data == needle) 
                foundOffsets.add(offset);
            ++offset;
        }
        return foundOffsets;
    }

    public static void main(String[] argv) {

        int needle = ('A' << 24) | ('X' << 16) | ('F' << 8) | '0';

        long start = System.currentTimeMillis();
        try (InputStream is = new FileInputStream("your file")) {
            List<Long> found = scanFor(is, needle);
            System.out.println(found);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println("scan took " + (System.currentTimeMillis() - start) + "ms. Acceptable?");
    }

}

虽然它看起来效率很低，但您可能需要竭尽全力才能将性能实际提高显着。

Java 内存映射二分查找

Java memory mapped binary search

java

nio

mmap