Форум программистов, компьютерный форум 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 13:43     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #41
Цитата Сообщение от ct0r Посмотреть сообщение
сортировка быстрая, за О(n), как раз методом подсчета например
Прошу прощения, не методом подсчета конечно же (много памяти жрет, хороша когда диапазон возможных значений мал), а поразрядная (radix sort).

Цитата Сообщение от Eraston Посмотреть сообщение
То уже смахивает на многопоточность, когда пока 1 поток сортирует, 2ой пишет отсортированный массив, ибо из файлов-блоков без сортировки на выходе неотсортированный массив.
Ну у нас в файлах уже все отсортировано, а блоками мы читаем только для ускорения чтения с диска. Сливаем их по обычному алгоритму, а как только накопится достаточно отсортированных значений - сбрасываем кусок на диск.

Добавлено через 3 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?
А как ты без их сортировки потом сливать в отсортированный файл будешь? Ты понимаешь, как делается это слияние?

Цитата Сообщение от Butt-Head Посмотреть сообщение
В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?
Нет. Отсортированный кусок.

Цитата Сообщение от Butt-Head Посмотреть сообщение
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Не будет. Можешь проверить.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Eraston
 Аватар для Eraston
53 / 10 / 2
Регистрация: 09.09.2014
Сообщений: 123
30.07.2015, 13:46     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #42
Цитата Сообщение от Butt-Head Посмотреть сообщение
Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?
Ты выбираешь из 1ых элементов файлов-блоков минимальный элемент. Смотри сам, что получится по твоему разумению, что "А зачем тут сортировка при записи в блоки?":
Блоки
1: 64 2
2: 32 1
3: 10 90

Выход
Ф: 10 32 1 64 2 90


Цитата Сообщение от Butt-Head Посмотреть сообщение
В файле, в который ты пишешь лежит что? Таблица повторений на конкретный кусок?
Блок элементов из исоходного файла отсортированный в пределах самого себя (блока, а не общей последовательности в исходном файле)

Цитата Сообщение от Butt-Head Посмотреть сообщение
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Цитата Сообщение от Eraston Посмотреть сообщение
Второй проход 1 Тб: считать из блоков (1024 файловых стрима
Цитата Сообщение от ct0r Посмотреть сообщение
Одновременно
) с выборкой (очередное наименьшее значение из 1024) 1Тб и записать в 1 Тб
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 13:54     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #43
Цитата Сообщение от Butt-Head Посмотреть сообщение
А это в сумме не будет равно 16-м проходам по террабайту случаем?
Впрочем облегчу тебе задачу - раз мы суммарно в них записали 1 Тб, то и считаем тоже 1 Тб

Butt-Head, для пущей убедительности добавлю, что код к абсолютно такой же задаче я писал в офисе Яндекса на собеседовании в 2011 году, - и меня взяли. Это задача пары часов уровня младшего разработчика.
Butt-Head
Заблокирован
30.07.2015, 13:58  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #44
Да чиТо за хрень

Eraston, ct0r, вы можете на конкретном примере продемонстрировать пошагово, как работает ваш метод? Я чё то не улавливаю профита ...

Вот допустим у меня есть исходный файл (в оригинале - террабайтный) со значениями:
3
55
24
2
3
2

Вот тут 6 значений. Допустим наш лимит в 2 гига, это чтение 2-х значений. Короче блоки по два значения...
Как будет выглядеть ваш метод пошагово?

Добавлено через 1 минуту
Цитата Сообщение от ct0r Посмотреть сообщение
писал в офисе Яндекса на собеседовании
Так ты сейчас в Янедксе работаешь или уже откинулся ?
Цитата Сообщение от ct0r Посмотреть сообщение
Это задача пары часов уровня младшего разработчика.
Это задача тех, кто занимается подобными вещами.
Eraston
 Аватар для Eraston
53 / 10 / 2
Регистрация: 09.09.2014
Сообщений: 123
30.07.2015, 14:04     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #45
Цитата Сообщение от ct0r Посмотреть сообщение
Ну у нас в файлах уже все отсортировано, а блоками мы читаем только для ускорения чтения с диска. Сливаем их по обычному алгоритму, а как только накопится достаточно отсортированных значений - сбрасываем кусок на диск.
Я сейчас просто попробую воссоздать...
Блоки
1: 1 2 2 2 2 2
2: 1 1 1 1 1 9

Тут 2 варианта:
1. Выбирать минимальный из N=колво_открытых_блоков элементов (4*N байт) и писать в выходной файл.
2. Загрузить сразу определенное количество элементов (тут 6, т.е. N*6*4, а вообще... чтобы 2 Гб забить) и а) отсортировать их, б) записать.
а) память занята, сортировка идет, файл не пишется
б) память занята, сортировка не идет, файл пишется
3. В случае с тредами:
а) память занята, сортировка идет, файл пишется
б) память занята, сортировка идет, файл пишется

Добавлено через 4 минуты
Цитата Сообщение от Butt-Head Посмотреть сообщение
3
55
24
2
3
2
Чтение-память-запись-блока
3 55 - 3 55
24 2 - 2 24
3 2 - 2 3


