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

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

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

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

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

Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего 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++):

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Niko Demin
2 / 2 / 0
Регистрация: 21.01.2015
Сообщений: 73
30.07.2015, 15:29 #61
Короче идея такая: создаём переменную, где хранится максимальное значение входного файла (typename max_num например), создаём массив , который заполняет все 2 гига (от 0 до N).
Затем обходим весь входной файл и заносим кол-во соответствующих значений в массив (т.е. значению 0 соответствует нулевой элемент. Допустим нулей у нас 100, тогда заносим туда 100), при первом обходе заносим максимальное число в max_num. Затем записываем в выходной файл последовательно соответствующие значения столько раз, сколько указано в счётчике в массиве.
Потом обнуляем массив и совершаем ещё один проход, но теперь ячейки соответствуют значениям от N+1 до 2*N+1. Записываем в выходной файл и т.д.
И так до тех пор, пока последний элемент массива не будет соответствовать max_num.
shmkv
568 / 282 / 38
Регистрация: 21.07.2015
Сообщений: 860
30.07.2015, 15:37 #62
Цитата Сообщение от Butt-Head Посмотреть сообщение
отсортированных локально как бы, то есть внутри себя и записал их в файлы.
Ага, и на этом этапе мы уже записали 1 Тб памяти о чем я и сказал...

Добавлено через 4 минуты
Niko Demin, уже предлагалось.

Добавлено через 2 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
Далее открываешь одновременно все эти файлы, в данном случае с 13, 14 и 59 и читаешь из них (из каждого)
Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...
Butt-Head
Заблокирован
30.07.2015, 15:42  [ТС] #63
Цитата Сообщение от Mr.X Посмотреть сообщение
Если вы код пишете, то они вам требуются
Ну где мне может потребоваться сортировка террабайтного файла? Вопрос этого треда был из одного теста на одну вакансию и не более... Вот сейчас на работе сижу и пишу код одной системы управления предприятием на Qt и в ус не дую, где мне тут потребуются всякие студентческие выпендрёжные хитрости

Цитата Сообщение от shmkv Посмотреть сообщение
Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...
Согласен. Но в предыдущем способе было необходимо 16-и кратное чтение всего файла в 1 тб, что наверное медленнее...
ct0r
Игогошка!
1770 / 672 / 42
Регистрация: 19.08.2012
Сообщений: 1,284
Завершенные тесты: 1
30.07.2015, 15:47 #64
Цитата Сообщение от shmkv Посмотреть сообщение
Это как? С каких пор сортировка слиянием стала работать за O(N)?
И вообще я сильно сомневаюсь, что сортировка слиянием тут будет быстрее.
Речь о поразрядной сортировке и слиянии. Откуда ты взял сортировку слиянием?

Цитата Сообщение от w e Посмотреть сообщение
смешно)
Если кому-то смешно, то пусть подучит матчасть

Цитата Сообщение от shmkv Посмотреть сообщение
Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...
Я уже про все это написал. Прочитай внимательно еще раз.
shmkv
568 / 282 / 38
Регистрация: 21.07.2015
Сообщений: 860
30.07.2015, 15:56 #65
Цитата Сообщение от ct0r Посмотреть сообщение
Речь о поразрядной сортировке и слиянии.
Хорошо.
Цитата Сообщение от ct0r Посмотреть сообщение
Если кому-то смешно, то пусть подучит матчасть
Мне не смешно, но вот как можно отсортировать массив произвольных (путь даже 32хбитовых) чисел за O(N) и ограничиться 2 Гб памяти (без лишних шуршаний диском) мне непонятно.
ct0r
Игогошка!
1770 / 672 / 42
Регистрация: 19.08.2012
Сообщений: 1,284
Завершенные тесты: 1
30.07.2015, 15:58 #66
Цитата Сообщение от shmkv Посмотреть сообщение
Мне не смешно, но как можно отсортировать массив произвольных 32хбитных чисел за O(N)
Можно, потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n.
https://en.wikipedia.org/wiki/Sorting_algorithm - найди раздел Non-comparison sorts
shmkv
568 / 282 / 38
Регистрация: 21.07.2015
Сообщений: 860
30.07.2015, 16:24 #67
Цитата Сообщение от ct0r Посмотреть сообщение
найди раздел Non-comparison sorts
А конкретнее, какой из них подойдет для данной задачи?

