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

@~~Butt-Head~~ · 29.07.2015, 16:30. **Показов** 25251. **Ответов** 85

Author24 — интернет-сервис помощи студентам

Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1 террабайт, если на компе, к примеру, доступно всего 2 гб оперативки ... ?
Ну файл с нитами типа:

1
2
3
4
6346546
234524234
656546546
24234234
777
654646

и тд

Добавлено через 1 час 11 минут
Важная тема теряется... Up!

Добавлено через 4 часа 45 минут
Ну так что, никто не подскажет, как отсортировать 1 гиг в файле?

@Niko Demin · 30.07.2015, 15:29

Короче идея такая: создаём переменную, где хранится максимальное значение входного файла (typename max_num например), создаём массив , который заполняет все 2 гига (от 0 до N).
Затем обходим весь входной файл и заносим кол-во соответствующих значений в массив (т.е. значению 0 соответствует нулевой элемент. Допустим нулей у нас 100, тогда заносим туда 100), при первом обходе заносим максимальное число в max_num. Затем записываем в выходной файл последовательно соответствующие значения столько раз, сколько указано в счётчике в массиве.
Потом обнуляем массив и совершаем ещё один проход, но теперь ячейки соответствуют значениям от N+1 до 2*N+1. Записываем в выходной файл и т.д.
И так до тех пор, пока последний элемент массива не будет соответствовать max_num.

shmkv · 30.07.2015, 15:37

Сообщение от Butt-Head

отсортированных локально как бы, то есть внутри себя и записал их в файлы.

Ага, и на этом этапе мы уже записали 1 Тб памяти о чем я и сказал...

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

Добавлено через 2 минуты

Сообщение от Butt-Head

Далее открываешь одновременно все эти файлы, в данном случае с 13, 14 и 59 и читаешь из них (из каждого)

Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...

@~~Butt-Head~~ · 30.07.2015, 15:42 **[ТС]**

Сообщение от Mr.X

Если вы код пишете, то они вам требуются

Ну где мне может потребоваться сортировка террабайтного файла?

Вопрос этого треда был из одного теста на одну вакансию и не более... Вот сейчас на работе сижу и пишу код одной системы управления предприятием на Qt и в ус не дую, где мне тут потребуются всякие студентческие выпендрёжные хитрости

Сообщение от shmkv

Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...

Согласен. Но в предыдущем способе было необходимо 16-и кратное чтение всего файла в 1 тб, что наверное медленнее...

@ct0r · 30.07.2015, 15:47

Сообщение от shmkv

Это как? С каких пор сортировка слиянием стала работать за O(N)?
И вообще я сильно сомневаюсь, что сортировка слиянием тут будет быстрее.

Речь о поразрядной сортировке и слиянии. Откуда ты взял сортировку слиянием?

Сообщение от w e

смешно)

Если кому-то смешно, то пусть подучит матчасть

Сообщение от shmkv

Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости...

Я уже про все это написал. Прочитай внимательно еще раз.

shmkv · 30.07.2015, 15:56

Сообщение от ct0r

Речь о поразрядной сортировке и слиянии.

Хорошо.

Сообщение от ct0r

Если кому-то смешно, то пусть подучит матчасть

Мне не смешно, но вот как можно отсортировать массив произвольных (путь даже 32хбитовых) чисел за O(N) и ограничиться 2 Гб памяти (без лишних шуршаний диском) мне непонятно.

@ct0r · 30.07.2015, 15:58

Сообщение от shmkv

Мне не смешно, но как можно отсортировать массив произвольных 32хбитных чисел за O(N)

Можно, потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n.
https://en.wikipedia.org/wiki/Sorting_algorithm - найди раздел Non-comparison sorts

shmkv · 30.07.2015, 16:24

Сообщение от ct0r

найди раздел Non-comparison sorts

А конкретнее, какой из них подойдет для данной задачи?

Добавлено через 14 минут

Сообщение от ct0r

потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n.

Зато они требуют много дополнительной памяти. Есть и другие варианты, но они хорошо работают только на определенных данных...

@~~Butt-Head~~ · 30.07.2015, 16:28 **[ТС]**

Так...После битвы ct0r vs shmkv, расскажите мне всё таки, чей метод быстрее, ок ?

@ct0r · 30.07.2015, 16:43

Сообщение от shmkv

А конкретнее, какой из них подойдет для данной задачи?

Я упоминал radix sort.

Сообщение от shmkv

Зато они требуют много дополнительной памяти.

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

Добавлено через 1 минуту

Сообщение от Butt-Head

асскажите мне всё таки, чей метод быстрее, ок ?

Э, а ты вообще чего ждешь, уже давно бы написал оба варианта и посмотрел

