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

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

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

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

1
2
3
4
6346546
234524234
656546546
24234234
777
654646

и тд

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

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

@Renji · 30.07.2015, 08:20

Инты какие? Если 32-битовые, то читаем исходный файл и одним проходом строим табличку "сколько раз встречаются числа от 0 до 2^28-1" (счетчики в табличке 64-битовые). Как раз два гига и выжираем. На основе таблицы строим выходной файл. Алгоритм повторяем с диапазонами 2^28-(2^28)*2-1, (2^28)*2-(2^28)*3-1... Итого, укладываемся в шестнадцать проходов.

@PavelPol · 30.07.2015, 09:16

Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью?
1. Перегнать все числа в бинарный файл
2. Любым удобным вариантом сортировки генерировать новый файл на каждом шаге, а предыдущий удалять.
3. Преобразовать обратно в текстовый со строчным разделением.

ОЗУ будет играть роль буфера, для ускорения процесса. Считал 2 ГБ значений, провел сравнения среди них, считал следующие.

@Renji · 30.07.2015, 09:22

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

Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью?

Потому что:
1) Попытка прочитать с диска один байт влечет за собой чтение 512 байтового сектора. А то целого кластера таких секторов. И скорость работы алгоритма падает на порядки.
2) Это чтение еще и происходит на порядки медленнее чем из памяти. И скорость работы алгоритма падает еще на несколько порядков.

В итоге алгоритм может работать аккурат до новогодних праздников. Оно нам надо?

@Butt-Head · 30.07.2015, 10:06 **[ТС]**

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

и время выполнения

По скорости ограничение есть. См название треда: Наиболее быстрый способ ...

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

Инты какие?

Судя по оригиналу вопроса:
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?
не ясно, ну пусть будут 32-х битные...

Нельзя ли поподробнее:

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

"сколько раз встречаются числа от 0 до 2^28-1"

Встречаются где? В исходном файле? Ну ок, читаешь ты кусок в 2 гига из файла в оперативку. Дальше пробегаешь по этим данным и смотришь, сколько раз там встречаются int-ы от 0 до 2^28-1 ?

Но зачем чёрт возьми?
Допустим, исходный файл:
3
56564
8
5556
8
3
5

Получаем:
3 - встречается 2 раза
56564 - встречается 1 раз
8 - встречается 2 раза
5556 - встречается 1 раз

Ну и что это даёт?

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

счетчики в табличке 64-битовые

какие ещё счётчики?

shmkv · 30.07.2015, 11:21

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

Ну и что это даёт?

Ты неправильно понял идею. допустим есть последовательность цифр от 0 до 9: 314159265358,
мы можем для каждой возможной цифры подчитать сколько раз она встречается: [0, 2, 1, 2, 1, 3, 1, 0, 1, 1]
вот на базе такой таблицы отсортированный массив восстанавливается элементарно. Но это только для случая, когда значения ограничены.

Добавлено через 1 минуту
Этот способ будет работать быстрее моего варианта, но нужно удостовериться, что инты ограничены.

@Butt-Head · 30.07.2015, 11:33 **[ТС]**

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

сколько раз она встречается: [0, 2, 1, 2, 1, 3, 1, 0, 1, 1]

И как из этого восстановить массив?

А если в исходном террабайтном файле будут все инты одинаковые?

Добавлено через 3 минуты
Ааа ердить раскодрить, кажется меня осенило.
Мы ж как бы восстанавливаем не исходный массив (а то бы это был наикрутейший способ архивирования

), а отсортированный массив ...

shmkv · 30.07.2015, 11:42

ОМГ. Задача-то школьная.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
#include <limits>
int main()
{
    unsigned char arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8};
    const unsigned uchar_sz = (unsigned)std::numeric_limits<unsigned char>::max() + 1;
    unsigned arr_cnt[uchar_sz];
    std::fill(arr_cnt, arr_cnt + uchar_sz, 0);
    for(unsigned char val : arr)
        arr_cnt[val]++;
    for(unsigned val = 0; val < uchar_sz; val++)
        while(arr_cnt[val]-- > 0)
            std::cout << val << ' ';
   return 0;
}

