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

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

29.07.2015, 16:30. Просмотров 4169. Ответов 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
Ответы с готовыми решениями:

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

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

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

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

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

85
Butt-Head
Заблокирован
30.07.2015, 22:33  [ТС] 81
Цитата Сообщение от Renji Посмотреть сообщение
Диапазон адресов,
А почему тогда кастапуть пишет в этом Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти посте, что у него на 172 мегабайта этот проецируемый файл занял не более 500кБ? За счёт чего размер меньше - то? Да ещё и на столько?
Цитата Сообщение от castaway Посмотреть сообщение
Проверил на файле 172 MB. Программа использовала не более 500кБ ОЗУ.
0
Renji
2114 / 1552 / 473
Регистрация: 05.06.2014
Сообщений: 4,505
30.07.2015, 22:47 82
Цитата Сообщение от Butt-Head Посмотреть сообщение
За счёт чего размер меньше - то?
За счет того что диапазон адресов не имеет никакого отношения к расходам физической памяти. Про потемкинские деревни слышали? Вот здесь тот же механизм. Когда пользователь обращается по конкретному адресу, с этим адресом сразу связывается кусок физической памяти с фрагментом файла в нем. А как только пользователь отвернется, кусок памяти оперативно освобождается и направляется на другие нужды. В результате по бумагам у нас два терабайта, а по факту 500 килобайт.
0
Butt-Head
Заблокирован
30.07.2015, 22:51  [ТС] 83
Цитата Сообщение от Renji Посмотреть сообщение
В результате по бумагам у нас два терабайта, а по факту 500 килобайт
Ну в общем WinApi как бы декомпозирует блок в 1 террабайт (допустим) на какие - то кусочки и представляет пользователю только начала и концы этих кусочков ... ? Ну бред какой - то... Ну да ладно, я уже давно чисто под WinApi не пишу, только Qt
0
shmkv
1207 / 430 / 59
Регистрация: 21.07.2015
Сообщений: 1,113
30.07.2015, 23:07 84
Цитата Сообщение от ct0r Посмотреть сообщение
Все равно сложность линейная
Ага, только вопрос в коэффициенте перед N.
Цитата Сообщение от ct0r Посмотреть сообщение
shmkv, кстати как насчет того, что числа не факт, что 32битные?
Не понял почему вопрос адресован именно мне. Я изначально и предлагал делать слиянием. Потом уже были от других людей предложения делать подсчет количества чисел. Я лишь только объяснил как это можно организовать.
0
ct0r
Игогошка!
1789 / 690 / 44
Регистрация: 19.08.2012
Сообщений: 1,342
Завершенные тесты: 1
31.07.2015, 00:20 85
Цитата Сообщение от shmkv Посмотреть сообщение
Ага, только вопрос в коэффициенте перед N.
Ну тут уже надо смотреть, на каких объемах данных константа не играет главной роли.

Цитата Сообщение от shmkv Посмотреть сообщение
Не понял почему вопрос адресован именно мне. Я изначально и предлагал делать слиянием. Потом уже были от других людей предложения делать подсчет количества чисел. Я лишь только объяснил как это можно организовать.
Понятно. В принципе идея с подсчетом неплохая, но нужно ясно представлять, для какого юз-кейса она подходит лучше всего.
0
Enno
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
31.07.2015, 07:05 86
Цитата Сообщение от Butt-Head Посмотреть сообщение
Может пояснишь?
Работаешь с файлом методами памяти. Фактически ты теребишь диск только когда читаешь/записываешь. Это удобнее, чем SetFilePointer. А доступ к данным так вообще прозрачно осуществляется, никаких ReadFile/WriteFile. Короче считай что файл уже в памяти, но только подтормаживает. Множество функций работает с данными которые уже в памяти, поэтому нужен указатель. Это как выделение памяти под что-нибудь используя SEH или аналогичное - надо память? ок, сейчас выделим.

Добавлено через 4 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
В нашем случае, камнем предкновения будет харддиск, а не процессор, так что GPGPU и не потребуется...
Тут не один камень. Камни с видюхи помогут. Тебе же надо обработать данные. Даже 400 метров Int'ов за мгновение не рассортируются.
0
31.07.2015, 07:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2015, 07:05

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

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

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


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

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

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