在输入流中搜索字符串

Question

我有一个很大的二进制文件（很多千兆字节，所以无法将其加载到内存中），我想搜索所有出现的字符串 "icpf".

我尝试为此使用 std::search，但被 std::search 仅适用于前向迭代器而不适用于输入迭代器这一事实所困扰。

标准库是否为此提供了快速替代方案？或者我是否需要手动编写搜索代码（要么一次读取块，然后 std::search ，要么 ignore 所有内容直到 'i' 然后手动检查接下来的三个字符）？

Answer 1

最快的方法是将整个文件加载到内存中，然后搜索内存。

下一个最佳选择是让硬盘保持运转。也许有一个线程将数据块读入缓冲区，另一个线程搜索缓冲区。

沿着列表往下看，将大块数据读入缓冲区，然后搜索缓冲区是一种很好的技术，尽管效率不如以前的方法。

您可以使用 std::getline 和 std::string 逐行阅读。这不如块读取快，因为输入函数正在搜索换行符（并在 std::string 中分配内存）。

最坏的情况可能是一个字一个字地读。函数开销不利于读取单个字符（通常读取大块数据的开销相同）。

不，没有用于搜索文件的标准 C++ 库函数。某些操作系统具有用于搜索文件的实用程序；也许你可以使用其中之一。

编辑 1：
瓶颈是输入数据。一旦将数据放入缓冲区，就会有许多有效的搜索算法而不是蛮力（搜索第一个字母，然后搜索下一个字母，等等）。

在互联网上搜索 "string search algorithm"。

Answer 2

Does the standard library provide a fast alternative for this?

尽管标准 C++ 库提供了搜索文本流的方法，但它不提供可比较的二进制流算法。

Or do I need to hand-code the search (either reading in chunks at a time then std::search on those, or ignore everything until an 'i' and then manually check the next three characters)?

编码 "skip and search" 方法可能很棘手，因为编写跳过条目的解决方案很容易。例如，如果您在包含 "icpicpf" 的文件中查找 "icpf"，一次处理一个字符的简单程序将无法在丢弃 "icpi" 后找到 "icpf" 后缀前缀。

如果您要自己编写代码，请考虑实施 Knuth–Morris–Pratt algorithm。网上有很多实现，它在流上运行正确，因为它一次只考虑一个字符，永远不会返回。

Answer 3

我不知道任何纯标准库的解决方案，但是内核已经实现了预取，所以应该可以mmap()文件来获得所需的前向迭代器：（省略错误处理）

size_t search(int fd, size_t fileSize) {
    auto start = reinterpret_cast<char*>(
        ::mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0));
    ::madvise(start, fileSize, MADV_SEQUENTIAL);
    auto pattern = "icpf";
    auto offset = std::search(start, start+fileSize, pattern, pattern+4);
    return offset - start;
}

这是一个小小的信仰飞跃，相信你的内核会正确地进行延迟加载、预取和丢弃。另一方面，如果您可以信任任何人，那可能是内核开发人员。

免责声明：我实际上并没有在数 GB 的文件上对此进行测试。

在输入流中搜索字符串

Searching for a string in an input stream

c++

iostream