|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.03.2013, 20:19 | #1 |
Пользователь
Регистрация: 04.11.2012
Сообщений: 33
|
Сортировка больших файлов.
Здравствуйте. Столкнулся со следующей проблемой: нужно отсортировать содержимое файла по возрастанию, размер файла более 4Gb, немного подумав, решил разбить исходный файл на кусочки по 50Mb, по отдельности сортируя их содержимое посредством std::sort, и далее поочередно сливая их std::merge, получается отсортированный файл. Потестил на файле в 650Mb, сортируется около 20-ти минут, процессор 2-х ядерный, загружается на 50%, а одним их основных условий задачи является максимальная загрузка CPU, подскажите, пожалуйста, как можно это осуществить? Советы по улучшению алгоритма также принимаются.
|
05.03.2013, 21:07 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Что в файле? (тип данных)
Благими намерениями устлана дорога на programmersforum.ru
|
05.03.2013, 21:41 | #3 |
Пользователь
Регистрация: 04.11.2012
Сообщений: 33
|
беззнаковые 4-х байтовые числа
|
05.03.2013, 21:52 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Эта задача эффективно решается индексированием (упорядочение разложением в массив). Дважды (по младшему и старшему слову (паре байтов)).
Благими намерениями устлана дорога на programmersforum.ru
|
05.03.2013, 22:07 | #5 |
Пользователь
Регистрация: 04.11.2012
Сообщений: 33
|
|
05.03.2013, 22:36 | #6 |
МегаМодератор
СуперМодератор
Регистрация: 27.11.2012
Сообщений: 5,678
|
Подобные числа в очень большом кол-ве не упорядочивают на основе сравнения
Например, самое наивное, в 4-прохода: 1-ый: Массив 2^16 - инкрементируется по младшему слову чисел Последовательным сложением получают смещения чисел. 2-ой: Числа записываются в новый файл аналогичного размера по вычисленным смещениями (которые также по ходу сдвигают). Делается буферизация, заводится еще массив, например, 2^16 x 1024 числа по 4 байта. И массив 2^16 с позициями в буфере. При заполнении любого буфера - запись соотв. чисел в файл по соотв. смещению. В конце проход по всему массиву буферов и запись в файл что осталось. Аналогичная процедура в 2 прохода с записью нового файла но только по старшим словам чисел.
Благими намерениями устлана дорога на programmersforum.ru
|
05.03.2013, 22:52 | #7 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,342
|
Запустите два потока, каждый сортирует один из файлов, по окончании берут следующий и т.д. По завершении всех файлов уже один поток сливает файлы.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Загрузка больших файлов | Rita26 | JavaScript, Ajax | 2 | 09.08.2012 11:23 |
Загрузка больших файлов | Rita26 | Общие вопросы .NET | 0 | 23.07.2012 14:47 |
Отправка больших файлов по почте | pu4koff | Софт | 6 | 17.07.2012 19:35 |
Загруprf больших файлов в blob | eldalex | SQL, базы данных | 4 | 12.10.2010 16:10 |
Открытие больших текстовых файлов | sht0p0r | Помощь студентам | 4 | 16.12.2008 12:42 |