Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
Butt-Head
Заблокирован
29.07.2015, 16:30     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #1
Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1 террабайт, если на компе, к примеру, доступно всего 2 гб оперативки ... ?
Ну файл с нитами типа:
1
2
3
4
6346546
234524234
656546546
24234234
777
654646
и тд



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

Добавлено через 4 часа 45 минут
Ну так что, никто не подскажет, как отсортировать 1 гиг в файле?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2015, 16:30     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Посмотрите здесь:

C++ Быстрый способ определения цвета пиксела координатам x, y
Самый быстрый способ посчитать сумма элементов матрицы, находящихся в матрице C++
C++ Считать квадратную матрицу. Какой самый быстрый способ это сделать?
Быстрый способ сравнить содержимое двух файлов C++
C++ Быстрый способ получение уникального ID
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Renji
1532 / 980 / 238
Регистрация: 05.06.2014
Сообщений: 2,950
30.07.2015, 08:20     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #21
Инты какие? Если 32-битовые, то читаем исходный файл и одним проходом строим табличку "сколько раз встречаются числа от 0 до 2^28-1" (счетчики в табличке 64-битовые). Как раз два гига и выжираем. На основе таблицы строим выходной файл. Алгоритм повторяем с диапазонами 2^28-(2^28)*2-1, (2^28)*2-(2^28)*3-1... Итого, укладываемся в шестнадцать проходов.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
PavelPol
21 / 21 / 10
Регистрация: 05.11.2014
Сообщений: 97
30.07.2015, 09:16     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #22
Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью?
1. Перегнать все числа в бинарный файл
2. Любым удобным вариантом сортировки генерировать новый файл на каждом шаге, а предыдущий удалять.
3. Преобразовать обратно в текстовый со строчным разделением.

ОЗУ будет играть роль буфера, для ускорения процесса. Считал 2 ГБ значений, провел сравнения среди них, считал следующие.
Renji
1532 / 980 / 238
Регистрация: 05.06.2014
Сообщений: 2,950
30.07.2015, 09:22     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #23
Цитата Сообщение от PavelPol Посмотреть сообщение
Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью?
Потому что:
1) Попытка прочитать с диска один байт влечет за собой чтение 512 байтового сектора. А то целого кластера таких секторов. И скорость работы алгоритма падает на порядки.
2) Это чтение еще и происходит на порядки медленнее чем из памяти. И скорость работы алгоритма падает еще на несколько порядков.

В итоге алгоритм может работать аккурат до новогодних праздников. Оно нам надо?
Butt-Head
Заблокирован
30.07.2015, 10:06  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #24
Цитата Сообщение от 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
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 11:21     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #25
Цитата Сообщение от Butt-Head Посмотреть сообщение
Ну и что это даёт?
Ты неправильно понял идею. допустим есть последовательность цифр от 0 до 9: 314159265358,
мы можем для каждой возможной цифры подчитать сколько раз она встречается: [0, 2, 1, 2, 1, 3, 1, 0, 1, 1]
вот на базе такой таблицы отсортированный массив восстанавливается элементарно. Но это только для случая, когда значения ограничены.

Добавлено через 1 минуту
Этот способ будет работать быстрее моего варианта, но нужно удостовериться, что инты ограничены.
Butt-Head
Заблокирован
30.07.2015, 11:33  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #26
Цитата Сообщение от shmkv Посмотреть сообщение
сколько раз она встречается: [0, 2, 1, 2, 1, 3, 1, 0, 1, 1]
И как из этого восстановить массив?

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

Добавлено через 3 минуты
Ааа ердить раскодрить, кажется меня осенило.
Мы ж как бы восстанавливаем не исходный массив (а то бы это был наикрутейший способ архивирования ), а отсортированный массив ...
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 11:42     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #27
ОМГ. Задача-то школьная.
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  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #28
Так, ну вот допустим, int-ы 32-х битные. Но как быть со счётчиками, всё в памяти я так полагаю опять же не удержишь ...
В случае 32-х битный интов, у нас значения от 0 до 2^32, то есть до 4294967296.
В 1 террабайте могут быть и все одинаковые числа, так что максимальное кол-во повторов:
1 Тб = 1099511627776 байт
1 int нынче = 4 байта.
максимальное кол-во int-ов в исходном файле: 1099511627776 / 4 = 274877906944
Для записи такого числа, нам необходима 64-х битная переменная.
То есть фактический, для таблицы повторов нам нужно:
8 байт * 4294967296 (кол-во возможных цифр в 32-х битных интах) = 34359738368 байт = 32 гигабайта ...
Вот и приплыли ...
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 11:46     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #29
Цитата Сообщение от 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  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #30
Ну я понял, что нужно будет просто добирать до двух гигов и свопить на хард, потом опять и опять...
А потом эти файлы по очереди читать и восстанавливать отсортированный массив...
Но скорость тут будет конечно... Ведь ты когда анализируешь исходный файл, там числа могут попадаться совершенно из разных диапазонов и тут, либо 32/2 = 16 раз пробегаться по всему файлу, либо мерджить файлы эти мелкие...
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 11:53     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #31
Цитата Сообщение от Butt-Head Посмотреть сообщение
либо 32/2 = 16 раз пробегаться по всему файлу
Без либо.
Butt-Head
Заблокирован
30.07.2015, 11:56  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #32
Цитата Сообщение от shmkv Посмотреть сообщение
Без либо.
Всё. Идею понял. Всем спасибо.

