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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

Это дает вам 6 1GB файлов, каждый из которых будет сортироваться по-отдельности. На этом этапе вы можете либо постепенно работать, либо идти на целую партию за один раз. С 6 кусков, идя на всю партию в порядке, в том, что называется «6-полосная слияния»:

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

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

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

Answer 2

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

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

Answer 3

Я предлагаю вам этого не делают.

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

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

Answer 4

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

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

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

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

Answer 5

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

Answer 6

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

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

Answer 7

Отъезд external sort. Найдите любую из внешних библиотек mergesort и измените их в соответствии с вашими потребностями.

Answer 8

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

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