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

@Butt-Head · 29.07.2015, 16:30. **Показов** 30781. **Ответов** 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-м проходам по террабайту случаем?

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

@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