Добавлено через 2 минуты
Кстати по поводу диска - а фиг там его знает, может у нас вообще RAID SSD

@~~Butt-Head~~ · 30.07.2015, 16:45 **[ТС]**

Сообщение от ct0r

уже давно бы написал оба варианта и посмотрел

У меня хард всего гигов на 250 что ли ... 1 Тб не влезет для чистоты эксперимента.

Я лучше подожду

@smartpointer · 30.07.2015, 18:02

Хмм , а что если использовать дерево, например RB ? Обход дерева можно замутить с помощью стека без рекурсии.Тогда схема достаточна проста будет файл->память->дерево.

@Mr.X · 30.07.2015, 18:06

Сообщение от Butt-Head

Ну где мне может потребоваться сортировка террабайтного файла?

Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление.

shmkv · 30.07.2015, 18:08

Сообщение от ct0r

Я упоминал radix sort.

Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно.

@~~Butt-Head~~ · 30.07.2015, 18:20 **[ТС]**

Сообщение от smartpointer

Хмм , а что если использовать дерево, например RB ?

Конкретней, на примере и с учётом наших условий - файл размером в 1 Тб с 32-х битными интами, размер оперативки - 2 Гб.

Сообщение от Mr.X

Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление.

Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё

Вот видишь, в принципе, тут даже этого знать не обязательно и для того, что бы засорят мозг, достаточно знать, что вообще есть какая - то сортировка и что можно что - то отсортировать, всё остальное несложно узнать на в интернете

@ct0r · 30.07.2015, 18:29

Сообщение от shmkv

Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно.

Неоднозачно? А какие варианты неоднозначности? Все равно сложность линейная. А как насчет того, что есть модификации к увеличению локальности кэша и распараллеливанию?

https://ieeexplore.ieee.org/xp... ber=994310
http://dl.acm.org/citation.cfm?id=377792.377816

@Enno · 30.07.2015, 18:33

Сообщение от Butt-Head

размер оперативки - 2 Гб.

Повлияет только на скорость. Проецируемые файлы решают эту задачу, как на первой странице.
Хочу напомнить всем любителям метода "Считаем в память, а потом..." что придётся оптимизировать доступ к памяти, учитывать кэш-линии и прочее. Для совсем озадаченных - CUDA. Даже есть уже готовые библиотеки для параллельной сортировки, только данные успевай подавать.

@ct0r · 30.07.2015, 18:40

shmkv, кстати как насчет того, что числа не факт, что 32битные? А если 64битные, то тогда что?

@Mr.X · 30.07.2015, 18:42

Сообщение от Butt-Head

Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё

Не согласен. Программист творит с помощью интуиции. А чтобы она работала, необходимо в подсознание загрузить необходимую информацию.
Собственно, специалист - это человек с загруженной в подсознание специальной информацией и с опытом оперирования ею на сознательном и подсознательном уровне.

@~~Butt-Head~~ · 30.07.2015, 20:15 **[ТС]**

Сообщение от Enno

Проецируемые файлы решают эту задачу, как на первой странице.

Да, но это не кроссово. Да и потом, если честно, я не понимаю, что из себя конкретно представляют это проецируемые файлы... Почему они так мало памяти занимают... Может пояснишь?

Сообщение от Enno

Для совсем озадаченных - CUDA.

В нашем случае, камнем предкновения будет харддиск, а не процессор, так что GPGPU и не потребуется...

Сообщение от Mr.X

Программист творит с помощью интуиции.

Интуиция - это мнимое понятие, фактический в биологических нейронных сетях головного мозга её нет, есть только опыт, то есть память. А для того, что бы импульс действия прошёл туда, куда надо, необязательно пускать его по дебрям подробностей, достаточно достичь цели, а подробности можно будет вытащить отдельно позже. Говоря языком программирования, достаточно хедер файлов, с описанием своих знаний, а реализацию можно посмотреть в интернете

@Renji · 30.07.2015, 22:13

Сообщение от Butt-Head

Да и потом, если честно, я не понимаю, что из себя конкретно представляют это проецируемые файлы...

Диапазон адресов, чтение/запись в которые эквивалентна чтению/записи с диска. То есть, никакой ускоряющей магии там не происходит, просто более понтовый способ вызвать fread/fwrite. Со всеми плюсами и минусами использования fread/fwrite.

