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

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

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

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

29.07.2015, 16:30. Просмотров 3529. Ответов 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++
Здравствуйте, подскажите наиболее быстрый способ сравнить содержимое двух текстовых файлов и вывести различия.

85
shmkv
603 / 317 / 41
Регистрация: 21.07.2015
Сообщений: 914
30.07.2015, 11:53 #31
Цитата Сообщение от Butt-Head Посмотреть сообщение
либо 32/2 = 16 раз пробегаться по всему файлу
Без либо.
1
Butt-Head
Заблокирован
30.07.2015, 11:56  [ТС] #32
Цитата Сообщение от shmkv Посмотреть сообщение
Без либо.
Всё. Идею понял. Всем спасибо.

Единственное что, как на ваш взгляд, это самый быстрый способ?
0
shmkv
603 / 317 / 41
Регистрация: 21.07.2015
Сообщений: 914
30.07.2015, 12:02 #33
Цитата Сообщение от Butt-Head Посмотреть сообщение
Единственное что, как на ваш взгляд, это самый быстрый способ?
Скорее всего да. Только убедись, что инты 32х битные.
0
Butt-Head
Заблокирован
30.07.2015, 12:11  [ТС] #34
Цитата Сообщение от shmkv Посмотреть сообщение
Скорее всего да. Только убедись, что инты 32х битные.
0
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,294
Завершенные тесты: 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
Сообщений: 127
30.07.2015, 13:17 #37
Цитата Сообщение от ct0r Посмотреть сообщение
Разбиваем на куски. Сортируем каждый кусок. Сразу сливаем все куски в выходной файл.
Как так сразу сливаем? Просто открываем все файлы. У каждого файла есть итератор на текущее число в нем. Выбираем наименьшее число среди всех итераторов. Пишем его в результирующий файл. Сдвигаем этот итератор на следующее число в этом файле. Снова выбираем наименьшее число среди итераторов. И так далее, пока все итераторы не дойдут до конца своих файлов.
Это самый простой и очевидный метод. Его можно оптимизировать. Например, читать из каждого файла не по одному числу, а пачками.
Так как у нас там числа, то можем сортировать за O(n).
Первый проход 1 Тб: считать и записать с сортировкой 1Тб блоками (например, 1024 блока по 1 Гб)
Второй проход 1 Тб: считать из блоков (1024 файловых стрима) с выборкой (очередное наименьшее значение из 1024) 1Тб и записать в 1 Тб
Итого:
Цитата Сообщение от ct0r Посмотреть сообщение
читаем 2 Тб и пишем 2 Тб (пусть и не совсем последовательно, но все равно блоками)
0
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,294
Завершенные тесты: 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
Сообщений: 127
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
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,294
Завершенные тесты: 1
30.07.2015, 13:43 #41
Цитата Сообщение от ct0r Посмотреть сообщение
сортировка быстрая, за О(n), как раз методом подсчета например
Прошу прощения, не методом подсчета конечно же (много памяти жрет, хороша когда диапазон возможных значений мал), а поразрядная (radix sort).

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

Добавлено через 3 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?
А как ты без их сортировки потом сливать в отсортированный файл будешь? Ты понимаешь, как делается это слияние?

Цитата Сообщение от Butt-Head Посмотреть сообщение
В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?
Нет. Отсортированный кусок.

Цитата Сообщение от Butt-Head Посмотреть сообщение
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Не будет. Можешь проверить.
0
Eraston
53 / 10 / 2
Регистрация: 09.09.2014
Сообщений: 127
30.07.2015, 13:46 #42
Цитата Сообщение от Butt-Head Посмотреть сообщение
Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?
Ты выбираешь из 1ых элементов файлов-блоков минимальный элемент. Смотри сам, что получится по твоему разумению, что "А зачем тут сортировка при записи в блоки?":
Блоки
1: 64 2
2: 32 1
3: 10 90

Выход
Ф: 10 32 1 64 2 90


