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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
Butt-Head
Заблокирован
#1

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

29.07.2015, 16:30. Просмотров 3334. Ответов 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++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Butt-Head
Заблокирован
29.07.2015, 22:57  [ТС] #16
Цитата Сообщение от shmkv Посмотреть сообщение
Временные. Сливаешь попарно. В итоге образуется в 2 разв меньше файлов, но каждый файл в 2 раза большего размера.
Смотри. Вот есть у тебя три куска:
Первый: 0,7,3 [допустим размер 1 гб]
Второй: 4,2,8 [допустим размер 1 гб]
Третий: 9,0,8 [допустим размер 1 гб]

sort первых двух:
Первый: 0,3,7
Второй: 2,4,8

смерджил их:
merge1: 0,2,3,4,7,8 [2 гб]

что ты дальше будешь делать? Подгружать весь merg1 в память и сливать его с третьим куском? Тогда у тебя этот мердж кусок будет расти как на дрожжах и привет пямять ...
0
shmkv
580 / 294 / 39
Регистрация: 21.07.2015
Сообщений: 880
29.07.2015, 22:58 #17
Цитата Сообщение от Butt-Head Посмотреть сообщение
ожет быть можно как - то вообще без вспомогательный файлов?
Можно, но будет ооочень долго.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
Подгружать весь merg1
Чтобы сливать совсем необязательно грузить файл целиком.
0
castaway
Эксперт С++
4884 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
29.07.2015, 23:01 #18
Цитата Сообщение от Butt-Head Посмотреть сообщение
Слушай, а по поводу Mapped файлов в WinApi, как то можно просчитать размер будущего проецируемого файла? Ну вот, допустим, какой объём потребуется для 1 Tb. ..
Его размер не меняется. Зачем его считать?

Цитата Сообщение от Butt-Head Посмотреть сообщение
И вообще, как эта проекция физический работает, что - то я не пойму ... Небойсь через кеш в файл подкачки самой винды и на террабайте просто упадёт
Детали не знаю. Может и упадёт.
0
shmkv
580 / 294 / 39
Регистрация: 21.07.2015
Сообщений: 880
29.07.2015, 23:01 #19
Цитата Сообщение от Butt-Head Посмотреть сообщение
как это проекция физический работает, что - то я не пойму
Да работает она просто - при обращении к памяти #PF генерируется и ОС по этому адресу страницу из файла подгружает. Сам я никогда не использовал эту технологию. Но чудес-то не бывает, если памяти жрет мало, значит постоянно тасует страницы между диском и озу, что не особо благоприятно скажется на скорости.
0
ct0r
Игогошка!
1773 / 675 / 42
Регистрация: 19.08.2012
Сообщений: 1,287
Завершенные тесты: 1
29.07.2015, 23:10 #20
Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл.

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

Это самый простой и очевидный метод. Его можно оптимизировать. Например, читать из каждого файла не по одному числу, а пачками.

Так как у нас там числа, то можем сортировать за O(n).
0
Renji
1917 / 1315 / 298
Регистрация: 05.06.2014
Сообщений: 3,758
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
39 / 39 / 16
Регистрация: 05.11.2014
Сообщений: 186
30.07.2015, 09:16 #22
Если в задаче нет ограничения на размер временных файлов и время выполнения, почему бы просто не работать с ними как с оперативной памятью?
1. Перегнать все числа в бинарный файл
2. Любым удобным вариантом сортировки генерировать новый файл на каждом шаге, а предыдущий удалять.
3. Преобразовать обратно в текстовый со строчным разделением.

ОЗУ будет играть роль буфера, для ускорения процесса. Считал 2 ГБ значений, провел сравнения среди них, считал следующие.
1
Renji
1917 / 1315 / 298
Регистрация: 05.06.2014
Сообщений: 3,758
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
580 / 294 / 39
Регистрация: 21.07.2015
Сообщений: 880
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
580 / 294 / 39
Регистрация: 21.07.2015
Сообщений: 880
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
580 / 294 / 39
Регистрация: 21.07.2015
Сообщений: 880
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 11:50
Привет! Вот еще темы с ответами:

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

Наиболее быстрый способ склеивания фрагментов файла - C#
Имеется несколько фрагментов одного файла. Требуется собрать эти фрагменты в исходный файл. Размеры фрагментов могут быть разными, от...

Наиболее быстрый способ забрать данные из html - C# ASP.NET
Мне нужно забрать данные с вебстранички. Там может содержаться просто одно слово, например &quot;ОК&quot;, в этом случае использую следующую...

Наиболее быстрый способ работы с файлом Excel (около 20000 строк) - C#
Здравствуйте ребята, хотел спросить у вас совета. Есть программа по распечатке ценников по артикулу или штрихкоду товара. Какой обработкой...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.07.2015, 11:50
Ответ Создать тему
Опции темы

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