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

@~~Butt-Head~~ · 29.07.2015, 16:30. **Показов** 25253. **Ответов** 85

Author24 — интернет-сервис помощи студентам

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

1
2
3
4
6346546
234524234
656546546
24234234
777
654646

и тд

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

Добавлено через 4 часа 45 минут
Ну так что, никто не подскажет, как отсортировать 1 гиг в файле?

@nmcf · 29.07.2015, 18:01

Файл текстовый?

@~~Butt-Head~~ · 29.07.2015, 21:14 **[ТС]**

Сообщение от 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 · 29.07.2015, 21:27

Butt-Head, ну я бы сделал как-то так:
1.В цикле до конца файла:
1.1 Считать инты, сколько гарантированно влезет в память.
2.2. Отсортировать их быстрой сортировкой.
2.3 записать фрагмент во временный файл (обязательно в двоичном виде) с уникальным именем для (для фрагмента).
2. Последовательно попарно объединят файлы сортировкой слиянием. Когда останется 2 фрагмента - сливаешь в один текстовый.

@~~Butt-Head~~ · 29.07.2015, 21:36 **[ТС]**

Сообщение от shmkv

Последовательно попарно объединят файлы сортировкой слиянием. Когда останется 2 фрагмента - сливаешь в один текстовый.

Объединять какие фалы?

@nmcf · 29.07.2015, 21:37

Вот была тема: Сортировка больших текстовых файлов размером до двух терабайт

@castaway · 29.07.2015, 21:44

Сообщение от Butt-Head

Объединять какие фалы?

Сообщение от shmkv

2.3 записать фрагмент во временный файл

...

@~~Butt-Head~~ · 29.07.2015, 21:51 **[ТС]**

nmcf, я не очень въехал в чём там ваще фокус ...
Ну открыл ты кучу потоков, о одной строчке читаешь из каждого потока и пишешь в финальный поток...
Бред какой - то.
А что - то не помню, файловый поток в памяти занимает размер файлы или нет?
Вот тут нашёл кое что, но не понял суть опять же http://stackoverflow.com/quest... -hard-disk

Добавлено через 1 минуту

Сообщение от castaway

записать фрагмент во временный файл

Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.

Как вообще, пусть даже не быстро, отсортировать файл в 1 террабайт?

@iRomul · 29.07.2015, 21:56

Вот тут есть информация по теме + код,, можете глянуть

@castaway · 29.07.2015, 22:01

Сообщение от Butt-Head

Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.

Я никак не буду обходить. Мне эта задача не интересна. Я лишь цитировал сообщение пользователя shmkv, которое ты пропустил.

@smartpointer · 29.07.2015, 22:09

Почему то хотел изначально отговорить от MergeSort, поскольку она требовательна к памяти, но видимо в данном случае без нее никак, кстати можно взять немного оптимизации из TimSort при склеивании двух фрагментов, в случае постоянного извлечения из одного подмассива брать следущий элемент галопом, так можно записывать в исходный массив целыми кусками.

@~~Butt-Head~~ · 29.07.2015, 22:21 **[ТС]**

Сообщение от castaway

Я никак не буду обходить. Мне эта задача не интересна

Сама вакансия мне если честно то же не очень интересна, вот этот вопрос мне стал интересен чисто по профессиональному.
Интересно, может быть можно как - то вообще без вспомогательный файлов?

@castaway · 29.07.2015, 22:43

Сообщение от Butt-Head

Интересно, может быть можно как - то вообще без вспомогательный файлов?

Как вариант, алгоритм исключительно для WinAPI и для двоичного файла:

C++

    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 **[ТС]**

Сообщение от castaway

Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ.

Хмм... Я в принципе знал про это, но конечно же хотелось чего - то кроссового. Ну да ладно, для кроссового я так понял нужно External Merge Sort
Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. ..
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт

shmkv · 29.07.2015, 22:54

Сообщение от Butt-Head

Объединять какие фалы?

Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.

Добавлено через 1 минуту

Сообщение от Butt-Head

Непонятно, как ты обойдёшь ограничение в 2 гб оперативки.

Сообщение от shmkv

Считать инты, сколько гарантированно влезет в память

...

@~~Butt-Head~~ · 29.07.2015, 22:57 **[ТС]**

Сообщение от 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 · 29.07.2015, 22:58

Сообщение от Butt-Head

ожет быть можно как - то вообще без вспомогательный файлов?

Можно, но будет ооочень долго.

Добавлено через 1 минуту

Сообщение от Butt-Head

Подгружать весь merg1

Чтобы сливать совсем необязательно грузить файл целиком.

@castaway · 29.07.2015, 23:01

Сообщение от Butt-Head

Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. ..

Его размер не меняется. Зачем его считать?

Сообщение от Butt-Head

И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт

Детали не знаю. Может и упадёт.

shmkv · 29.07.2015, 23:01

Сообщение от Butt-Head

как это проекция физический работает, что - то я не пойму