Цитата Сообщение от Butt-Head Посмотреть сообщение
В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?
Блок элементов из исоходного файла отсортированный в пределах самого себя (блока, а не общей последовательности в исходном файле)

Цитата Сообщение от Butt-Head Посмотреть сообщение
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Цитата Сообщение от Eraston Посмотреть сообщение
Второй проход 1 Тб: считать из блоков (1024 файловых стрима
Цитата Сообщение от ct0r Посмотреть сообщение
Одновременно
) с выборкой (очередное наименьшее значение из 1024) 1Тб и записать в 1 Тб
1
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,294
Завершенные тесты: 1
30.07.2015, 13:54 #43
Цитата Сообщение от Butt-Head Посмотреть сообщение
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Впрочем облегчу тебе задачу - раз мы суммарно в них записали 1 Тб, то и считаем тоже 1 Тб

Butt-Head, для пущей убедительности добавлю, что код к абсолютно такой же задаче я писал в офисе Яндекса на собеседовании в 2011 году, - и меня взяли. Это задача пары часов уровня младшего разработчика.
1
Butt-Head
Заблокирован
30.07.2015, 13:58  [ТС] #44
Да чиТо за хрень

Eraston, ct0r, вы можете на конкретном примере продемонстрировать пошагово, как работает ваш метод? Я чё то не улавливаю профита ...

Вот допустим у меня есть исходный файл (в оригинале - террабайтный) со значениями:
3
55
24
2
3
2

Вот тут 6 значений. Допустим наш лимит в 2 гига, это чтение 2-х значений. Короче блоки по два значения...
Как будет выглядеть ваш метод пошагово?

Добавлено через 1 минуту
Цитата Сообщение от ct0r Посмотреть сообщение
писал в офисе Яндекса на собеседовании
Так ты сейчас в Янедксе работаешь или уже откинулся ?
Цитата Сообщение от ct0r Посмотреть сообщение
Это задача пары часов уровня младшего разработчика.
Это задача тех, кто занимается подобными вещами.
0
Eraston
53 / 10 / 2
Регистрация: 09.09.2014
Сообщений: 127
30.07.2015, 14:04 #45
Цитата Сообщение от ct0r Посмотреть сообщение
Ну у нас в файлах уже все отсортировано, а блоками мы читаем только для ускорения чтения с диска. Сливаем их по обычному алгоритму, а как только накопится достаточно отсортированных значений - сбрасываем кусок на диск.
Я сейчас просто попробую воссоздать...
Блоки
1: 1 2 2 2 2 2
2: 1 1 1 1 1 9

Тут 2 варианта:
1. Выбирать минимальный из N=колво_открытых_блоков элементов (4*N байт) и писать в выходной файл.
2. Загрузить сразу определенное количество элементов (тут 6, т.е. N*6*4, а вообще... чтобы 2 Гб забить) и а) отсортировать их, б) записать.
а) память занята, сортировка идет, файл не пишется
б) память занята, сортировка не идет, файл пишется
3. В случае с тредами:
а) память занята, сортировка идет, файл пишется
б) память занята, сортировка идет, файл пишется

Добавлено через 4 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
3
55
24
2
3
2
Чтение-память-запись-блока
3 55 - 3 55
24 2 - 2 24
3 2 - 2 3


Блоки
1: 3 55
2: 2 24
3: 2 3


Чтениеизблоков-записьввыходнойфайл
1 шаг: 3 2 2 - 2
1: 3 55
2: 24
3: 2 3
2 шаг: 3 24 2 - 2 2
1: 3 55
2: 24
3: 3
3 шаг: 3 24 3 - 2 2 3
1: 55
2: 24
3: 3
4 шаг: 55 24 3 - 2 2 3 3
1: 55
2: 24
5 шаг: 55 24 - 2 2 3 3 24
1: 55
6 шаг: 55 - 2 2 3 3 24 55
1
30.07.2015, 14:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 14:04
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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