Форум программистов, компьютерный форум CyberForum.ru

Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
Butt-Head
Заблокирован
29.07.2015, 16:30     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #1
Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1 террабайт, если на компе, к примеру, доступно всего 2 гб оперативки ... ?
Ну файл с нитами типа:
1
2
3
4
6346546
234524234
656546546
24234234
777
654646
и тд



Добавлено через 1 час 11 минут
Важная тема теряется... Up!

Добавлено через 4 часа 45 минут
Ну так что, никто не подскажет, как отсортировать 1 гиг в файле?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2015, 16:30     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Посмотрите здесь:

C++ Быстрый способ определения цвета пиксела координатам x, y
Самый быстрый способ посчитать сумма элементов матрицы, находящихся в матрице C++
C++ Считать квадратную матрицу. Какой самый быстрый способ это сделать?
Быстрый способ сравнить содержимое двух файлов C++
C++ Быстрый способ получение уникального ID
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
4265 / 3696 / 1243
Регистрация: 14.04.2014
Сообщений: 14,476
29.07.2015, 18:01     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #2
Файл текстовый?
Butt-Head
Заблокирован
29.07.2015, 21:14  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #3
Цитата Сообщение от nmcf Посмотреть сообщение
Файл текстовый?
Хмм... а хз. Вот оригинальный текст вопроса:
You have a 1TB file containing integers (one number per line). You have 2GB of memory. How do you sort this file as fast as possible?

Судя по фразе: one number per line могу предположить, что текстовой ...

Добавлено через 3 часа 5 минут
nmcf, так ты подкинешь идейку, как эту сортировку получше реализовать?
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 749
29.07.2015, 21:27     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #4
Butt-Head, ну я бы сделал как-то так:
1.В цикле до конца файла:
1.1 Считать инты, сколько гарантированно влезет в память.
2.2. Отсортировать их быстрой сортировкой.
2.3 записать фрагмент во временный файл (обязательно в двоичном виде) с уникальным именем для (для фрагмента).
2. Последовательно попарно объединят файлы сортировкой слиянием. Когда останется 2 фрагмента - сливаешь в один текстовый.
Butt-Head
Заблокирован
29.07.2015, 21:36  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #5
Цитата Сообщение от shmkv Посмотреть сообщение
Последовательно попарно объединят файлы сортировкой слиянием. Когда останется 2 фрагмента - сливаешь в один текстовый.
Объединять какие фалы?
nmcf
4265 / 3696 / 1243
Регистрация: 14.04.2014
Сообщений: 14,476
29.07.2015, 21:37     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот была тема: Сортировка больших текстовых файлов размером до двух терабайт
castaway
Эксперт С++
4839 / 2978 / 367
Регистрация: 10.11.2010
Сообщений: 11,012
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 21:44     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #7
Цитата Сообщение от Butt-Head Посмотреть сообщение
Объединять какие фалы?
Цитата Сообщение от shmkv Посмотреть сообщение
2.3 записать фрагмент во временный файл
...
Butt-Head
Заблокирован
29.07.2015, 21:51  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #8
nmcf, я не очень въехал в чём там ваще фокус ...
Ну открыл ты кучу потоков, о одной строчке читаешь из каждого потока и пишешь в финальный поток...
Бред какой - то.
А что - то не помню, файловый поток в памяти занимает размер файлы или нет?
Вот тут нашёл кое что, но не понял суть опять же http://stackoverflow.com/questions/4...from-hard-disk

Добавлено через 1 минуту
Цитата Сообщение от castaway Посмотреть сообщение
записать фрагмент во временный файл
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.

Как вообще, пусть даже не быстро, отсортировать файл в 1 террабайт?
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
29.07.2015, 21:56     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот тут есть информация по теме + код,, можете глянуть
castaway
Эксперт С++
4839 / 2978 / 367
Регистрация: 10.11.2010
Сообщений: 11,012
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 22:01     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #10
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Я никак не буду обходить. Мне эта задача не интересна. Я лишь цитировал сообщение пользователя shmkv, которое ты пропустил.
smartpointer
 Аватар для smartpointer
