Как отсортировать очень большой массив в C

Question

Я хочу отсортировать порядка четырех миллионов long long с в C. Обычно я бы просто malloc() буфер использовал в качестве массива и вызывал qsort(), но четыре миллиона * 8 байт - это один большой кусок непрерывная память.

Какой самый простой способ сделать это? Я оцениваю легкость над чистой скоростью для этого. Я предпочел бы не использовать какие-либо библиотеки, и результат должен будет работать на скромном нетбуке как под Windows, так и под Linux.

Answer 1

Просто выделите буфер и вызовите qsort.32 МБ в наши дни не такие уж большие, даже на скромном нетбуке.

Если вам действительно нужно разбить его на части: сортируйте меньшие куски, записывайте их в файлы и объединяйте их (объединение занимает один линейный проходкаждая из вещей объединяется).Но на самом деле нет.Просто отсортируйте его.

(Хорошее обсуждение подхода сортировки и слияния во втором томе Кнута, где он называется «внешняя сортировка». Когда Кнут писал это, внешние данные были бы включенымагнитная лента, но принципы работы с дисками не сильно отличаются: вы все же хотите, чтобы ваш ввод / вывод был максимально последовательным. Компромиссы немного отличаются от SSD.)

Answer 2

32 МБ?это не слишком большой .... быстрая сортировка должна сделать свое дело.

Answer 3

Лучшим вариантом будет, если это возможно, предотвратить неупорядоченные данные. Как уже было упомянуто, вам лучше читать данные с диска (или сети, или любого другого источника) непосредственно в самоорганизующийся контейнер (дерево, возможно, подойдет std::set).

Таким образом, вам никогда не придется разбирать партии или беспокоиться об управлении памятью. Если вы знаете требуемую емкость контейнера, вы можете выжать дополнительную производительность, используя std::vector(initialcapacity) или позвонив vector::reserve заранее.

Тогда вам лучше всего использовать std::make_heap до heapify любых существующих элементов, а затем добавлять элемент за элементом, используя push_heap (см. Также pop_heap). По сути, это та же парадигма, что и у самоупорядочивающегося множества, но

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

(О, мелкие детали, обратите внимание, что sort_heap в куче занимает не более N log N сравнений, где N - количество элементов)

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