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

@Mindc0d3 · Регистрация: 24.01.2014

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

Собственно стоит задача отсортировать большой текстовый файл (до 2тб) состоящий из строк длинной менее 100 символов. Решил разбить файл по частям (скажем по 2гб), отсортировать их, а потом получившиеся отсортированные .tmp файлы (порядка 1к файлов) склеить воедино. Завис на этапе склейки. Подскажите, как организовывать склейку отсортированных файлов? Гугл сказал что через merge sort но ведь на выходе у нас все равно получится 2 огромных файла по 1тб которые мы в итоге не сможем поместить в память, не могу уловить суть в склейке этим методом.

@some_name · 20.08.2014, 01:30

А кто сказал, что отсортировав по отдельности части по 2 гб и после склейки их, вы получите отсортированный файл 2тб.
Пример
Нужно отсортировать последовательность: 6 4 2 8 3 0 1 7 5 9.
Я разбиваю ее на 2 части: 1) 6 4 2 8 3 и 2) 0 1 7 5 9.
Сортирую их : 1) 2 3 4 6 8 и 2) 0 1 5 7 9
Склеиваю : 2 3 4 6 8 0 1 5 7 9
Разве это верно?
Поправьте, если я не прав?

@kolorotur · 20.08.2014, 02:20

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

А кто сказал, что отсортировав по отдельности части по 2 гб и после склейки их, вы получите отсортированный файл 2тб.

Так автор же и сказал

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

Решил разбить файл по частям (скажем по 2гб), отсортировать их, а потом получившиеся отсортированные .tmp файлы (порядка 1к файлов) склеить воедино. Завис на этапе склейки.

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

Гугл сказал что через merge sort но ведь на выходе у нас все равно получится 2 огромных файла по 1тб которые мы в итоге не сможем поместить в память

Так а их и не обязательно в памяти все держать.

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

не могу уловить суть в склейке этим методом.

Допустим, у вас имеется n отсортированных файлов, которые надо слепить воедино.
1. Открывайте FileStream на финальный файл
2. Открывайте n FileStream'ов — по одному на каждый из мелких отсортированных файлов.
3. Считывайте по одной строчке из каждого файла.
4. Найдите строчку, которая "меньше" всех остальных.
5. Запишите эту строчку в финальный файл.
6. Найдите FileStream, из которого вы считали эту строчку
7. Считайте следующую строчку из этого же потока.
8. Если строчек больше нет, то закройте этот поток и удалите временный файл.
9. Если все файлы были закрыты и удалены, то работа завершена, закройте поток в финальный файл.
10. В противном случае goto 4.

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@Mindc0d3 0 / 0 / 0 Регистрация: 24.01.2014 Сообщений: 5

	Сортировка больших текстовых файлов размером до двух терабайт 20.08.2014, 01:03. Показов 13487. Ответов 2 Метки нет (Все метки) Собственно стоит задача отсортировать большой текстовый файл (до 2тб) состоящий из строк длинной менее 100 символов. Решил разбить файл по частям (скажем по 2гб), отсортировать их, а потом получившиеся отсортированные .tmp файлы (порядка 1к файлов) склеить воедино. Завис на этапе склейки. Подскажите, как организовывать склейку отсортированных файлов? Гугл сказал что через merge sort но ведь на выходе у нас все равно получится 2 огромных файла по 1тб которые мы в итоге не сможем поместить в память, не могу уловить суть в склейке этим методом. 0

@some_name Вежливость-главное оружие 233 / 234 / 86 Регистрация: 19.02.2013 Сообщений: 1,446
	20.08.2014, 01:30
	А кто сказал, что отсортировав по отдельности части по 2 гб и после склейки их, вы получите отсортированный файл 2тб. Пример Нужно отсортировать последовательность: 6 4 2 8 3 0 1 7 5 9. Я разбиваю ее на 2 части: 1) 6 4 2 8 3 и 2) 0 1 7 5 9. Сортирую их : 1) 2 3 4 6 8 и 2) 0 1 5 7 9 Склеиваю : 2 3 4 6 8 0 1 5 7 9 Разве это верно? Поправьте, если я не прав? 0