在c++优化中合并大型二进制文件
背景:我已经编写了一个修改过的adler32校验和例程，它可以生成64位校验和。我想检查大小写字母、数字和_区域中的冲突。我已经写了一个生成器程序，它遍历这个范围内的所有字符串组合，直到给定的最大长度。它具有大小高达4G的已排序二进制文件的输出，以及校验和的结果。4G的限制是由于内存大小，尽管文件越大意味着文件越少，这就大大加快了合并和检查的速度。最多6字节字符串的总数据大小为64 * 64 * 64 * 64 * 64 * 63 = 67,645,734,912个整数或541 at，每个整数8个字节。这是我的限制，因为下一次迭代将导致文件增加到64 *541 TB或超过34TB。
问题:我有122个uint64_t二进制文件，其中大部分是4 4GB大小。对每个单独的文件进行排序。我需要检查这些文件中是否有重复的值。
以下代码似乎可以工作，但估计要考虑多达6个字节的字符串的校验和大约需要35天。有没有人能想到任何可能更快的优化或替代方法？请注意，我不能一次在内存中完全存储两个以上的文件。
麦克
struct DataItem
{
uint64_t data;
ifstream ifs;
unique_ptr<char[]> buf;
explicit DataItem(const string &filename)
: ifs(filename, ifstream::in | ifstream::binary)
{
constexpr size_t bufSize = 1'048'576;
buf = make_unique<char[]>(bufSize);
ifs.rdbuf()->pubsetbuf(buf.get(), bufSize);
readNext();
}
void readNext()
{
if (ifs.is_open() && !ifs.eof())
ifs.read(reinterpret_cast<char *>(&data), sizeof(uint64_t));
}
bool operator<(DataItem const &other)
{
return data < other.data;
}
bool operator>(DataItem const &other)
{
return data > other.data;
}
};
int main(int argc, char *argv[])
{
path givenPath;
vector<DataItem> data;
if (argc > 1)
givenPath = path(argv[1]);
else
givenPath = path("*.dat");
auto directory = givenPath;
directory.remove_filename();
if (directory.empty())
directory = path("./");
auto extension = givenPath.extension();
for (auto &p : directory_iterator(directory))
if (p.path().extension() == extension && is_regular_file(p))
data.emplace_back(p.path().string());
sort(data.begin(), data.end());
uint64_t current = data.front().data;
data.front().readNext();
int progress = 0, loop = 0;
while (!data.empty())
{
// bubble the new value to resort the data vector
auto now = data.begin();
auto next = now + 1;
while ((next != data.end()) && (*now > *next))
{
swap(*now, *next);
++now;
++next;
}
if (current == data.front().data)
cout << current << '\t' << (current >> 32) << endl;
current = data.front().data;
if (data.front().ifs.eof())
data.erase(data.begin());
else
data.front().readNext();
++progress;
if (progress >= 1'000'000)
{
{
progress = 0;
cerr << '.';
++loop;
if (loop >= 10)
{
loop = 0;
cerr << '|';
}
}
}
}
return 0;
}回答 2
Stack Overflow用户
发布于 2018-06-10 05:39:19
当你的日志在文件中时，你不应该在执行过程中对它们进行排序。只需将哈希值写入日志即可。使用散列写入日志将使其本身并行化。在开始写入之前，请确保收集了较大的数据块(例如16MB)。
完成散列后，进行排序。避免冒泡排序，它需要O(n**2)时间。合并排序对于基于文件的排序非常有用。它可以很容易地并行化。在没有并行化的情况下，它需要O(n (N))时间。
Stack Overflow用户
发布于 2018-06-10 23:44:08
正如您已经注意到的，测试哈希函数(校验和是其变体)的质量很快变得难以处理。
因此，抗撞性通常是统计测试，而不是算法测试。一些示例包括spectral testing和chi-squared testing，前者用于查看输出的分布情况，后者用于查看在输入发生某些变化的情况下，输出如何发生不可预测的变化。还可以看看NIST SP 800-22，它定义了一些用于加密散列函数的检查。当然，字典测试也很有用，但仅限于一定的深度。
还要注意的是，针对短序列的测试通常不能提供足够的质量证明，因为长序列上哈希函数的行为可能会有本质上的不同。您至少还应该检查较长但基本相似的数据集是否不冲突，并检查边缘情况，例如当一些内部值变为0或其他临界值时(这取决于正在测试的函数的具体情况)。
话虽如此，您不需要读取内存中的整个文件；因为您的文件是排序的，所以只需一次打开所有文件，并为每个文件维护一个滑动窗口，在读取和比较条目时向前移动“指针”(移动量将因文件而异)。不过，一些缓冲将会有所帮助。
https://stackoverflow.com/questions/50778293
复制相似问题