@Niko Demin 2 / 2 / 0 Регистрация: 21.01.2015 Сообщений: 90
	30.07.2015, 15:29	61
	Короче идея такая: создаём переменную, где хранится максимальное значение входного файла (typename max_num например), создаём массив , который заполняет все 2 гига (от 0 до N). Затем обходим весь входной файл и заносим кол-во соответствующих значений в массив (т.е. значению 0 соответствует нулевой элемент. Допустим нулей у нас 100, тогда заносим туда 100), при первом обходе заносим максимальное число в max_num. Затем записываем в выходной файл последовательно соответствующие значения столько раз, сколько указано в счётчике в массиве. Потом обнуляем массив и совершаем ещё один проход, но теперь ячейки соответствуют значениям от N+1 до 2*N+1. Записываем в выходной файл и т.д. И так до тех пор, пока последний элемент массива не будет соответствовать max_num. 0

shmkv 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	30.07.2015, 15:37	62
	Сообщение от Butt-Head отсортированных локально как бы, то есть внутри себя и записал их в файлы. Ага, и на этом этапе мы уже записали 1 Тб памяти о чем я и сказал... Добавлено через 4 минуты Niko Demin, уже предлагалось. Добавлено через 2 минуты Сообщение от Butt-Head Далее открываешь одновременно все эти файлы, в данном случае с 13, 14 и 59 и читаешь из них (из каждого) Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости... 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	30.07.2015, 15:58	66
	Сообщение от shmkv Мне не смешно, но как можно отсортировать массив произвольных 32хбитных чисел за O(N) Можно, потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n. https://en.wikipedia.org/wiki/Sorting_algorithm - найди раздел Non-comparison sorts 0

shmkv 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	30.07.2015, 16:24	67
	Сообщение от ct0r найди раздел Non-comparison sorts А конкретнее, какой из них подойдет для данной задачи? Добавлено через 14 минут Сообщение от ct0r потому что в их основе не лежат сравнения и дерево решений, которые ограничивают нас асимптотикой n * lоg n. Зато они требуют много дополнительной памяти. Есть и другие варианты, но они хорошо работают только на определенных данных... 0

@~~Butt-Head~~ Заблокирован
	30.07.2015, 16:28 [ТС]	68
	Так...После битвы ct0r vs shmkv, расскажите мне всё таки, чей метод быстрее, ок ? 0

@~~Butt-Head~~ Заблокирован
	30.07.2015, 15:42 [ТС]	63
	Сообщение от Mr.X Если вы код пишете, то они вам требуются Ну где мне может потребоваться сортировка террабайтного файла? Вопрос этого треда был из одного теста на одну вакансию и не более... Вот сейчас на работе сижу и пишу код одной системы управления предприятием на Qt и в ус не дую, где мне тут потребуются всякие студентческие выпендрёжные хитрости Сообщение от shmkv Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости... Согласен. Но в предыдущем способе было необходимо 16-и кратное чтение всего файла в 1 тб, что наверное медленнее... 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	30.07.2015, 15:47	64
	Сообщение от shmkv Это как? С каких пор сортировка слиянием стала работать за O(N)? И вообще я сильно сомневаюсь, что сортировка слиянием тут будет быстрее. Речь о поразрядной сортировке и слиянии. Откуда ты взял сортировку слиянием? Сообщение от w e смешно) Если кому-то смешно, то пусть подучит матчасть Сообщение от shmkv Да и еще плюсом операция чтения 1Тб и записи 1Тб. Причем чтение будет производится последовательно из разных участков диска, что тоже не прибавит скорости... Я уже про все это написал. Прочитай внимательно еще раз. 0

shmkv 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	30.07.2015, 15:56	65
	Сообщение от ct0r Речь о поразрядной сортировке и слиянии. Хорошо. Сообщение от ct0r Если кому-то смешно, то пусть подучит матчасть Мне не смешно, но вот как можно отсортировать массив произвольных (путь даже 32хбитовых) чисел за O(N) и ограничиться 2 Гб памяти (без лишних шуршаний диском) мне непонятно. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	30.07.2015, 16:43	69
	Сообщение от shmkv А конкретнее, какой из них подойдет для данной задачи? Я упоминал radix sort. Сообщение от shmkv Зато они требуют много дополнительной памяти. Почему много? Есть которые больше, есть которые меньше... А например в radix sort зависит от того, в какой системе счисления ты представишь числа. Добавлено через 1 минуту Сообщение от Butt-Head асскажите мне всё таки, чей метод быстрее, ок ? Э, а ты вообще чего ждешь, уже давно бы написал оба варианта и посмотрел Добавлено через 2 минуты Кстати по поводу диска - а фиг там его знает, может у нас вообще RAID SSD 0

@~~Butt-Head~~ Заблокирован
	30.07.2015, 16:45 [ТС]	70
	Сообщение от ct0r уже давно бы написал оба варианта и посмотрел У меня хард всего гигов на 250 что ли ... 1 Тб не влезет для чистоты эксперимента. Я лучше подожду 0

