Java内存映射二分搜索

Question

Java内存映射二分搜索

javaniommap

4

我目前正在尝试找到在Java中搜索一个2GB二进制文件的最快方法。这与我的正常问题不同，因为该文件已经通过mmap映射到Linux文件系统中。

这个文件是一个二进制文件，我需要搜索它以查找一个固定的四字节字符串; AXL0。

通常，在较小的文件上，我会将其缓冲，转换为字符串，然后使用正则表达式进行匹配。但是，由于该文件已经被内存映射，并且非常大，重新缓冲它的想法似乎是错误的，而将其转换为2GB字符串似乎更加错误...

阅读一些资料后，我发现了Java NIO包以及FileChannels和MappedByteBuffers，但我不确定如何设置它们。

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

如果有人能提供一些建议或意见，我将非常感激。

谢谢。

- Tony

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - tonys

也许这可以帮助？http://codereview.stackexchange.com/questions/44021/fast-way-of-searching-for-a-string-in-a-text-file - Viktor Mellgren

1

这不是内存映射的工作方式。你可以基本上忘记文件被其他程序mmap了。只需使用缓冲读取器读取它，并逐部分查找您的模式。如果您想要更多信息，请联系我，我会尽力提供更长的答案。 - Fox

好的，你所说的“映射到文件系统”是什么意思？因为mmap的作用是相反的（将文件从文件系统映射到内存）。你使用哪个应用程序/命令来进行这种映射？ - Fox

我所指的是，在 /tmp/scanme 目录下存在一个二进制文件，这个文件是由另一个应用程序通过 mmap 创建的。它已经使得另一个应用程序的部分内存可用，并在 /tmp/scanme 中进行了映射。如果这样说能让您理解的话？ - Tony

显示剩余3条评论

1个回答

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

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

- Durandal · Accepted Answer

从抽象的角度看待这个任务，你无法比线性搜索更好地完成它。

因此，实际执行搜索时使用哪个API可能并不重要。为了简单起见，我会选择一个缓冲InputStream，它可以独立于实际数据源实现，并且没有固有限制，可以处理大于2GB的文件。

只要您选择合理的缓冲区大小（即不要太小），您应该可以获得合理的性能（接近实际I/O速度极限，除了可能需要较长时间扫描SSD之外）。

编辑：根据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?");
    }

}

虽然看起来非常低效，但你可能需要付出很大的努力才能将性能提高到一个显著的水平。