如何高效地倒序读取文件以查找子字符串

Question

我有一个类似这样结构的大型日志文件：

"时间戳": {"标识符":值}

"1463403600":{"AA":74.42},
"1463403601":{"AA":29.55},
"1463403603":{"AA":24.78},
"1463403604":{"AA":8.46},
"1463403605":{"AA":44.84},
"1463403607":{"AA":87.05},
"1463403608":{"AA":54.81},
"1463403609":{"AA":93.1},
"1463403611":{"AA":77.64},
"1463403612":{"AA":33.39},
"1463403613":{"AA":69.2},

我想提取给定时间戳后的内容，例如：

std::ifstream * myfunc( uint32_t timestamp) 

示例：

myfunc(1463403611);
/* returns
"1463403611":{"AA":77.64},
"1463403612":{"AA":33.39},
"1463403613":{"AA":69.2},
*/

日志文件太长了，无法在内存中保存。代码将在资源受限的嵌入式设备上运行（80Mhz，约10kB可用内存），因此我正在寻找一些有效解决方案。

日志文件可能有500k+条记录，在99％的情况下，时间戳将在最后100行中，因此从文件开头开始检查每一行以获取正确的时间戳将非常低效。

所以我想要的是一种逐行向后读取文件的解决方案。我没有真正的解决方案，如何在不加载大块内存的情况下高效地实现这一点。

我尝试了从EOF开始读取200字节的块，但面临的问题是，该块在许多情况下将时间戳分成两半。我尝试检测并重新选择一些字节（如果需要），但感觉必须有更聪明的解决方案。

- Res ulma

---

1. 通过文件创建时间戳、文件最后修改时间戳以及每天的时间戳数量，您可以大致估算偏移量，然后通过读取进行调整。
2. 通过“99%的时间……”，应该很容易近似计算出起始偏移量。

- Jean-Baptiste Yunès

你可以使用一种针对文件末尾的二分搜索算法来查找记录。 - Galik

你不需要读取大块内容，缓冲区只需比最长可能的行长两倍稍微大一点即可。在你的例子中，这些行似乎总是相当小的；一个64字节的缓冲区可能就足够了。 - Fabio Ceconello

每 1,000 行或每小时滚动一次日志，这样每个日志文件就不会太多。 - Mark Setchell

你能让数据生成者将行设置为固定宽度（必要时通过填充实现）吗？这将大大加快文件访问速度，您可以使用基于内存的算法，例如二进制搜索。 - Thomas Matthews

Answer 1

我发现这个想法很有趣，所以我做了一个二分搜索的概念验证。

这个程序测试不够充分，可能会有一些错误，但目前看起来还是能够工作的，并且演示了分治的思想。你在文件的中间检查，根据是否太高或太低，将数据分成两部分并搜索相关的一半。你递归地重复执行这个过程，直到你接近目标。

#include <ctime>
#include <cmath>
#include <cstdlib>
#include <string>
#include <fstream>
#include <iostream>

// Don't use this, its just to show how many reads
// are being done to find the record.
int global_counter;

std::streampos find_stamp(std::istream& is, long stamp, std::streampos pos, std::streampos end)
{
    ++global_counter;

    if(pos == 0) // can't divide zero
        return 0;

    std::string s;
    long found_stamp;

    // extract nearest timestamp after pos
    is.seekg(pos);
    if(!(std::getline(std::getline(is, s, ','), s, '"') >> found_stamp))
        return end;

    // if its too big check first half of this region
    if(found_stamp > stamp)
        return find_stamp(is, stamp, pos / 2, pos);

    // if its not within 10 timestamp seconds check end half of this region
    if(stamp - found_stamp > 10)
        return find_stamp(is, stamp, (pos + end) / 2, end);

    // read record by record (prolly more efficient than skipping)
    pos = is.tellg();
    while(std::getline(std::getline(is, s, ','), s, '"') >> found_stamp)
    {
        if(found_stamp > stamp)
            return pos;
        pos = is.tellg();
    }
    return end;
}

void print_after(const std::string& filename, long stamp)
{
    // open at end of file (to get length)
    std::ifstream ifs(filename, std::ios::ate);

    std::streampos end = ifs.tellg();
    auto pos = end / 2; // start checking in middle

    // find position before required record
    // (may be in the middle of a record)
    if((pos = find_stamp(ifs, stamp, pos, end)) != end)
    {
        ifs.seekg(pos);

        std::string line;
        std::getline(ifs, line, ','); // skip to next whole record

        // print out all following recors
        while(std::getline(ifs, line, ','))
            std::cout << line;
    }
}

inline
std::string leading_zeros(int n, int zeros = 2)
{
    std::string s;
    for(int z = std::pow(10, zeros - 1); z; z /= 10)
        s += (n < z ? "0":"");
    return s + std::to_string(n);
}

int main()
{
    std::srand(std::time(0));

    // generate some test data
    std::ofstream ofs("test.txt");

    for(int i = 0; i < 1000; ++i)
    {
        ofs << '"' << leading_zeros(i, 10) << '"';
        ofs << ":{\"AA\":" << (std::rand() % 100);
        ofs << '.' << (std::rand() % 100) << "},\n";
    }

    ofs.close();

    global_counter = 0;
    print_after("test.txt", 993);

    std::cout << "find checked " << global_counter << " places in the file\n";
}

输出：

"0000000994":{"AA":80.6}
"0000000995":{"AA":11.90}
"0000000996":{"AA":16.43}
"0000000997":{"AA":53.11}
"0000000998":{"AA":68.43}
"0000000999":{"AA":79.77}
find checked 6 places in the file

- Galik

---

超过500,000条记录，99%的时间戳将在最后100行中。通过从末尾开始搜索而不是中间开始，可以进一步改善此情况。这样可以减少对99%的检查次数。（并且，根据系统的缓存设计，还可以减少缓存未命中） - Daniel Jour

Answer 2

由于您使用的是嵌入式设备，可能无法使用 mmap()，因此我认为唯一可行的方法是使用缓冲区填充文件的一部分，以便能够逐个块地检查其内容。请注意，您需要重叠缓冲区窗口，以避免错过被缓冲区开头截断的行。您需要在块的开头寻找第一个换行符，并将其与之前的任何内容一起丢弃，然后才能开始检查时间戳。在缓冲区开头丢弃部分行还有助于在将上一个块加载到缓冲区时将该行的末尾与缓冲区的末尾对齐。

处理缓冲区开头的不完整行使这成为一种非常丑陋和容易出错的方法。这就是为什么我建议如果可能的话使用 mmap()，它可以让您忽略这些问题的原因。

- cmaster - reinstate monica

---

我想二分查找和分块的结合可能会有良好的性能。我会尝试一下（感谢@Galik提供的二分查找提示）我刚听说mmap-会进行调查。 - Res ulma

@Resulma：特别是，如果99%的时间结果在最后100行中，那么请尽量将您的块大小增加到至少是典型行长度的100倍（因此为2700个字节或更多），以便99%的时间您只需要执行一次查找和读取操作。 - Steve Jessop

Answer 3

如果性能不是问题，您可以逐行读取整个文件直到达到所请求的时间，然后开始转储。没有必要将整个文件读入内存。如果性能是一个问题，可以在文件的一半处进行查找，检查时间戳，然后以二分搜索方式再次将其除以二。

- Felice Pollano