Добавлено через 14 минут
Цитата Сообщение от ct0r Посмотреть сообщение
потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n.
Зато они требуют много дополнительной памяти. Есть и другие варианты, но они хорошо работают только на определенных данных...
Butt-Head
Заблокирован
30.07.2015, 16:28  [ТС] #68
Так...После битвы ct0r vs shmkv, расскажите мне всё таки, чей метод быстрее, ок ?
ct0r
Игогошка!
1770 / 672 / 42
Регистрация: 19.08.2012
Сообщений: 1,284
Завершенные тесты: 1
30.07.2015, 16:43 #69
Цитата Сообщение от shmkv Посмотреть сообщение
А конкретнее, какой из них подойдет для данной задачи?
Я упоминал radix sort.

Цитата Сообщение от shmkv Посмотреть сообщение
Зато они требуют много дополнительной памяти.
Почему много? Есть которые больше, есть которые меньше... А например в radix sort зависит от того, в какой системе счисления ты представишь числа.

Добавлено через 1 минуту
Цитата Сообщение от Butt-Head Посмотреть сообщение
асскажите мне всё таки, чей метод быстрее, ок ?
Э, а ты вообще чего ждешь, уже давно бы написал оба варианта и посмотрел

Добавлено через 2 минуты
Кстати по поводу диска - а фиг там его знает, может у нас вообще RAID SSD
Butt-Head
Заблокирован
30.07.2015, 16:45  [ТС] #70
Цитата Сообщение от ct0r Посмотреть сообщение
уже давно бы написал оба варианта и посмотрел
У меня хард всего гигов на 250 что ли ... 1 Тб не влезет для чистоты эксперимента.
Я лучше подожду
smartpointer
67 / 61 / 23
Регистрация: 17.02.2014
Сообщений: 256
30.07.2015, 18:02 #71
Хмм , а что если использовать дерево, например RB ? Обход дерева можно замутить с помощью стека без рекурсии.Тогда схема достаточна проста будет файл->память->дерево.
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2015, 18:06 #72
Цитата Сообщение от Butt-Head Посмотреть сообщение
Ну где мне может потребоваться сортировка террабайтного файла?
Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление.
shmkv
568 / 282 / 38
Регистрация: 21.07.2015
Сообщений: 860
30.07.2015, 18:08 #73
Цитата Сообщение от ct0r Посмотреть сообщение
Я упоминал radix sort.
Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно.
Butt-Head
Заблокирован
30.07.2015, 18:20  [ТС] #74
Цитата Сообщение от smartpointer Посмотреть сообщение
Хмм , а что если использовать дерево, например RB ?
Конкретней, на примере и с учётом наших условий - файл размером в 1 Тб с 32-х битными интами, размер оперативки - 2 Гб.

Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление.
Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё Вот видишь, в принципе, тут даже этого знать не обязательно и для того, что бы засорят мозг, достаточно знать, что вообще есть какая - то сортировка и что можно что - то отсортировать, всё остальное несложно узнать на в интернете
ct0r
Игогошка!
1770 / 672 / 42
Регистрация: 19.08.2012
Сообщений: 1,284
Завершенные тесты: 1
30.07.2015, 18:29 #75
Цитата Сообщение от shmkv Посмотреть сообщение
Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно.
Неоднозачно? А какие варианты неоднозначности? Все равно сложность линейная. А как насчет того, что есть модификации к увеличению локальности кэша и распараллеливанию?
http://ieeexplore.ieee.org/xpls/abs_...rnumber=994310
http://dl.acm.org/citation.cfm?id=377792.377816
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 18:29
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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