Форум программистов, компьютерный форум 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Niko Demin
 Аватар для Niko Demin
1 / 1 / 0
Регистрация: 21.01.2015
Сообщений: 14
30.07.2015, 15:29     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #61
Короче идея такая: создаём переменную, где хранится максимальное значение входного файла (typename max_num например), создаём массив , который заполняет все 2 гига (от 0 до N).
Затем обходим весь входной файл и заносим кол-во соответствующих значений в массив (т.е. значению 0 соответствует нулевой элемент. Допустим нулей у нас 100, тогда заносим туда 100), при первом обходе заносим максимальное число в max_num. Затем записываем в выходной файл последовательно соответствующие значения столько раз, сколько указано в счётчике в массиве.
Потом обнуляем массив и совершаем ещё один проход, но теперь ячейки соответствуют значениям от N+1 до 2*N+1. Записываем в выходной файл и т.д.
И так до тех пор, пока последний элемент массива не будет соответствовать max_num.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 15:37     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #62
Цитата Сообщение от Butt-Head Посмотреть сообщение
отсортированных локально как бы, то есть внутри себя и записал их в файлы.
Ага, и на этом этапе мы уже записали 1 Тб памяти о чем я и сказал...

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

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

Цитата Сообщение от shmkv Посмотреть сообщение
Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...
Согласен. Но в предыдущем способе было необходимо 16-и кратное чтение всего файла в 1 тб, что наверное медленнее...
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 15:47     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #64
Цитата Сообщение от shmkv Посмотреть сообщение
Это как? С каких пор сортировка слиянием стала работать за O(N)?
И вообще я сильно сомневаюсь, что сортировка слиянием тут будет быстрее.
Речь о поразрядной сортировке и слиянии. Откуда ты взял сортировку слиянием?

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

Цитата Сообщение от shmkv Посмотреть сообщение
Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...
Я уже про все это написал. Прочитай внимательно еще раз.
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 15:56     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #65
Цитата Сообщение от ct0r Посмотреть сообщение
Речь о поразрядной сортировке и слиянии.
Хорошо.
Цитата Сообщение от ct0r Посмотреть сообщение
Если кому-то смешно, то пусть подучит матчасть
Мне не смешно, но вот как можно отсортировать массив произвольных (путь даже 32хбитовых) чисел за O(N) и ограничиться 2 Гб памяти (без лишних шуршаний диском) мне непонятно.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 15:58     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #66
Цитата Сообщение от shmkv Посмотреть сообщение
Мне не смешно, но как можно отсортировать массив произвольных 32хбитных чисел за O(N)
Можно, потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n.
https://en.wikipedia.org/wiki/Sorting_algorithm - найди раздел Non-comparison sorts
shmkv
538 / 252 / 28
Регистрация: 21.07.2015
Сообщений: 748
30.07.2015, 16:24     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #67
Цитата Сообщение от ct0r Посмотреть сообщение
найди раздел Non-comparison sorts
А конкретнее, какой из них подойдет для данной задачи?

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

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

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

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

Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление.
Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё Вот видишь, в принципе, тут даже этого знать не обязательно и для того, что бы засорят мозг, достаточно знать, что вообще есть какая - то сортировка и что можно что - то отсортировать, всё остальное несложно узнать на в интернете
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 18:29     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #75
Цитата Сообщение от shmkv Посмотреть сообщение
Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно.
Неоднозачно? А какие варианты неоднозначности? Все равно сложность линейная. А как насчет того, что есть модификации к увеличению локальности кэша и распараллеливанию?
http://ieeexplore.ieee.org/xpls/abs_...rnumber=994310
http://dl.acm.org/citation.cfm?id=377792.377816
Enno
265 / 168 / 38
Регистрация: 25.08.2014
Сообщений: 1,088
Записей в блоге: 1
30.07.2015, 18:33     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #76
Цитата Сообщение от Butt-Head Посмотреть сообщение
размер оперативки - 2 Гб.
Повлияет только на скорость. Проецируемые файлы решают эту задачу, как на первой странице.
Хочу напомнить всем любителям метода "Считаем в память, а потом..." что придётся оптимизировать доступ к памяти, учитывать кэш-линии и прочее. Для совсем озадаченных - CUDA. Даже есть уже готовые библиотеки для параллельной сортировки, только данные успевай подавать.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 18:40     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #77
shmkv, кстати как насчет того, что числа не факт, что 32битные? А если 64битные, то тогда что?
Mr.X
Эксперт С++
 Аватар для Mr.X
2797 / 1573 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
30.07.2015, 18:42     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #78
Цитата Сообщение от Butt-Head Посмотреть сообщение
Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё
Не согласен. Программист творит с помощью интуиции. А чтобы она работала, необходимо в подсознание загрузить необходимую информацию.
Собственно, специалист - это человек с загруженной в подсознание специальной информацией и с опытом оперирования ею на сознательном и подсознательном уровне.
Butt-Head
Заблокирован
30.07.2015, 20:15  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #79
Цитата Сообщение от Enno Посмотреть сообщение
Проецируемые файлы решают эту задачу, как на первой странице.
Да, но это не кроссово. Да и потом, если честно, я не понимаю, что из себя конкретно представляют это проецируемые файлы... Почему они так мало памяти занимают... Может пояснишь?
Цитата Сообщение от Enno Посмотреть сообщение
Для совсем озадаченных - CUDA.
В нашем случае, камнем предкновения будет харддиск, а не процессор, так что GPGPU и не потребуется...
Цитата Сообщение от Mr.X Посмотреть сообщение
Программист творит с помощью интуиции.
Интуиция - это мнимое понятие, фактический в биологических нейронных сетях головного мозга её нет, есть только опыт, то есть память. А для того, что бы импульс действия прошёл туда, куда надо, необязательно пускать его по дебрям подробностей, достаточно достичь цели, а подробности можно будет вытащить отдельно позже. Говоря языком программирования, достаточно хедер файлов, с описанием своих знаний, а реализацию можно посмотреть в интернете
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 22:13     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Renji
1532 / 980 / 238
Регистрация: 05.06.2014
Сообщений: 2,950
30.07.2015, 22:13     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #80
Цитата Сообщение от Butt-Head Посмотреть сообщение
Да и потом, если честно, я не понимаю, что из себя конкретно представляют это проецируемые файлы...
Диапазон адресов, чтение/запись в которые эквивалентна чтению/записи с диска. То есть, никакой ускоряющей магии там не происходит, просто более понтовый способ вызвать fread/fwrite. Со всеми плюсами и минусами использования fread/fwrite.
Yandex
Объявления
30.07.2015, 22:13     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Ответ Создать тему
Опции темы

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