Возможно ли mmap для очень большого файла и использование qsort?

Question

Мне нужно отсортировать большое количество данных, которые не помещаются в памяти, и я могу сделать одно: «внешняя сортировка».Но мне интересно, возможно ли отобразить этот большой файл данных и использовать «qsort», поскольку это «обычный массив данных»?Если это возможно, в чем разница с «внешней сортировкой»?

Answer 1

Если файл поместится в непрерывное отображение в вашем адресном пространстве, вы можете сделать это.Если этого не произойдет, вы не сможете.

Что касается различий:

• , если файл подходит примерно к , и вы добавляете еще несколькоданные, Mmap не удастся.Обычная внешняя сортировка внезапно не перестанет работать, потому что у вас есть немного больше данных.
• , если вы не сопоставите их с MAP_PRIVATE, сортировка приведет к изменению исходного файла.Обычная внешняя сортировка не будет (обязательно)
• , если вы сопоставите ее с MAP_PRIVATE, вы можете в любой момент произойти сбой, если на виртуальной машине нет места для дублирования всего файла.Опять же, требования к памяти строго внешней сортировки не масштабируются линейно с размером данных.

---

tl; dr

Возможно, это может произойти непредсказуемо и неисправимо,Вы почти наверняка не должны этого делать.

Answer 2

Это определенно должно работать, если данные помещаются в адресное пространство (почти наверняка на 64-битных машинах; может или нет на 32-битных), но производительность во многом зависит от базового алгоритма, используемого qsort и его свойства локальности данных.Одна проблема, которую нужно рассмотреть, это то, является ли количество элементов огромным или же каждый элемент имеет большой размер на диске.В последнем случае вам лучше выполнить mmap, но выделить отдельный массив указателей для каждого элемента, а затем отсортировать массив указателей с функцией сравнения, которая сравнивает то, на что они указывают.Это значительно сократит количество перемещений данных в памяти, но в конце потребуется небольшая работа, если вы хотите сохранить выходные данные обратно в тот же файл.

Answer 3

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