Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1 террабайт, если на компе, к примеру, доступно всего 2 гб оперативки ... ?
Ну файл с нитами типа:
1
2
3
4
6346546
234524234
656546546
24234234
777
654646
и тд



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

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

Наиболее быстрый способ сравнения двух экземпляров структур на предмет одинаковости их полей - C++
Есть структура, в которой есть несколько int-ов и char-ов, какой имеется наиболее быстрый способ в C/C++ для сравнения двух экземпляров...

Memory shift или самый быстрый способ перемещения блока памяти - C++
int* dataField = new int{0}; for (int i = 0; i < 50; i++) dataField = 777; //тут должен быть memory shift delete dataField;...

Работа с бинарными файлами: какой способ работает наиболее быстро при записи и считывании? - C++
Всем привет прошу помощи по этой теме. Попробую изложить кратко: 1) Есть не бинарный файл -> Считываю его ifstream -> работаю с данными...

Быстрый способ получение уникального ID - C++
Есть какой - то список уже существующих уникальных ID, нужно наибыстрейшим способом создать новый уникальный для этого списка ID. (пусть...

Самый быстрый способ решения задачи a+b - C++
несколько раз ходил на олимпиады, во многих из них в пробном туре даётся задача а+б, решаю её стандартным способом: cin >> a >> b; ...

Быстрый способ сравнить содержимое двух файлов - C++
Здравствуйте, подскажите наиболее быстрый способ сравнить содержимое двух текстовых файлов и вывести различия.

85
nmcf
5677 / 4987 / 1700
Регистрация: 14.04.2014
Сообщений: 20,335
29.07.2015, 18:01 #2
Файл текстовый?
1
Butt-Head
Заблокирован
29.07.2015, 21:14  [ТС] #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, так ты подкинешь идейку, как эту сортировку получше реализовать?
0
shmkv
611 / 326 / 41
Регистрация: 21.07.2015
Сообщений: 972
29.07.2015, 21:27 #4
Butt-Head, ну я бы сделал как-то так:
1.В цикле до конца файла:
1.1 Считать инты, сколько гарантированно влезет в память.
2.2. Отсортировать их быстрой сортировкой.
2.3 записать фрагмент во временный файл (обязательно в двоичном виде) с уникальным именем для (для фрагмента).
2. Последовательно попарно объединят файлы сортировкой слиянием. Когда останется 2 фрагмента - сливаешь в один текстовый.
1
Butt-Head
Заблокирован
29.07.2015, 21:36  [ТС] #5
Цитата Сообщение от shmkv Посмотреть сообщение
Последовательно попарно объединят файлы сортировкой слиянием. Когда останется 2 фрагмента - сливаешь в один текстовый.
Объединять какие фалы?
0
nmcf
5677 / 4987 / 1700
Регистрация: 14.04.2014
Сообщений: 20,335
29.07.2015, 21:37 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот была тема: Сортировка больших текстовых файлов размером до двух терабайт
1
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 21:44 #7
Цитата Сообщение от Butt-Head Посмотреть сообщение
Объединять какие фалы?
Цитата Сообщение от shmkv Посмотреть сообщение
2.3 записать фрагмент во временный файл
...
1
Butt-Head
Заблокирован
29.07.2015, 21:51  [ТС] #8
nmcf, я не очень въехал в чём там ваще фокус ...
Ну открыл ты кучу потоков, о одной строчке читаешь из каждого потока и пишешь в финальный поток...
Бред какой - то.
А что - то не помню, файловый поток в памяти занимает размер файлы или нет?
Вот тут нашёл кое что, но не понял суть опять же http://stackoverflow.com/questions/4...from-hard-disk

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

Как вообще, пусть даже не быстро, отсортировать файл в 1 террабайт?
0
iRomul
159 / 100 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
29.07.2015, 21:56 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот тут есть информация по теме + код,, можете глянуть
1
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 22:01 #10
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Я никак не буду обходить. Мне эта задача не интересна. Я лишь цитировал сообщение пользователя shmkv, которое ты пропустил.
0
smartpointer
69 / 63 / 24
Регистрация: 17.02.2014
Сообщений: 264
29.07.2015, 22:09 #11
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Почему то хотел изначально отговорить от MergeSort, поскольку она требовательна к памяти, но видимо в данном случае без нее никак, кстати можно взять немного оптимизации из TimSort при склеивании двух фрагментов, в случае постоянного извлечения из одного подмассива брать следущий элемент галопом, так можно записывать в исходный массив целыми кусками.
0
Butt-Head
Заблокирован
29.07.2015, 22:21  [ТС] #12
Цитата Сообщение от castaway Посмотреть сообщение
Я никак не буду обходить. Мне эта задача не интересна
Сама вакансия мне если честно то же не очень интересна, вот этот вопрос мне стал интересен чисто по профессиональному.
Интересно, может быть можно как - то вообще без вспомогательный файлов?
0
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 22:43 #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кБ ОЗУ.
0
Butt-Head
Заблокирован
29.07.2015, 22:51  [ТС] #14
Цитата Сообщение от castaway Посмотреть сообщение
Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ.
Хмм... Я в принципе знал про это, но конечно же хотелось чего - то кроссового. Ну да ладно, для кроссового я так понял нужно External Merge Sort
Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. ..
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт
0
shmkv
611 / 326 / 41
Регистрация: 21.07.2015
Сообщений: 972
29.07.2015, 22:54 #15
Цитата Сообщение от Butt-Head Посмотреть сообщение
Объединять какие фалы?
Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Цитата Сообщение от shmkv Посмотреть сообщение
Считать инты, сколько гарантированно влезет в память
...
0
29.07.2015, 22:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2015, 22:54
Привет! Вот еще темы с ответами:

Быстрый способ определения цвета пиксела координатам x, y - C++
В общем задача такая , нужен быстрый способ определения цвета пиксела в настоящее время на экране по заданным координатам x, y мне нужно...

Наиболее быстрый способ склеивания фрагментов файла - C#
Имеется несколько фрагментов одного файла. Требуется собрать эти фрагменты в исходный файл. Размеры фрагментов могут быть разными, от...

Наиболее быстрый способ забрать данные из html - C# ASP.NET
Мне нужно забрать данные с вебстранички. Там может содержаться просто одно слово, например "ОК", в этом случае использую следующую...

Наиболее быстрый способ работы с файлом Excel (около 20000 строк) - C#
Здравствуйте ребята, хотел спросить у вас совета. Есть программа по распечатке ценников по артикулу или штрихкоду товара. Какой обработкой...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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