在 C++ 优化中合并大型二进制文件

Question

>背景： 我编写了一个修改后的 adler32 校验和例程，它生成 64 位校验和。 我想检查大写和小写字母、数字和 _ 区域中的冲突。 我编写了一个生成器程序，可以逐步执行此范围内的所有字符串组合，直至给定的最大长度。 它具有最大 4G 大小的排序二进制文件的输出以及校验和的结果。 4G限制是由于内存大小，尽管较大的文件意味着更少的文件，从而显着加快了合并和检查的速度。 最多 6 字节字符串的总数据大小为 64 * 64 * 64 * 64 * 64 * 63 = 67,645,734,912 个整数或 541GB，每个整数 8 个字节。 这是我的限制，因为下一次迭代将导致文件总计高达 64 * 541GB 或超过 34 TB。

问题： 我有 122 个二进制文件uint64_t，其中大部分大小为 4GB。 对每个单独的文件进行排序。 我需要检查这些文件是否有任何重复值。

以下代码似乎有效，但估计需要大约 35 天才能考虑最多 6 字节字符串的校验和。 谁能想到任何可能更快的优化或替代方法？ 请注意，我不能同时在内存中完全包含两个以上的文件。

话筒

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;
}

Answer 1

当您的日志位于文件中时，您不应在执行过程中对其进行排序。只需在哈希出现时将其写入日志即可。使用哈希写入日志有助于并行化。确保在开始写入之前收集大块(例如 16 MB(。

完成哈希后进行排序。避免气泡排序，它需要 O(n**2( 时间。合并排序非常适合基于文件的排序。它可以很容易地并行化。如果没有并行化，它需要 O(n log(n(( 时间。

Answer 2

正如您已经注意到的那样，测试哈希函数(校验和是其变体(的质量很快就会变得棘手。

因此，抗碰撞性通常通过统计而不是算法进行测试。一些示例包括频谱测试，以查看输出的分布情况，以及卡方测试，以查看输入发生某些变化时输出的不可预测变化程度。 另请查看 NIST SP 800-22，它定义了对加密哈希函数的一些检查。 当然，字典测试也很有用，但仅限于一定的深度。

另请注意，针对短序列的测试通常不能提供足够的质量证明，因为哈希函数在较长序列上的行为可能大不相同。 您至少还应该检查更长但大致相似的数据集是否不冲突，并检查边缘情况，例如当某些内部值变为 0 或其他临界值时(这取决于所测试函数的具体情况(。

话虽如此，您不需要读取内存中的整个文件;由于您的文件已排序，只需一次打开所有文件并为每个文件维护一个滑动窗口，在读取和比较条目时向前移动"指针"(每个文件的移动量会有所不同(。不过，一些缓冲会有所帮助。