时间戳

首页 > 解决方案 > C - 对具有可变长度元素的大型二进制文件进行排序

c - C - 对具有可变长度元素的大型二进制文件进行排序

问题描述

我的问题如下：

问题是如何data.bin有效地排序。

现在我已经定义了一个数据结构

typedef struct {
    int key;
    unsigned int size;
    long int pos;
} index

和一个数组index indices[]，其中包含存储在 中的元素的值data.bin。该列表根据key使用快速排序算法连续排序，即使对于非常大量的条目（例如10M）也足够快。然后我使用排序列表indices将排序后的data.bin文件写为sorted.bin. 我的代码的核心如下（这里我故意删除了错误检查部分）：

size_t mergeBuffIdx = 0;
char  *mergeBuff = (char *) calloc(MERGE_BUFF_SIZE, sizeof(char));

for (unsigned int idx = 0; idx < numEntries; idx++) {
    unsigned int dataSize = indices[idx].size;
    if ((mergeBuffIdx + dataSize) >= MERGE_BUFF_SIZE) {
            fwrite(mergeBuff, sizeof(unsigned char), mergeBuffIdx, sortedDataFile);
            mergeBuffIdx = 0;
    }

    // set the file pointer at the beginning of the data file position
    fseek(dataFile, indices[idx].pos, SEEK_SET);

    // read the data from the file as an unsigned char array
    fread(&mergeBuff[mergeBuffIdx], sizeof(unsigned char), dataSize, dataFile);
    mergeBuffIdx += dataSize;
}

// write remaining data
if (mergeBuffIdx != 0) {
    fwrite(mergeBuff, sizeof(unsigned char), mergeBuffIdx, sortedDataFile);
}

这种方法非常简单，但在data.bin非常大（我的一般用例是 30GB）时很快就会变得非常慢，条目数约为 10M 并且两个连续排序的条目可能在原始data.bin文件上很远。对于data.bin1GB 的文件，即使我使用的是 SSD HD，这种方法也可能需要 30 多分钟。

您对这个问题有一些想法、替代解决方案或方法吗？

我曾尝试使用性能相似甚至最差的内存映射文件。我的想法是瓶颈是fseek调用，但是，我无法找出替代方案和更高效的方法。

感谢阅读，S，

标签： cperformancesortingiobinaryfiles

解决方案

使用您的方法，每次读取只能获得一个元素，因此根据排序键读取文件的命令为 1000 万条。至少 SSD 将消除随机访问开销。

使用外部合并排序直接对数据进行排序而不是排序键并进行随机访问应该更快。这将允许一次使用可能超过 256 MB 的读/写。初始通道将读取 256MB 块，对元素进行排序，然后写入 256MB 块（其中 128 个是 32GB）。16 路合并（2048 次读取，每次 16 MB）然后是 8 路合并（1024 次读取，每次读取 32 MB）将排序大约 32GB 的数据。对于 16 或 8 路合并，您可能希望使用某种形式的优先级队列，例如堆。

您没有提及密钥/大小信息是否在单独的文件中。如果有足够的空闲内存，您可以在外部合并排序期间将此信息保留在内存中，并在完成后将其写回。

推荐阅读