@Butt-Head · 30.07.2015, 11:43 **[ТС]**

Так, ну вот допустим, int-ы 32-х битные. Но как быть со счётчиками, всё в памяти я так полагаю опять же не удержишь ...
В случае 32-х битный интов, у нас значения от 0 до 2^32, то есть до 4294967296.
В 1 террабайте могут быть и все одинаковые числа, так что максимальное кол-во повторов:
1 Тб = 1099511627776 байт
1 int нынче = 4 байта.
максимальное кол-во int-ов в исходном файле: 1099511627776 / 4 = 274877906944
Для записи такого числа, нам необходима 64-х битная переменная.
То есть фактический, для таблицы повторов нам нужно:
8 байт * 4294967296 (кол-во возможных цифр в 32-х битных интах) = 34359738368 байт = 32 гигабайта ...
Вот и приплыли ...

shmkv · 30.07.2015, 11:46

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

Вот и приплыли ...

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

Инты какие? Если 32-битовые, то читаем исходный файл и одним проходом строим табличку "сколько раз встречаются числа от 0 до 2^28-1" (счетчики в табличке 64-битовые). Как раз два гига и выжираем. На основе таблицы строим выходной файл. Алгоритм повторяем с диапазонами 2^28-(2^28)*2-1, (2^28)*2-(2^28)*3-1... Итого, укладываемся в шестнадцать проходов.

!!!

@Butt-Head · 30.07.2015, 11:50 **[ТС]**

Ну я понял, что нужно будет просто добирать до двух гигов и свопить на хард, потом опять и опять...
А потом эти файлы по очереди читать и восстанавливать отсортированный массив...
Но скорость тут будет конечно... Ведь ты когда анализируешь исходный файл, там числа могут попадаться совершенно из разных диапазонов и тут, либо 32/2 = 16 раз пробегаться по всему файлу, либо мерджить файлы эти мелкие...

shmkv · 30.07.2015, 11:53

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

либо 32/2 = 16 раз пробегаться по всему файлу

Без либо.

@Butt-Head · 30.07.2015, 11:56 **[ТС]**

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

Без либо.

Всё. Идею понял. Всем спасибо.

Единственное что, как на ваш взгляд, это самый быстрый способ?

shmkv · 30.07.2015, 12:02

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

Единственное что, как на ваш взгляд, это самый быстрый способ?

Скорее всего да. Только убедись, что инты 32х битные.

@Butt-Head · 30.07.2015, 12:11 **[ТС]**

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

Скорее всего да. Только убедись, что инты 32х битные.

@ct0r · 30.07.2015, 13:04

Действительно, всего лишь 16 проходов... Итого читаем 16 Тб и пишем 1 Тб.
А в другом варианте - читаем 2 Тб и пишем 2 Тб (пусть и не совсем последовательно, но все равно блоками).
И что быстрее? 16 проходов?

@Butt-Head · 30.07.2015, 13:12 **[ТС]**

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

И что быстрее? 16 проходов?

Где читаем два и пишем два, это ты про external merge sort ? Так там скорость ваще на нуле будет ...

@Eraston · 30.07.2015, 13:17

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

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

Первый проход 1 Тб: считать и записать с сортировкой 1Тб блоками (например, 1024 блока по 1 Гб)
Второй проход 1 Тб: считать из блоков (1024 файловых стрима) с выборкой (очередное наименьшее значение из 1024) 1Тб и записать в 1 Тб
Итого:

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

читаем 2 Тб и пишем 2 Тб (пусть и не совсем последовательно, но все равно блоками)

@ct0r · 30.07.2015, 13:23

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

Где читаем два и пишем два, это ты про external merge sort ? Так там скорость ваще на нуле будет ...

Объясняю еще раз.
1) Читаем исходный файл пачками в 2 Гб. Сразу сортируем (сортировка быстрая, за О(n), как раз методом подсчета например). Пишем отсортированную пачку в файл. Получаем N=1Тб/2Гб файлов.
2) Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб. Сразу их сливаем и пишем в выходной файл. Все.

