我在这种结构中有一个巨大的日志文件:
“ timestamp”:{“ identifier”:value}
"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的空闲内存)上运行,因此Im正在寻找有效解决方案的一些想法。
日志文件可能具有500k +条目,并且在99%的时间中,时间戳将位于最后100行中,因此从文件的beginnig开始并检查每一行以获取正确的时间戳将非常低效。
所以我想我正在寻找一种解决方案,可以逐行向后读取文件。我真的没有解决方案,如何高效地做到这一点,而又无需将大块数据加载到内存中。
我尝试从EOF开始读取200字节的数据块,但是遇到了这个问题,在很多情况下,数据块将时间戳减少了一半。我尝试检测到该错误,并在需要时重新选择一些字节,但感觉到必须有一个明智的解决方案。
好吧,我发现这种有趣的东西,所以我为二元搜索的想法敲了一个概念证明。
这没有经过很好的测试,可能有点小问题,但到目前为止似乎仍然有效,并展示了“分而治之”的思想。您检查文件的中间位置,然后根据数据的高低将数据分为两部分,然后搜索相关的一半。您可以递归地进行操作,直到足够接近为止。
#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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句