Единственное что, как на ваш взгляд, это самый быстрый способ?
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 12:02     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #33
Цитата Сообщение от Butt-Head Посмотреть сообщение
Единственное что, как на ваш взгляд, это самый быстрый способ?
Скорее всего да. Только убедись, что инты 32х битные.
Butt-Head
Заблокирован
30.07.2015, 12:11  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #34
Цитата Сообщение от shmkv Посмотреть сообщение
Скорее всего да. Только убедись, что инты 32х битные.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 13:04     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #35
Действительно, всего лишь 16 проходов... Итого читаем 16 Тб и пишем 1 Тб.
А в другом варианте - читаем 2 Тб и пишем 2 Тб (пусть и не совсем последовательно, но все равно блоками).
И что быстрее? 16 проходов?
Butt-Head
Заблокирован
30.07.2015, 13:12  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #36
Цитата Сообщение от ct0r Посмотреть сообщение
И что быстрее? 16 проходов?
Где читаем два и пишем два, это ты про external merge sort ? Так там скорость ваще на нуле будет ...
Eraston
 Аватар для Eraston
53 / 10 / 2
Регистрация: 09.09.2014
Сообщений: 123
30.07.2015, 13:17     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #37
Цитата Сообщение от ct0r Посмотреть сообщение
Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл.
Как так сразу сливаем? Просто открываем все файлы. У каждого файла есть итератор на текущее число в нем. Выбираем наименьшее число среди всех итераторов. Пишем его в результирующий файл. Сдвигаем этот итератор на следующее число в этом файле. Снова выбираем наименьшее число среди итераторов. И так далее, пока все итераторы не дойдут до конца своих файлов.
Это самый простой и очевидный метод. Его можно оптимизировать. Например, читать из каждого файла не по одному числу, а пачками.
Так как у нас там числа, то можем сортировать за O(n).
Первый проход 1 Тб: считать и записать с сортировкой 1Тб блоками (например, 1024 блока по 1 Гб)
Второй проход 1 Тб: считать из блоков (1024 файловых стрима) с выборкой (очередное наименьшее значение из 1024) 1Тб и записать в 1 Тб
Итого:
Цитата Сообщение от ct0r Посмотреть сообщение
читаем 2 Тб и пишем 2 Тб (пусть и не совсем последовательно, но все равно блоками)
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 13:23     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #38
Цитата Сообщение от Butt-Head Посмотреть сообщение
Где читаем два и пишем два, это ты про external merge sort ? Так там скорость ваще на нуле будет ...
Объясняю еще раз.
1) Читаем исходный файл пачками в 2 Гб. Сразу сортируем (сортировка быстрая, за О(n), как раз методом подсчета например). Пишем отсортированную пачку в файл. Получаем N=1Тб/2Гб файлов.
2) Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб. Сразу их сливаем и пишем в выходной файл. Все.

Добавлено через 4 минуты
Butt-Head, ты вообще представляешь, сколько времени займет 16 проходов 1 Тб файла на машине с 2 Гб ОЗУ? Так вот - просто дофига и больше. У нас в задаче узкое место совсем не сортировка, а чтение и запись с диска.
Eraston
 Аватар для Eraston
53 / 10 / 2
Регистрация: 09.09.2014
Сообщений: 123
30.07.2015, 13:35     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #39
Цитата Сообщение от ct0r Посмотреть сообщение
Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб
То уже смахивает на многопоточность, когда пока 1 поток сортирует, 2ой пишет отсортированный массив, ибо из файлов-блоков без сортировки на выходе неотсортированный массив.
Цитата Сообщение от ct0r Посмотреть сообщение
Пишем отсортированную пачку в файл. Получаем N=1Тб/2Гб файлов.
И пишем в бинарном формате.

Добавлено через 2 минуты
Цитата Сообщение от Eraston Посмотреть сообщение
когда пока 1 поток сортирует, 2ой пишет отсортированный массив
А сортировать больше чем ( N = 1 Тб / размер_блока = количество файлов-блоков ) элементов мы не можем
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 13:38     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Еще ссылки по теме:

C++ Работа с бинарными файлами: какой способ работает наиболее быстро при записи и считывании?
C++ Memory shift или самый быстрый способ перемещения блока памяти
C++ Самый быстрый способ решения задачи a+b

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

Или воспользуйтесь поиском по форуму:
Butt-Head
Заблокирован
30.07.2015, 13:38  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #40
Цитата Сообщение от ct0r Посмотреть сообщение
Читаем исходный файл пачками в 2 Гб. Сразу сортируем
Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?
Цитата Сообщение от ct0r Посмотреть сообщение
Пишем отсортированную пачку в файл
В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?

Цитата Сообщение от ct0r Посмотреть сообщение
Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб. Сразу их сливаем и пишем в выходной файл.
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Yandex
Объявления
30.07.2015, 13:38     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Ответ Создать тему
Опции темы

Текущее время: 14:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru