c++ - 从文件中读取第 n 行的快速方法

Question

简介

我有一个名为 MyProcess 的 C++ 进程，我调用了 nbLines 次，其中 nbLines 是名为 InputDataFile.txt 在其中找到输入数据。例如调用

./MyProcess InputDataFile.txt 142

通知 MyProcess 输入数据位于 InputDataFile.txt 文件的 142 行。

问题

问题是 InputDataFile.txt 太大(~ 150 GB)以至于搜索正确行的时间不可忽略。启发形式this post ，这是我的(可能不是最优的)代码

int line = 142;
int N = line - 1;
std::ifstream inputDataFile(filename.c_str());
std::string inputData;
for(int i = 0; i < N; ++i)
    std::getline(inputDataFile, inputData);

std::getline(inputDataFile,inputData);

目标

我的目标是为 MyProcess 更快地搜索 inputData。

可能的解决方案

在 bash 中将每行的第一个字符的索引与行号匹配一次会很方便。这样，我就可以直接给出第一个感兴趣的字符的索引，而不是将 142 提供给 MyProcess。 MyProcess 可以直接跳转到这个位置，而无需搜索和计算 '\n' 字符。然后它将读取数据，直到遇到“\n”字符。这样的事情可行吗？如何实现？

当然，我欢迎任何其他可以减少导入这些输入数据的总体计算时间的解决方案。

Answer 1

正如其他答案中所建议的那样，构建文件的 map 可能是个好主意。我这样做的方式(伪代码)是:

let offset be a unsigned 64 bit int =0;

for each line in the file 
    read the line
    write offset to a binary file (as 8 bytes rather as chars)
    offset += length of line in bytes

现在您有一个“ map ”文件，它是一个 64 位整数列表(文件中的每一行一个)。要阅读 map ，您只需计算您想要的线路条目在 map 中的位置:

offset = desired_line_number * 8 // where line number starts at 0
offset2 = (desired_line_number+1) * 8

data_position1 = load bytes [offset through offset + 8] as a 64bit int from map
data_position2 = load bytes [offset2 through offset2 + 8] as a 64bit int from map

data = load bytes[data_position1 through data_position2-1] as a string from data.

这个想法是，您读取一次数据文件并在文件中每行开始的位置记录字节偏移量，然后使用固定大小的整数类型将偏移量顺序存储在二进制文件中。映射文件的大小应为 number_of_lines * sizeof(integer_type_used)。然后，您只需通过计算存储行号偏移量的偏移量并读取该偏移量以及下一行偏移量来查找 map 文件。从那里你有一个数字范围，以字节为单位，说明你的数据应该位于何处。

例子:

数据:

hello\n 
world\n
(\n newline at end of file)

创建 map 。

Map:每个分组[number]代表文件中的一个8字节长度

[0][7][14]
//or in binary
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00001110

现在说我想要第 2 行:

line offset = 2-1 * 8 // offset is 8 

因此，由于我们使用的是基数为 0 的系统，因此它是文件中的第 9 个字节。所以输出数字由字节 9 - 17 组成，它们是:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000111
//or as decimal
7

现在我们知道 out 行应该从数据文件中的偏移量 7 开始(这个偏移量以 1 为底，如果我们从 0 开始计数，它就是 6)。

然后我们执行相同的过程以获得下一行的起始偏移量，即 14。

最后我们查找字节范围 7-14(基数 1、6-13 基数 0)并将其存储为字符串并获取 world\n。

C++ 实现:

#include <iostream>
#include <fstream>

int main(int argc, const char * argv[]) {
    std::string filename = "path/to/input.txt";

    std::ifstream inputFile(filename.c_str(),std::ios::binary);
    std::ofstream outfile("path/to/map/file.bin",std::ios::binary|std::ios::ate);

    if (!inputFile.is_open() || !outfile.is_open()) {
        //use better error handling than this
        throw std::runtime_error("Error opening files");
    }


    std::string inputData;
    std::size_t offset = 0;
    while(std::getline(inputFile, inputData)){
        //write the offset as binary
        outfile.write((const char*)&offset, sizeof(offset));
        //increment the counter
        offset+=inputData.length()+2;
        //add one becuase getline strips the \n and add one to make the index represent the next line
    }
    outfile.close();

    offset=0;

    //from here on we are reading the map
    std::ifstream inmap("/Users/alexanderzywicki/Documents/xcode/textsearch/textsearch/map",std::ios::binary);
    std::size_t line = 2;//your chosen line number
    std::size_t idx = (line-1) * sizeof(offset); //the calculated offset
    //seek into the map
    inmap.seekg(idx);
    //read the binary at that location
    inmap.read((char*)&offset, sizeof(offset));
    std::cout<<offset<<std::endl;

    //from here you just need to lookup from the data file in the same manor


    return 0;
}