c++ - C++ のファイルから特定の単語をすばやく読み取る

Question

上司から、特定の単語がファイルに存在するかどうかをテストする必要があるテストを作成するように言われました。問題は、ファイルが非常に大きい可能性があり、テストが長時間実行されると、回帰テスト中に失敗することです。そのため、単語が存在するかどうかをすぐに教えてくれる、私の目的のために標準 C++ に便利な API があるかどうかを知りたいです。単語の場所を知りたくありません。この単語はファイルの先頭付近にありますが、正確な場所は不明です。この点で何か助けはありますか？ありがとうございました。

Answer 1

ファイルに (任意の順序で) 単語を含む以外に特定の構造がない場合、唯一の解決策は、ファイル全体を読み取ることを意味する線形検索です。単語が先頭近くにしかないことがわかっている場合は、その単語が見つかる最も遠い点まで検索するだけで済みます。

それが十分に速くない場合は、何らかの方法でファイルを構造化する (ソートするなど) か、読み取り手順自体を高速化する必要があります (例: を使用mmap)。

Answer 2

メモリ マップ ファイル アクセスを使用すると、ファイルをメモリにロードせずに、ファイルの一部に直接アクセスできます。

私の知る限り、Qt はメモリ マッピングを提供していますが、Boost も C++ 標準ライブラリにはありません。

OS のネイティブ API を使用することもできます。mmapUNIXCreateFileMapping用、Windows 用。

Answer 3

mmapファイルであり、strnstrおそらくそれが最適です。検索する必要がある領域を制限するファイルの構造について何か賢いことを知っていない限り.

extern "C" {
#include <sys/mman.h>
#include <fcntl.h>
}

#include <cstring>
#include <cerrno>
#include <iostream>

int main(int argc, char* argv[]) {

    // I don't check the arguments here, you should probably do that

    // String to search for
    char* search_string = argv[2];

    // Open the file so we can map it
    int fd = open(argv[1], O_RDONLY);
    if (fd < 0) {
        std::cout << "Open failed: " << strerror(errno) << std::endl;
        return 1;
    }

    // Find the length of the file so we know how much to map
    off_t len = lseek(fd, 0, SEEK_END);
    if (len == -1) {
        std::cout << "Seek failed: " << strerror(errno) << std::endl;
        return 1;
    }

    // map the file into memory
    char* file_contents = (char*)mmap(
        NULL, len, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, 0);
    if (file_contents == MAP_FAILED) {
        std::cout << "map failed: " << strerror(errno) << std::endl;
        return 1;
    }

    // We don't need the file open any more, we do need to unmap it later though
    close(fd);

    // Search for the string in the file here
    char* found = strnstr(file_contents, search_string, len);
    if (found == NULL)
        std::cout << "String not found" << std::endl;
    else
        std::cout << "String found @ " << found - file_contents << std::endl;

    munmap(file_contents, len);
}