64 / 58 / 23
Регистрация: 17.02.2014
Сообщений: 250
29.07.2015, 22:09     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Почему то хотел изначально отговорить от MergeSort, поскольку она требовательна к памяти, но видимо в данном случае без нее никак, кстати можно взять немного оптимизации из TimSort при склеивании двух фрагментов, в случае постоянного извлечения из одного подмассива брать следущий элемент галопом, так можно записывать в исходный массив целыми кусками.
Butt-Head
Заблокирован
29.07.2015, 22:21  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #12
Цитата Сообщение от castaway Посмотреть сообщение
Я никак не буду обходить. Мне эта задача не интересна
Сама вакансия мне если честно то же не очень интересна, вот этот вопрос мне стал интересен чисто по профессиональному.
Интересно, может быть можно как - то вообще без вспомогательный файлов?
castaway
Эксперт С++
4839 / 2978 / 367
Регистрация: 10.11.2010
Сообщений: 11,012
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 22:43     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #13
Цитата Сообщение от Butt-Head Посмотреть сообщение
Интересно, может быть можно как - то вообще без вспомогательный файлов?
Как вариант, алгоритм исключительно для WinAPI и для двоичного файла:
C++
1
2
3
4
5
6
7
8
    HANDLE hFile = CreateFile( "test", GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 0, NULL );
    DWORD dwSize = GetFileSize( hFile,  NULL );
    HANDLE hMap = CreateFileMapping( hFile, NULL, PAGE_READWRITE, 0, 0, NULL );
    int * p = (int *)MapViewOfFile( hMap, FILE_MAP_WRITE, 0, 0, 0 );
    std::sort( p, p + dwSize / sizeof( int ) );
    UnmapViewOfFile( p );
    CloseHandle( hMap );
    CloseHandle( hFile );
Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ.
Butt-Head
Заблокирован
29.07.2015, 22:51  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #14
Цитата Сообщение от castaway Посмотреть сообщение
Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ.
Хмм... Я в принципе знал про это, но конечно же хотелось чего - то кроссового. Ну да ладно, для кроссового я так понял нужно External Merge Sort
Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. ..
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 749
29.07.2015, 22:54     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #15
Цитата Сообщение от Butt-Head Посмотреть сообщение
Объединять какие фалы?
Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Цитата Сообщение от shmkv Посмотреть сообщение
Считать инты, сколько гарантированно влезет в память
...
Butt-Head
Заблокирован
29.07.2015, 22:57  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #16
Цитата Сообщение от shmkv Посмотреть сообщение
Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.
Смотри. Вот есть у тебя три куска:
Первый: 0,7,3 [допустим размер 1 гб]
Второй: 4,2,8 [допустим размер 1 гб]
Третий: 9,0,8 [допустим размер 1 гб]

sort первых двух:
Первый: 0,3,7
Второй: 2,4,8

смерджил их:
merge1: 0,2,3,4,7,8 [2 гб]

что ты дальше будешь делать? Подгружать весь merg1 в память и сливать его с третьим куском? Тогда у тебя этот мердж кусок будет расти как на дрожжах и привет пямять ...
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 749
29.07.2015, 22:58     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #17
Цитата Сообщение от Butt-Head Посмотреть сообщение
ожет быть можно как - то вообще без вспомогательный файлов?
Можно, но будет ооочень долго.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
Подгружать весь merg1
Чтобы сливать совсем необязательно грузить файл целиком.
castaway
Эксперт С++
4839 / 2978 / 367
Регистрация: 10.11.2010
Сообщений: 11,012
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 23:01     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #18
Цитата Сообщение от Butt-Head Посмотреть сообщение
Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. ..
Его размер не меняется. Зачем его считать?

Цитата Сообщение от Butt-Head Посмотреть сообщение
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт
Детали не знаю. Может и упадёт.
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 749
29.07.2015, 23:01     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #19
Цитата Сообщение от Butt-Head Посмотреть сообщение
как это проекция физический работает, что - то я не пойму
Да работает она просто - при обращении к памяти #PF генерируется и ОС по этому адресу страницу из файла подгружает. Сам я никогда не использовал эту технологию. Но чудес-то не бывает, если памяти жрет мало, значит постоянно тасует страницы между диском и озу, что не особо благоприятно скажется на скорости.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2015, 23:10     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Еще ссылки по теме:

C++ Работа с бинарными файлами: какой способ работает наиболее быстро при записи и считывании?
C++ Memory shift или самый быстрый способ перемещения блока памяти
C++ Самый быстрый способ решения задачи a+b

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
29.07.2015, 23:10     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #20
Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл.

Как так сразу сливаем? Просто открываем все файлы. У каждого файла есть итератор на текущее число в нем. Выбираем наименьшее число среди всех итераторов. Пишем его в результирующий файл. Сдвигаем этот итератор на следующее число в этом файле. Снова выбираем наименьшее число среди итераторов. И так далее, пока все итераторы не дойдут до конца своих файлов.

Это самый простой и очевидный метод. Его можно оптимизировать. Например, читать из каждого файла не по одному числу, а пачками.

Так как у нас там числа, то можем сортировать за O(n).
Yandex
Объявления
29.07.2015, 23:10     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Ответ Создать тему
Опции темы

Текущее время: 05:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru