Справочная информация. Я написал измененную подпрограмму контрольной суммы adler32, которая генерирует 64-битные контрольные суммы.Я хочу проверить наличие коллизий в области прописных и строчных букв, цифр и _.Я написал программу-генератор, которая просматривает все комбинации строк в этом диапазоне до заданной максимальной длины.Он выводит отсортированные двоичные файлы размером до 4G с результатами контрольных сумм.Ограничение 4G связано с размером памяти, хотя большие файлы означают меньшее количество файлов, что ускоряет слияние и проверку значительно.Общий размер данных для строк длиной до 6 байтов составляет 64 * 64 * 64 * 64 * 64 * 63 = 67 645 734 912 целых или 541 ГБ при 8 байтах на целое число.Это мой предел, так как следующий итератон может привести к добавлению файлов размером до 64 * 541 ГБ или более 34 ТБ.
Проблема: у меня 122 двоичных файла uint64_t, большинство из которых имеют размер 4 ГБ.Каждый отдельный файл отсортирован.Мне нужно проверить, есть ли какие-либо дубликаты значений в этих файлах.
Кажется, что работает следующий код, но, по оценкам, потребуется около 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;
}