Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.59/22: Рейтинг темы: голосов - 22, средняя оценка - 4.59
Butt-Head
Заблокирован
#1

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

29.07.2015, 16:30. Просмотров 3993. Ответов 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
Ответы с готовыми решениями:

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

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

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

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

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

85
nmcf
6271 / 5577 / 2537
Регистрация: 14.04.2014
Сообщений: 23,468
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
903 / 405 / 59
Регистрация: 21.07.2015
Сообщений: 1,090
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
6271 / 5577 / 2537
Регистрация: 14.04.2014
Сообщений: 23,468
29.07.2015, 21:37 #6
Лучший ответ Сообщение было отмечено Butt-Head как решение

Решение

Вот была тема: Сортировка больших текстовых файлов размером до двух терабайт
1
castaway
Эксперт С++
4929 / 3036 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 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 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
29.07.2015, 21:56 #9
Лучший ответ Сообщение было отмечено Butt-Head как решение

Решение

Вот тут есть информация по теме + код,, можете глянуть
1
castaway
Эксперт С++
4929 / 3036 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 22:01 #10
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Я никак не буду обходить. Мне эта задача не интересна. Я лишь цитировал сообщение пользователя shmkv, которое ты пропустил.
0
smartpointer
69 / 63 / 39
Регистрация: 17.02.2014
Сообщений: 264
29.07.2015, 22:09 #11
Лучший ответ Сообщение было отмечено Butt-Head как решение

Решение

Почему то хотел изначально отговорить от MergeSort, поскольку она требовательна к памяти, но видимо в данном случае без нее никак, кстати можно взять немного оптимизации из TimSort при склеивании двух фрагментов, в случае постоянного извлечения из одного подмассива брать следущий элемент галопом, так можно записывать в исходный массив целыми кусками.
0
Butt-Head
Заблокирован
29.07.2015, 22:21  [ТС] #12
Цитата Сообщение от castaway Посмотреть сообщение
Я никак не буду обходить. Мне эта задача не интересна
Сама вакансия мне если честно то же не очень интересна, вот этот вопрос мне стал интересен чисто по профессиональному.
Интересно, может быть можно как - то вообще без вспомогательный файлов?
0
castaway
Эксперт С++
4929 / 3036 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 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
903 / 405 / 59
Регистрация: 21.07.2015
Сообщений: 1,090
29.07.2015, 22:54 #15
Цитата Сообщение от Butt-Head Посмотреть сообщение
Объединять какие фалы?
Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.
Цитата Сообщение от shmkv Посмотреть сообщение
Считать инты, сколько гарантированно влезет в память
...
0
Butt-Head
Заблокирован
29.07.2015, 22:57  [ТС] #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 в память и сливать его с третьим куском? Тогда у тебя этот мердж кусок будет расти как на дрожжах и привет пямять ...
0
shmkv
903 / 405 / 59
Регистрация: 21.07.2015
Сообщений: 1,090
29.07.2015, 22:58 #17
Цитата Сообщение от Butt-Head Посмотреть сообщение
ожет быть можно как - то вообще без вспомогательный файлов?
Можно, но будет ооочень долго.

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

Цитата Сообщение от Butt-Head Посмотреть сообщение
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт
Детали не знаю. Может и упадёт.
0
shmkv
903 / 405 / 59
Регистрация: 21.07.2015
Сообщений: 1,090
29.07.2015, 23:01 #19
Цитата Сообщение от Butt-Head Посмотреть сообщение
как это проекция физический работает, что - то я не пойму
Да работает она просто - при обращении к памяти #PF генерируется и ОС по этому адресу страницу из файла подгружает. Сам я никогда не использовал эту технологию. Но чудес-то не бывает, если памяти жрет мало, значит постоянно тасует страницы между диском и озу, что не особо благоприятно скажется на скорости.
0
ct0r
Игогошка!
1789 / 690 / 44
Регистрация: 19.08.2012
Сообщений: 1,339
Завершенные тесты: 1
29.07.2015, 23:10 #20
Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл.

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

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

Так как у нас там числа, то можем сортировать за O(n).
0
29.07.2015, 23:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2015, 23:10

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

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

Быстрый способ получить бинарную запись числа
Здравствуйте, хотелось бы узнать самый быстрый способ получить бинарное...


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

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

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