Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
Butt-Head
Заблокирован
#1

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

29.07.2015, 16:30. Просмотров 3868. Ответов 85
Метки нет (Все метки)

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



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

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

Наиболее быстрый способ сравнения двух экземпляров структур на предмет одинаковости их полей
Есть структура, в которой есть несколько int-ов и char-ов, какой имеется...

Memory shift или самый быстрый способ перемещения блока памяти
int* dataField = new int{0}; for (int i = 0; i < 50; i++) dataField = 777; ...

Работа с бинарными файлами: какой способ работает наиболее быстро при записи и считывании?
Всем привет прошу помощи по этой теме. Попробую изложить кратко: 1) Есть не...

Быстрый способ получение уникального ID
Есть какой - то список уже существующих уникальных ID, нужно наибыстрейшим...

Самый быстрый способ решения задачи a+b
несколько раз ходил на олимпиады, во многих из них в пробном туре даётся задача...

Быстрый способ сравнить содержимое двух файлов
Здравствуйте, подскажите наиболее быстрый способ сравнить содержимое двух...

85
Renji
2140 / 1499 / 456
Регистрация: 05.06.2014
Сообщений: 4,337
30.07.2015, 08:20 #21
Инты какие? Если 32-битовые, то читаем исходный файл и одним проходом строим табличку "сколько раз встречаются числа от 0 до 2^28-1" (счетчики в табличке 64-битовые). Как раз два гига и выжираем. На основе таблицы строим выходной файл. Алгоритм повторяем с диапазонами 2^28-(2^28)*2-1, (2^28)*2-(2^28)*3-1... Итого, укладываемся в шестнадцать проходов.
3
PavelPol
52 / 52 / 31
Регистрация: 05.11.2014
Сообщений: 241
30.07.2015, 09:16 #22
Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью?
1. Перегнать все числа в бинарный файл
2. Любым удобным вариантом сортировки генерировать новый файл на каждом шаге, а предыдущий удалять.
3. Преобразовать обратно в текстовый со строчным разделением.

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

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

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

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

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

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

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

Добавлено через 2 минуты
Цитата Сообщение от Eraston Посмотреть сообщение
когда пока 1 поток сортирует, 2ой пишет отсортированный массив
А сортировать больше чем ( N = 1 Тб / размер_блока = количество файлов-блоков ) элементов мы не можем
0
Butt-Head
Заблокирован
30.07.2015, 13:38  [ТС] #40
Цитата Сообщение от ct0r Посмотреть сообщение
Читаем исходный файл пачками в 2 Гб. Сразу сортируем
Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?
Цитата Сообщение от ct0r Посмотреть сообщение
Пишем отсортированную пачку в файл
В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?

Цитата Сообщение от ct0r Посмотреть сообщение
Одновременно читаем из N файлов пачками так, чтобы у нас были постоянно заняты 2 Гб. Сразу их сливаем и пишем в выходной файл.
А это в сумме не будет равно 16-м проходам по террабайту случаем?
0
30.07.2015, 13:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 13:38
Привет! Вот еще темы с решениями:

Быстрый способ определения цвета пиксела координатам x, y
В общем задача такая , нужен быстрый способ определения цвета пиксела в...

Быстрый способ получить бинарную запись числа
Здравствуйте, хотелось бы узнать самый быстрый способ получить бинарное...

Наиболее быстрый способ склеивания фрагментов файла
Имеется несколько фрагментов одного файла. Требуется собрать эти фрагменты в...

Наиболее быстрый способ записи в консоль
Какой наиболее быстрый способ отрисовки символов в консоли, если использовать...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru