как отсортировать много данных в c?

Question

в данный момент я пытаюсь записать нереальный объем данных в файлы,

в основном я генерирую новую структуру данных и записываю ее в файл, пока файл не станет размером 1 ГБ, и это происходит для6 файлов по 1 Гб каждый, структуры небольшие.8 байтов длиной с двумя 2 переменными id и количеством

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

помните, что есть 6 ГБ данных, как я могу отсортировать эти структуры по значению id и затем записать в файл?

или мне следует написатьсначала файл, а затем отсортировать каждый отдельный файл, и как мне собрать все эти данные в один файл?

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

Мне нужен хороший способ сортировки большого количества данных?(6gb)

Answer 1

Я не нашел вопрос с очень простым ответом на этот вопрос, так что здесь.

Кстати, если вы работаете на 64-битной машине, вам следует серьезно подумать о том, чтобы записать все данные в файл, отобразить в памяти файл и просто использовать тот массив, который вам нравится. Быстрая сортировка довольно приятна для кэша: она не будет сильно зависать. Задание, вероятно, предназначено, чтобы помешать вам сделать это, но может быть немного устаревшим; -)

В противном случае вам нужен какой-то внешний вид. Есть и другие способы сделать это, но я думаю, что сортировка слиянием, вероятно, самая простая. Перед началом слияния:

• определите, сколько данных вы можете поместить в память (или, опять же, отобразить их). Если вы работаете на ПК, то 1 ГБ выглядит вполне обоснованным предположением, но может быть в несколько раз больше или меньше.
• загрузить столько данных (так, например, один из ваших 6 файлов)
• Быстрая сортировка (поскольку вы пометили «Быстрая сортировка», я думаю, вы знаете, как это сделать) или любой другой вид по вашему выбору.
• запишите его обратно на диск (если вы не сделали mmap).

В результате у вас останется 6 файлов по 1 ГБ, каждый из которых будет отсортирован по отдельности. На этом этапе вы можете либо работать постепенно, либо делать все за один раз. С 6 кусками все в порядке, что называется «объединением в 6 направлений»:

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

Существует некоторая оптимизация, которую вы можете предпринять, чтобы определить, какая из ваших 6 возможностей наименьшая, но большая разница в производительности будет заключаться в том, чтобы убедиться, что вы используете достаточно большие буферы чтения и записи.

Очевидно, что нет ничего особенного в том, что слияние происходит в 6 направлений. Если вы предпочитаете двухстороннее слияние, которое легче кодировать, то, конечно, вы можете. Для объединения 6 файлов потребуется 5 двусторонних слияний.

Answer 2

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

http://www.sqlite.org/features.html

Answer 3

Я советую вам этого не делать.

Если вы хотите хранить такой объем данных, почему бы не использовать выделенный формат базы данных, который может иметь множество различных индексов и мощный механизм запросов.

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

Answer 4

Что ж, поскольку фактическое назначение состоит в том, чтобы сохранить закодированные данные, а затем просто сравнить их с декодированными данными, я бы также сказал - использовать базу данных и просто создать хеш-индекс в столбце идентификатора.

НоЧто касается такого огромного числа, другая очень важная вещь - сделать это параллельно.Есть много способов сделать это.Стив Джессоп упомянул подход сортировки-слияния: действительно легко отсортировать первые 6 блоков параллельно, вопрос только в том, сколько ядер процессора и памяти у вас на машине.(Сегодня редко можно найти компьютер с одним ядром, а также не так уж редко 4 ГБ памяти).

Answer 5

Проверить внешняя сортировка .Найдите любую из внешних библиотек слияния и измените их в соответствии с вашими потребностями.

Answer 6

Сначала отсортируйте каждый файл по отдельности.Либо загрузите все это в память, либо (лучше) mmap, и используйте функцию qsort.

Затем напишите собственную сортировку слиянием, которая принимает N FILE * входов (т.е.1007 * в вашем случае) и выводит в N новые файлы, переключаясь на следующий при заполнении.

Answer 7

Может быть, вы могли бы использовать mmap и использовать его в качестве огромного массива, который вы могли бы сортировать с помощью qsort.Я не уверен, каковы будут последствия.Будет ли это расти в памяти?

Answer 8

Самый простой способ (во время разработки) сделать это - записать данные в отдельные файлы в соответствии с их идентификатором.Вам не нужно совпадать от 1 до 1 между количеством файлов и количеством идентификаторов (если идентификаторов много), но если вы выберете префикс идентификатора (например, если ключ для одного конкретногозапись - 987, она может помещаться в файл 9, тогда как запись с ключом 456 - в файл 4) вам не нужно беспокоиться о расположении всех ключей во всех файлах, поскольку сортировка каждого файла сама по себе приведет ктогда просмотр файлов в их порядке (по именам) даст вам отсортированные результаты.

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

Что касается сортировки содержимого файла, который слишком велик для размещения в ОЗУ, вы можете использовать сортировку слиянием непосредственно в файле или использовать замена выделение сортировка для сортировки файла на месте.Это включает в себя несколько проходов по файлу при использовании некоторого объема ОЗУ (чем больше, тем лучше) для хранения очереди с приоритетами (двоичной кучи) и набора записей, которые не могут быть использованы в этом запуске (их ключи предполагают, что они должнынаходиться в файле раньше текущей позиции запуска, поэтому вы просто держитесь за них до следующего запуска).

Поиск замена выбор сортировка или турнир сортировка даст лучшие объяснения.