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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
Butt-Head
Заблокирован
#1

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

29.07.2015, 16:30. Просмотров 3256. Ответов 85
Метки нет (Все метки)

Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего 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++ Наиболее быстрый способ сравнения двух экземпляров структур на предмет одинаковости их полей
C++ Memory shift или самый быстрый способ перемещения блока памяти
C++ Работа с бинарными файлами: какой способ работает наиболее быстро при записи и считывании?
C++ Быстрый способ получение уникального ID
C++ Самый быстрый способ решения задачи a+b
Быстрый способ сравнить содержимое двух файлов C++
C++ Быстрый способ определения цвета пиксела координатам x, y
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
5263 / 4583 / 1537
Регистрация: 14.04.2014
Сообщений: 18,213
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
563 / 277 / 37
Регистрация: 21.07.2015
Сообщений: 847
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
5263 / 4583 / 1537
Регистрация: 14.04.2014
Сообщений: 18,213
29.07.2015, 21:37     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот была тема: Сортировка больших текстовых файлов размером до двух терабайт
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 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
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
29.07.2015, 21:56     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот тут есть информация по теме + код,, можете глянуть
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 22:01     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #10
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Я никак не буду обходить. Мне эта задача не интересна. Я лишь цитировал сообщение пользователя shmkv, которое ты пропустил.
smartpointer
67 / 61 / 23
Регистрация: 17.02.2014
Сообщений: 256
29.07.2015, 22:09     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Почему то хотел изначально отговорить от MergeSort, поскольку она требовательна к памяти, но видимо в данном случае без нее никак, кстати можно взять немного оптимизации из TimSort при склеивании двух фрагментов, в случае постоянного извлечения из одного подмассива брать следущий элемент галопом, так можно записывать в исходный массив целыми кусками.
Butt-Head
Заблокирован
29.07.2015, 22:21  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #12
Цитата Сообщение от castaway Посмотреть сообщение
Я никак не буду обходить. Мне эта задача не интересна
Сама вакансия мне если честно то же не очень интересна, вот этот вопрос мне стал интересен чисто по профессиональному.
Интересно, может быть можно как - то вообще без вспомогательный файлов?
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 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. ..
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2015, 22:54     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Еще ссылки по теме:
Быстрый поиск наиболее близких вершин графа C++
Самый быстрый способ посчитать сумма элементов матрицы, находящихся в матрице C++
C++ Считать квадратную матрицу. Какой самый быстрый способ это сделать?
C++ По заданным номерам остановок определить наиболее быстрый путь перемещения пассажира
Каков самый быстрый способ узнать количество строк в оргомном текстовом файле в Windows? C++

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

Или воспользуйтесь поиском по форуму:
shmkv
563 / 277 / 37
Регистрация: 21.07.2015
Сообщений: 847
29.07.2015, 22:54     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #15
Цитата Сообщение от Butt-Head Посмотреть сообщение
Объединять какие фалы?
Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Цитата Сообщение от shmkv Посмотреть сообщение
Считать инты, сколько гарантированно влезет в память
...
Yandex
Объявления
29.07.2015, 22:54     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru