Форум программистов, компьютерный форум 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Butt-Head
Заблокирован
30.07.2015, 22:33  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #81
Цитата Сообщение от Renji Посмотреть сообщение
Диапазон адресов,
А почему тогда кастапуть пишет в этом Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти посте, что у него на 172 мегабайта этот проецируемый файл занял не более 500кБ? За счёт чего размер меньше - то? Да ещё и на столько?
Цитата Сообщение от castaway Посмотреть сообщение
Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Renji
1533 / 981 / 239
Регистрация: 05.06.2014
Сообщений: 2,951
30.07.2015, 22:47     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #82
Цитата Сообщение от Butt-Head Посмотреть сообщение
За счёт чего размер меньше - то?
За счет того что диапазон адресов не имеет никакого отношения к расходам физической памяти. Про потемкинские деревни слышали? Вот здесь тот же механизм. Когда пользователь обращается по конкретному адресу, с этим адресом сразу связывается кусок физической памяти с фрагментом файла в нем. А как только пользователь отвернется, кусок памяти оперативно освобождается и направляется на другие нужды. В результате по бумагам у нас два терабайта, а по факту 500 килобайт.
Butt-Head
Заблокирован
30.07.2015, 22:51  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #83
Цитата Сообщение от Renji Посмотреть сообщение
В результате по бумагам у нас два терабайта, а по факту 500 килобайт
Ну в общем WinApi как бы декомпозирует блок в 1 террабайт (допустим) на какие - то кусочки и представляет пользователю только начала и концы этих кусочков ... ? Ну бред какой - то... Ну да ладно, я уже давно чисто под WinApi не пишу, только Qt
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 749
30.07.2015, 23:07     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #84
Цитата Сообщение от ct0r Посмотреть сообщение
Все равно сложность линейная
Ага, только вопрос в коэффициенте перед N.
Цитата Сообщение от ct0r Посмотреть сообщение
shmkv, кстати как насчет того, что числа не факт, что 32битные?
Не понял почему вопрос адресован именно мне. Я изначально и предлагал делать слиянием. Потом уже были от других людей предложения делать подсчет количества чисел. Я лишь только объяснил как это можно организовать.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
31.07.2015, 00:20     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #85
Цитата Сообщение от shmkv Посмотреть сообщение
Ага, только вопрос в коэффициенте перед N.
Ну тут уже надо смотреть, на каких объемах данных константа не играет главной роли.

Цитата Сообщение от shmkv Посмотреть сообщение
Не понял почему вопрос адресован именно мне. Я изначально и предлагал делать слиянием. Потом уже были от других людей предложения делать подсчет количества чисел. Я лишь только объяснил как это можно организовать.
Понятно. В принципе идея с подсчетом неплохая, но нужно ясно представлять, для какого юз-кейса она подходит лучше всего.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2015, 07:05     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Enno
265 / 168 / 38
Регистрация: 25.08.2014
Сообщений: 1,088
Записей в блоге: 1
31.07.2015, 07:05     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #86
Цитата Сообщение от Butt-Head Посмотреть сообщение
Может пояснишь?
Работаешь с файлом методами памяти. Фактически ты теребишь диск только когда читаешь/записываешь. Это удобнее, чем SetFilePointer. А доступ к данным так вообще прозрачно осуществляется, никаких ReadFile/WriteFile. Короче считай что файл уже в памяти, но только подтормаживает. Множество функций работает с данными которые уже в памяти, поэтому нужен указатель. Это как выделение памяти под что-нибудь используя SEH или аналогичное - надо память? ок, сейчас выделим.

Добавлено через 4 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
В нашем случае, камнем предкновения будет харддиск, а не процессор, так что GPGPU и не потребуется...
Тут не один камень. Камни с видюхи помогут. Тебе же надо обработать данные. Даже 400 метров Int'ов за мгновение не рассортируются.
Yandex
Объявления
31.07.2015, 07:05     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Ответ Создать тему
Опции темы

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