C - сортировка больших двоичных файлов с элементами переменной длины - PullRequest
Новая
       30

C - сортировка больших двоичных файлов с элементами переменной длины

0 голосов
/ 17 ноября 2018

Моя проблема заключается в следующем:

  • У меня есть набор элементов с переменной длиной, хранящихся в двоичном файле, который мы назовем data.bin.
  • Каждый элемент имеет параметр ключа сортировки, который мы назовем key, размер size и позицию файла в data.bin pos.Эти 3 параметра представлены в виде структуры.

Проблема заключается в том, как эффективно сортировать 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 очень большой (мой общийслучай использования составляет 30 ГБ), количество записей составляет около 10 МБ, и две последовательные отсортированные записи могут быть очень далеко от исходного файла data.bin.Для data.bin файла объемом 1 ГБ этот подход может потребовать даже более 30 минут, даже если я использую твердотельный накопитель HD.

У вас есть какие-либо идеи, альтернативные решения или подходы к этой проблеме?

Я пытался использовать файлы с отображением в памяти с похожими или даже худшими характеристиками.Я думаю, что узким местом является fseek вызов, однако я не могу найти альтернативы и более эффективные подходы.

Спасибо за чтение, S,

1 Ответ

0 голосов
/ 17 ноября 2018

При вашем подходе вы получаете только один элемент за чтение, так что это 10 миллионов команд для чтения файла в соответствии с отсортированными ключами. По крайней мере, SSD устранит издержки произвольного доступа.

Должно быть быстрее использовать внешнюю сортировку слиянием для прямой сортировки данных, а не для сортировки ключей и выполнения произвольного доступа. Это позволило бы использовать чтение / запись для чуть более 256 МБ за раз. Первоначальный этап считывал фрагменты 256 МБ, сортировал элементы, а затем записывал фрагменты 256 МБ (128 из них составляли бы 32 ГБ). 16-канальное слияние (2048 операций чтения по 16 МБ каждый) с последующим 8-канальным слиянием (1024 чтения, 32 МБ на чтение) будет сортировать около 32 ГБ данных. Для слияния 16 или 8 вы, вероятно, захотите использовать некоторую форму очереди с приоритетами, например, кучу.

Вы не упоминаете, находится ли информация о ключе / размере в отдельном файле. Если имеется достаточно свободной памяти, вы можете просто сохранить эту информацию в памяти во время внешней сортировки слиянием и записать ее обратно, когда закончите.

...