Да работает она просто - при обращении к памяти #PF генерируется и ОС по этому адресу страницу из файла подгружает. Сам я никогда не использовал эту технологию. Но чудес-то не бывает, если памяти жрет мало, значит постоянно тасует страницы между диском и озу, что не особо благоприятно скажется на скорости.

@ct0r · 29.07.2015, 23:10

Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл.

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

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

Так как у нас там числа, то можем сортировать за O(n).

@~~Butt-Head~~ Заблокирован
	29.07.2015, 22:21 [ТС]	12
	Сообщение от castaway Я никак не буду обходить. Мне эта задача не интересна Сама вакансия мне если честно то же не очень интересна, вот этот вопрос мне стал интересен чисто по профессиональному. Интересно, может быть можно как - то вообще без вспомогательный файлов? 0

shmkv 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	29.07.2015, 23:01	19
	Сообщение от Butt-Head как это проекция физический работает, что - то я не пойму Да работает она просто - при обращении к памяти #PF генерируется и ОС по этому адресу страницу из файла подгружает. Сам я никогда не использовал эту технологию. Но чудес-то не бывает, если памяти жрет мало, значит постоянно тасует страницы между диском и озу, что не особо благоприятно скажется на скорости. 0

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

Решение

Решение

Решение

@nmcf 7793 / 6560 / 2984 Регистрация: 14.04.2014 Сообщений: 28,672
	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 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	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 7793 / 6560 / 2984 Регистрация: 14.04.2014 Сообщений: 28,672
	29.07.2015, 21:37	6
	Сообщение было отмечено Butt-Head как решение Решение Вот была тема: Сортировка больших текстовых файлов размером до двух терабайт 1

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	29.07.2015, 21:44	7
	Сообщение от Butt-Head Объединять какие фалы? Сообщение от shmkv 2.3 записать фрагмент во временный файл ... 1

@~~Butt-Head~~ Заблокирован
	29.07.2015, 21:51 [ТС]	8
	nmcf, я не очень въехал в чём там ваще фокус ... Ну открыл ты кучу потоков, о одной строчке читаешь из каждого потока и пишешь в финальный поток... Бред какой - то. А что - то не помню, файловый поток в памяти занимает размер файлы или нет? Вот тут нашёл кое что, но не понял суть опять же http://stackoverflow.com/quest... -hard-disk Добавлено через 1 минуту Сообщение от castaway записать фрагмент во временный файл Непонятно, как ты обойдёшь ограничение в 2 гб оперативки. Как вообще, пусть даже не быстро, отсортировать файл в 1 террабайт? 0

@iRomul 163 / 104 / 14 Регистрация: 17.10.2012 Сообщений: 488
	29.07.2015, 21:56	9
	Сообщение было отмечено Butt-Head как решение Решение Вот тут есть информация по теме + код,, можете глянуть 1

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	29.07.2015, 22:01	10
	Сообщение от Butt-Head Непонятно, как ты обойдёшь ограничение в 2 гб оперативки. Я никак не буду обходить. Мне эта задача не интересна. Я лишь цитировал сообщение пользователя shmkv, которое ты пропустил. 0

@smartpointer 70 / 64 / 40 Регистрация: 17.02.2014 Сообщений: 265
	29.07.2015, 22:09	11
	Сообщение было отмечено Butt-Head как решение Решение Почему то хотел изначально отговорить от MergeSort, поскольку она требовательна к памяти, но видимо в данном случае без нее никак, кстати можно взять немного оптимизации из TimSort при склеивании двух фрагментов, в случае постоянного извлечения из одного подмассива брать следущий элемент галопом, так можно записывать в исходный массив целыми кусками. 0

	29.07.2015, 23:10

@~~Butt-Head~~ Заблокирован
	29.07.2015, 22:51 [ТС]	14
	Сообщение от castaway Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ. Хмм... Я в принципе знал про это, но конечно же хотелось чего - то кроссового. Ну да ладно, для кроссового я так понял нужно External Merge Sort Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. .. И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт 0

shmkv 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	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 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	29.07.2015, 22:58	17
	Сообщение от Butt-Head ожет быть можно как - то вообще без вспомогательный файлов? Можно, но будет ооочень долго. Добавлено через 1 минуту Сообщение от Butt-Head Подгружать весь merg1 Чтобы сливать совсем необязательно грузить файл целиком. 0

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	29.07.2015, 23:01	18
	Сообщение от Butt-Head Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. .. Его размер не меняется. Зачем его считать? Сообщение от Butt-Head И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт Детали не знаю. Может и упадёт. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	29.07.2015, 23:10	20
	Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл. Как так сразу сливаем? Просто открываем все файлы. У каждого файла есть итератор на текущее число в нем. Выбираем наименьшее число среди всех итераторов. Пишем его в результирующий файл. Сдвигаем этот итератор на следующее число в этом файле. Снова выбираем наименьшее число среди итераторов. И так далее, пока все итераторы не дойдут до конца своих файлов. Это самый простой и очевидный метод. Его можно оптимизировать. Например, читать из каждого файла не по одному числу, а пачками. Так как у нас там числа, то можем сортировать за O(n). 0