Блоки
1: 3 55
2: 2 24
3: 2 3


Чтениеизблоков-записьввыходнойфайл
1 шаг: 3 2 2 - 2
1: 3 55
2: 24
3: 2 3
2 шаг: 3 24 2 - 2 2
1: 3 55
2: 24
3: 3
3 шаг: 3 24 3 - 2 2 3
1: 55
2: 24
3: 3
4 шаг: 55 24 3 - 2 2 3 3
1: 55
2: 24
5 шаг: 55 24 - 2 2 3 3 24
1: 55
6 шаг: 55 - 2 2 3 3 24 55
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 14:06     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #46
Считали 3 55. Отсортировали. Записали 3 55 в файл 1.dump
Считали 24 2. Отсортировали. Записали 2 24 в 2.dump
Считали 3 2. Отсортировали. Записали 2 3 в 3.dump

Итого у нас 3 открытых файла
3 55
2 24
2 3

Считываем например по одному значению из них - 3 2 2. Берем минимальное - 2, пишем в выходной файл его, считываем из файла, откуда мы взяли эту двойку, следующее число - 24. Выбираем минимальное из 3 24 2. Это 2. Пишем в выходной файл. Читаем из третьего файла (посколько мы оттуда уже взяли двойку и записали в выходной файл) тройку. Берем минимум из 3 24 3. И так далее.

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

Цитата Сообщение от Butt-Head Посмотреть сообщение
Так ты сейчас в Янедксе работаешь или уже откинулся ?
Сейчас не в яндексе, а в его конкуренте

Цитата Сообщение от Butt-Head Посмотреть сообщение
Это задача тех, кто занимается подобными вещами.
Это была моя первая работа. О каких подобных вещах ты говоришь? Тут нет никакой специфики, должен каждый уметь.
Butt-Head
Заблокирован
30.07.2015, 14:15  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #47
Цитата Сообщение от ct0r Посмотреть сообщение
Берем минимальное - 2, пишем в выходной файл его, считываем из файла, откуда мы взяли эту двойку, следующее число - 24.
Всё. Теперь идею понял. Спасибо.
Eraston, ты нуб, объяснять ваще не умеешь Но всё равно спасибо

Цитата Сообщение от ct0r Посмотреть сообщение
Сейчас не в яндексе, а в его конкуренте
в гугле что ли?
Цитата Сообщение от ct0r Посмотреть сообщение
О каких подобных вещах ты говоришь? Тут нет никакой специфики, должен каждый уметь.
Каждый должен знать то, что ему нужно знать в текущей момент времени, а так же владеть информацией о том, где посмотреть дополнительную информацию для решения других задач. Иначе ты просто загрузишь себе череп всякой хренатенью алгоритмической и на то, что б свободно мыслить и решать творческие задачи у тебя не хватит оперативки в мозгу. Поверь мне, я знаю что говорю. Слышал историю про маленьких гениев? Один из них в 8 или 9 лет мог "брать 4-х этажные интегралы", но не мог даже себе жопу самостоятельно подтереть, т.к. всё время забывал, как это делается.
Eraston
30.07.2015, 14:20
  #48

Не по теме:

Цитата Сообщение от Butt-Head Посмотреть сообщение
Eraston, ты нуб, объяснять ваще не умеешь
Уровень понимания не зависит от уровня объяснения ©.