@smartpointer 70 / 64 / 40 Регистрация: 17.02.2014 Сообщений: 265
	30.07.2015, 18:02	71
	Хмм , а что если использовать дерево, например RB ? Обход дерева можно замутить с помощью стека без рекурсии.Тогда схема достаточна проста будет файл->память->дерево. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	30.07.2015, 18:06	72
	Сообщение от Butt-Head Ну где мне может потребоваться сортировка террабайтного файла? Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление. 0

shmkv 1375 / 519 / 72 Регистрация: 21.07.2015 Сообщений: 1,304
	30.07.2015, 18:08	73
	Сообщение от ct0r Я упоминал radix sort. Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно. 0

@~~Butt-Head~~ Заблокирован
	30.07.2015, 18:20 [ТС]	74
	Сообщение от smartpointer Хмм , а что если использовать дерево, например RB ? Конкретней, на примере и с учётом наших условий - файл размером в 1 Тб с 32-х битными интами, размер оперативки - 2 Гб. Сообщение от Mr.X Ну, терабайтного - не терабайтного, но давайте согласимся, что о сортировке слиянием таки надо иметь представление. Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё Вот видишь, в принципе, тут даже этого знать не обязательно и для того, что бы засорят мозг, достаточно знать, что вообще есть какая - то сортировка и что можно что - то отсортировать, всё остальное несложно узнать на в интернете 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	30.07.2015, 18:29	75
	Сообщение от shmkv Там делается несколько проходов по массиву, количество зависит от диапазона значений и размера ключа + судя по описанию он не дружен с кэшем процессора. Так, что не все так однозначно. Неоднозачно? А какие варианты неоднозначности? Все равно сложность линейная. А как насчет того, что есть модификации к увеличению локальности кэша и распараллеливанию? https://ieeexplore.ieee.org/xp... ber=994310 http://dl.acm.org/citation.cfm?id=377792.377816 0

	30.07.2015, 22:13

@Enno 267 / 170 / 40 Регистрация: 25.08.2014 Сообщений: 1,087 Записей в блоге: 1
	30.07.2015, 18:33	76
	Сообщение от Butt-Head размер оперативки - 2 Гб. Повлияет только на скорость. Проецируемые файлы решают эту задачу, как на первой странице. Хочу напомнить всем любителям метода "Считаем в память, а потом..." что придётся оптимизировать доступ к памяти, учитывать кэш-линии и прочее. Для совсем озадаченных - CUDA. Даже есть уже готовые библиотеки для параллельной сортировки, только данные успевай подавать. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	30.07.2015, 18:40	77
	shmkv, кстати как насчет того, что числа не факт, что 32битные? А если 64битные, то тогда что? 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	30.07.2015, 18:42	78
	Сообщение от Butt-Head Зачем? Я запостил на форум, мне сказали, что такая сортировка есть, в википедии посмторел, как она реализована - всё Не согласен. Программист творит с помощью интуиции. А чтобы она работала, необходимо в подсознание загрузить необходимую информацию. Собственно, специалист - это человек с загруженной в подсознание специальной информацией и с опытом оперирования ею на сознательном и подсознательном уровне. 0

@~~Butt-Head~~ Заблокирован
	30.07.2015, 20:15 [ТС]	79
	Сообщение от Enno Проецируемые файлы решают эту задачу, как на первой странице. Да, но это не кроссово. Да и потом, если честно, я не понимаю, что из себя конкретно представляют это проецируемые файлы... Почему они так мало памяти занимают... Может пояснишь? Сообщение от Enno Для совсем озадаченных - CUDA. В нашем случае, камнем предкновения будет харддиск, а не процессор, так что GPGPU и не потребуется... Сообщение от Mr.X Программист творит с помощью интуиции. Интуиция - это мнимое понятие, фактический в биологических нейронных сетях головного мозга её нет, есть только опыт, то есть память. А для того, что бы импульс действия прошёл туда, куда надо, необязательно пускать его по дебрям подробностей, достаточно достичь цели, а подробности можно будет вытащить отдельно позже. Говоря языком программирования, достаточно хедер файлов, с описанием своих знаний, а реализацию можно посмотреть в интернете 0

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	30.07.2015, 22:13	80
	Сообщение от Butt-Head Да и потом, если честно, я не понимаю, что из себя конкретно представляют это проецируемые файлы... Диапазон адресов, чтение/запись в которые эквивалентна чтению/записи с диска. То есть, никакой ускоряющей магии там не происходит, просто более понтовый способ вызвать fread/fwrite. Со всеми плюсами и минусами использования fread/fwrite. 0