Добавлено через 4 минуты
Butt-Head, ты вообще представляешь, сколько времени займет 16 проходов 1 Тб файла на машине с 2 Гб ОЗУ? Так вот - просто дофига и больше. У нас в задаче узкое место совсем не сортировка, а чтение и запись с диска.

@Eraston · 30.07.2015, 13:35

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

Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб

То уже смахивает на многопоточность, когда пока 1 поток сортирует, 2ой пишет отсортированный массив, ибо из файлов-блоков без сортировки на выходе неотсортированный массив.

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

Пишем отсортированную пачку в файл. Получаем N=1Тб/2Гб файлов.

И пишем в бинарном формате.

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

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

когда пока 1 поток сортирует, 2ой пишет отсортированный массив

А сортировать больше чем ( N = 1 Тб / размер_блока = количество файлов-блоков ) элементов мы не можем

@Butt-Head · 30.07.2015, 13:38 **[ТС]**

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

Читаем исходный файл пачками в 2 Гб. Сразу сортируем

Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?

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

Пишем отсортированную пачку в файл

В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?

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

Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб. Сразу их сливаем и пишем в выходной файл.

А это в сумме не будет равно 16-м проходам по террабайту случаем?

Новые блоги и статьи Все статьи Все блоги /
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	30.07.2015, 08:20
	Инты какие? Если 32-битовые, то читаем исходный файл и одним проходом строим табличку "сколько раз встречаются числа от 0 до 2^28-1" (счетчики в табличке 64-битовые). Как раз два гига и выжираем. На основе таблицы строим выходной файл. Алгоритм повторяем с диапазонами 2^28-(2^28)2-1, (2^28)2-(2^28)*3-1... Итого, укладываемся в шестнадцать проходов. 3

@PavelPol 56 / 54 / 33 Регистрация: 05.11.2014 Сообщений: 259
	30.07.2015, 09:16
	Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью? 1. Перегнать все числа в бинарный файл 2. Любым удобным вариантом сортировки генерировать новый файл на каждом шаге, а предыдущий удалять. 3. Преобразовать обратно в текстовый со строчным разделением. ОЗУ будет играть роль буфера, для ускорения процесса. Считал 2 ГБ значений, провел сравнения среди них, считал следующие. 1

@Butt-Head Заблокирован
	30.07.2015, 11:43 [ТС]
	Так, ну вот допустим, int-ы 32-х битные. Но как быть со счётчиками, всё в памяти я так полагаю опять же не удержишь ... В случае 32-х битный интов, у нас значения от 0 до 2^32, то есть до 4294967296. В 1 террабайте могут быть и все одинаковые числа, так что максимальное кол-во повторов: 1 Тб = 1099511627776 байт 1 int нынче = 4 байта. максимальное кол-во int-ов в исходном файле: 1099511627776 / 4 = 274877906944 Для записи такого числа, нам необходима 64-х битная переменная. То есть фактический, для таблицы повторов нам нужно: 8 байт * 4294967296 (кол-во возможных цифр в 32-х битных интах) = 34359738368 байт = 32 гигабайта ... Вот и приплыли ... 0

@Butt-Head Заблокирован
	30.07.2015, 11:50 [ТС]
	Ну я понял, что нужно будет просто добирать до двух гигов и свопить на хард, потом опять и опять... А потом эти файлы по очереди читать и восстанавливать отсортированный массив... Но скорость тут будет конечно... Ведь ты когда анализируешь исходный файл, там числа могут попадаться совершенно из разных диапазонов и тут, либо 32/2 = 16 раз пробегаться по всему файлу, либо мерджить файлы эти мелкие... 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	30.07.2015, 13:04
	Действительно, всего лишь 16 проходов... Итого читаем 16 Тб и пишем 1 Тб. А в другом варианте - читаем 2 Тб и пишем 2 Тб (пусть и не совсем последовательно, но все равно блоками). И что быстрее? 16 проходов? 0