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

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

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


c arrays sorting large-data qsort
person hippietrail    schedule 07.04.2011    source источник
comment
Откуда берутся и куда уходят ценности? У вас есть они все в памяти для начала?   -  person Graham Borland    schedule 08.04.2011
comment
Где они сейчас хранятся, на диске? Я предполагаю, что вы не используете 64-битную систему?   -  person Yann Ramin    schedule 08.04.2011
comment
4 миллиона умножить на 8 — это ~32 мегабайта. Он также не должен быть непрерывным — вам просто нужно непрерывное адресное пространство для сопоставленных адресов множества блоков по 4 КБ. IOW, malloc/qsort должно быть в порядке.   -  person Jerry Coffin    schedule 08.04.2011
comment
32 МБ? Это не огромный кусок. Это крошечный кусок.   -  person Vilx-    schedule 08.04.2011
comment
4 миллиона * 8 байт = 32 МБ. Это не слишком много для malloc().   -  person pajton    schedule 08.04.2011
comment
@ Янн Рамин. Они хранятся на диске в виде необработанного файла. Я бы не возражал против qsort на диске, но его сложнее реализовать, чем bsearch на диске, который я делал раньше.   -  person hippietrail    schedule 08.04.2011
comment
@Jerry Coffin: я думал, что функция C qsort() работает только с непрерывным массивом.   -  person hippietrail    schedule 08.04.2011
comment
@hippietrail: массив будет казаться смежным с вашим кодом, но это всего лишь иллюзия, созданная аппаратным обеспечением управления памятью. На самом деле он выделяется как меньшие (4 КБ или на некоторых аппаратных средствах 8 КБ) блоки. Итог: если вы не работаете в системе с действительно ограниченной памятью, это не будет проблемой.   -  person Jerry Coffin    schedule 08.04.2011
comment
640K должно быть достаточно для всех.   -  person pmg    schedule 08.04.2011
comment
Однажды я отсортировал 4 миллиарда длинных строк. Теперь для этого потребовались альтернативные механизмы. Но, в конце концов, я все же использовал qsort() для партий по 19 миллионов записей за раз...   -  person Ben Jackson    schedule 08.04.2011

Ответы (3)


arrow_upward
11
arrow_downward

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

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

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

person Gareth McCaughan    schedule 07.04.2011
comment
Единственное, что я хотел бы добавить, это то, что если данные уже являются необработанными двоичными файлами на диске, вы можете mmap (или эквивалент) вместо загрузки и записи обратно. Но если вы заботитесь о сохранности своих данных в случае сбоя системы, это, вероятно, плохая идея. - person R.. GitHub STOP HELPING ICE; 08.04.2011
comment
qsort(), конечно, работал нормально - не знаю, о чем я волновался. Я, вероятно, не знал, насколько много дает управление памятью, так как я перешел с C на языки сценариев, когда пара мегабайт была большой оперативной памятью. - person hippietrail; 08.04.2011

arrow_upward
1
arrow_downward

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

person Keith Nicholas    schedule 07.04.2011

arrow_upward
0
arrow_downward

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

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

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

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

(О, небольшая деталь, обратите внимание, что sort_heap в куче принимает не более N log N сравнений, где N — количество элементов)

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

person sehe    schedule 07.04.2011
comment
Блэдди... :) Я сегодня ослеп. Хорошо, в C должны быть эквивалентные подходы; Я надеюсь, что это все еще имеет какую-то ценность - person sehe; 08.04.2011