Butt-Head
Заблокирован
30.07.2015, 14:23  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #49
Цитата Сообщение от Eraston Посмотреть сообщение
Уровень понимания не зависит от уровня объяснения ©.
Пфффф.... Ты лунтик что ли?
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
30.07.2015, 14:29     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #50
Цитата Сообщение от Butt-Head Посмотреть сообщение
Каждый должен знать то, что ему нужно знать в текущей момент времени, а так же владеть информацией о том, где посмотреть дополнительную информацию для решения других задач.
Ну смотри. Тебе нужно отсортировать много-много чисел. Ты вроде как знаешь - быстрая сортировка и норм. И из-за незнания того, что существуют специальные более быстрые методы сортировки именно для целых чисел, ты реализуешь не самый эффективный алгоритм. Конечно, подробно все заучивать не надо, действительно перегрузишься, но общее поверхностное представление - что вообще существует и когда что лучше применять - нужно иметь по многим вопросам.
Butt-Head
Заблокирован
30.07.2015, 14:39  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #51
Цитата Сообщение от ct0r Посмотреть сообщение
но общее поверхностное представление - что вообще существует
Вот этого и достаточно.
Цитата Сообщение от ct0r Посмотреть сообщение
Ты вроде как знаешь - быстрая сортировка и норм. И из-за незнания того
Почему же. Перед решением ответственной задачи я загляну в гугл и он отправит меня на хабр, стековерфлоу или сюда, где собственно я и узнаю о наилучшем методе сортировке в данном конкретном случае.
Видишь, даже мой тред называется: "Наиболее быстрый способ сортировки файла...". Я зашёл сюда, что бы узнать..
У человечества всё больше и больше знаний и забивать голову всякой ерундой, которую можно посмотреть на любом форуме, не имеет никакого смысла, собственно как и оценивать кандидата на собеседование аналогичными задачами. Сейчас более эффективна ссылочная память, то есть помнишь, что такое есть, примерное где применяется и главное, где посмотреть. Так больше в голову влезает
По этому я и говорил:
Цитата Сообщение от Butt-Head Посмотреть сообщение
а так же владеть информацией о том, где посмотреть дополнительную информацию для решения других задач.
Правда конечно же, в случае глобального катаклизма и краха интернета с одновременным уничтожением всех физических архивов каким - нибуть астероидом или ядреной войной, человечество быстро откатится до уровня каменного века, что собственно скорее всего уже было и не раз.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
30.07.2015, 15:00     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #52
Цитата Сообщение от Butt-Head Посмотреть сообщение
У человечества всё больше и больше знаний и забивать голову всякой ерундой
Ну, для программиста основы структур данных и алгоритмов - это, по сути, таблица умножения.
shmkv
540 / 254 / 29
Регистрация: 21.07.2015
Сообщений: 756
30.07.2015, 15:01     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #53
Цитата Сообщение от ct0r Посмотреть сообщение
Впрочем облегчу тебе задачу - раз мы суммарно в них записали 1 Тб
Это как? С каких пор сортировка слиянием стала работать за O(N)?
И вообще я сильно сомневаюсь, что сортировка слиянием тут будет быстрее.
w e
0 / 0 / 0
Регистрация: 10.03.2014
Сообщений: 15
30.07.2015, 15:02     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #54
Цитата Сообщение от ct0r Посмотреть сообщение
можем сортировать за O(n)
смешно)
а почему через жесткий диск не попробовать?
shmkv
540 / 254 / 29
Регистрация: 21.07.2015
Сообщений: 756
30.07.2015, 15:07     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #55
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, для программиста основы структур данных и алгоритмов - это, по сути, таблица умножения.
Смотря чем этот программист будет заниматься...

Добавлено через 4 минуты
Вот есть последовательность 3 1 4 1 5 9
на первом этапе мы записали 13 14 59 и все, памяти уже переписано эквивалентно исходной последовательности, а она еще не отсортирована. В чем я не прав?
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
30.07.2015, 15:13     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #56
Цитата Сообщение от shmkv Посмотреть сообщение
Смотря чем этот программист будет заниматься...
Попробую угадать с трех раз. Хранением и обработкой данных с помощью алгоритмов?
shmkv
30.07.2015, 15:20
  #57

Не по теме:

Цитата Сообщение от Mr.X Посмотреть сообщение
Хранением и обработкой данных с помощью алгоритмов?
Если бы... У нас очень много вакансий для "программистов", где по факту человеку предстоит знаться другими вещами.

Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
30.07.2015, 15:23     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #58
Цитата Сообщение от shmkv Посмотреть сообщение
Если бы... У нас очень много вакансий "программистов", где по факту человеку предстоит знаться другими вещами.
Ну так это и не программисты, а специалисты по другим вещам. Здесь же все типа программисты.
Butt-Head
Заблокирован
30.07.2015, 15:26  [ТС]     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #59
Цитата Сообщение от shmkv Посмотреть сообщение
на первом этапе мы записали 13 14 59 и все, памяти уже переписано эквивалентно исходной последовательности
не очень понял суть вопроса...
Да, ты сделал три блока, отсортированных локально как бы, то есть внутри себя и записал их в файлы.
Далее открываешь одновременно все эти файлы, в данном случае с 13, 14 и 59 и читаешь из них (из каждого), первое значение, получается:
1
1
5
ищешь первое минимальное, - это один из первого файла, пишешь это значение (единицу) в результирующий файл и cдвигаешь ленту первого файла на одно значение и берёшь опять слепок ;)
Смари, тут просто хитрость, представь тре плёнки от фотоаппарата (ну раньше были плёночные фотоаппараты, в курсе? :D ) Вот ты кладёшь их на стол. Берёшь... ну не знаю, листочек А4 и вырезаешь прямоугольник в нём, что б в столбик там поместилось 3 слайда. Кладёшь этот листок на три плёнки свои на столе на начало плёнок. Видишь там в столбик три кадра в столбик (по кадру от каждой плёнке) (первые кадры), это как бы три значения. Ищешь минимальное значение и записываешь его в результирующий файл. После этого, ты рукой сдвигаешь ленту с кадрами, с которой ты "брал" кадр, влево на 1 кадр и смотришь опять в прямоугольное окно... и т.д.

Добавлено через 1 минуту
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну так это и не программисты, а специалисты по другим вещам. Здесь же все типа программисты.
Алгоритмы и структуры данных требуются в 3..5 % вакансий программистов С++
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 15:28     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
30.07.2015, 15:28     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти #60
Цитата Сообщение от Butt-Head Посмотреть сообщение
Алгоритмы и структуры данных требуются в 3..5 % вакансий программистов С++
В смысле? Если вы код пишете, то они вам требуются, а если нет, то это вроде и не программирование.
Yandex
Объявления
30.07.2015, 15:28     Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Ответ Создать тему
Опции темы

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