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

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

1 2 3 4 6346546 234524234 656546546 24234234 777 654646

и тд



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

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

0

Сообщение от ct0r сортировка быстрая, за О(n), как раз методом подсчета например

Прошу прощения, не методом подсчета конечно же (много памяти жрет, хороша когда диапазон возможных значений мал), а поразрядная (radix sort).

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

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

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

Сообщение от Butt-Head Какой смысл вообще их сортировать? Раз ты всё равно все блоки одновременно читаешь и пишешь в общий файл?

А как ты без их сортировки потом сливать в отсортированный файл будешь? Ты понимаешь, как делается это слияние?

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

Нет. Отсортированный кусок.

Сообщение от Butt-Head А это в сумме не будет равно 16-м проходам по террабайту случаем?

Не будет. Можешь проверить.

0

Сообщение от 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 Тб

1

Сообщение от Butt-Head А это в сумме не будет равно 16-м проходам по террабайту случаем?

Впрочем облегчу тебе задачу - раз мы суммарно в них записали 1 Тб, то и считаем тоже 1 Тб

Butt-Head, для пущей убедительности добавлю, что код к абсолютно такой же задаче я писал в офисе Яндекса на собеседовании в 2011 году, - и меня взяли. Это задача пары часов уровня младшего разработчика.

1

Да чиТо за хрень

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

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

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

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

Сообщение от ct0r писал в офисе Яндекса на собеседовании

Так ты сейчас в Янедксе работаешь или уже откинулся ?

Сообщение от ct0r Это задача пары часов уровня младшего разработчика.

Это задача тех, кто занимается подобными вещами.

0

Сообщение от 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

1

Считали 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 Это задача тех, кто занимается подобными вещами.

Это была моя первая работа. О каких подобных вещах ты говоришь? Тут нет никакой специфики, должен каждый уметь.

1

Сообщение от ct0r Берем минимальное - 2, пишем в выходной файл его, считываем из файла, откуда мы взяли эту двойку, следующее число - 24.

Всё. Теперь идею понял. Спасибо.
Eraston, ты нуб, объяснять ваще не умеешь Но всё равно спасибо

Сообщение от ct0r Сейчас не в яндексе, а в его конкуренте

в гугле что ли?

Сообщение от ct0r О каких подобных вещах ты говоришь? Тут нет никакой специфики, должен каждый уметь.

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

0

0

Сообщение от Eraston Уровень понимания не зависит от уровня объяснения ©.

Пфффф.... Ты лунтик что ли?

0

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

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

1

Сообщение от ct0r но общее поверхностное представление - что вообще существует

Вот этого и достаточно.

Сообщение от ct0r Ты вроде как знаешь - быстрая сортировка и норм. И из-за незнания того

Почему же. Перед решением ответственной задачи я загляну в гугл и он отправит меня на хабр, стековерфлоу или сюда, где собственно я и узнаю о наилучшем методе сортировке в данном конкретном случае.
Видишь, даже мой тред называется: "Наиболее быстрый способ сортировки файла...". Я зашёл сюда, что бы узнать..
У человечества всё больше и больше знаний и забивать голову всякой ерундой, которую можно посмотреть на любом форуме, не имеет никакого смысла, собственно как и оценивать кандидата на собеседование аналогичными задачами. Сейчас более эффективна ссылочная память, то есть помнишь, что такое есть, примерное где применяется и главное, где посмотреть. Так больше в голову влезает
По этому я и говорил:

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

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

0

Сообщение от Butt-Head У человечества всё больше и больше знаний и забивать голову всякой ерундой

Ну, для программиста основы структур данных и алгоритмов - это, по сути, таблица умножения.

0

Сообщение от ct0r Впрочем облегчу тебе задачу - раз мы суммарно в них записали 1 Тб

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

0

Сообщение от ct0r можем сортировать за O(n)

смешно)
а почему через жесткий диск не попробовать?

0

Сообщение от Mr.X Ну, для программиста основы структур данных и алгоритмов - это, по сути, таблица умножения.

Смотря чем этот программист будет заниматься...

Добавлено через 4 минуты
Вот есть последовательность 3 1 4 1 5 9
на первом этапе мы записали 13 14 59 и все, памяти уже переписано эквивалентно исходной последовательности, а она еще не отсортирована. В чем я не прав?

0

Сообщение от shmkv Смотря чем этот программист будет заниматься...

Попробую угадать с трех раз. Хранением и обработкой данных с помощью алгоритмов?

0

0

Сообщение от shmkv Если бы... У нас очень много вакансий "программистов", где по факту человеку предстоит знаться другими вещами.

Ну так это и не программисты, а специалисты по другим вещам. Здесь же все типа программисты.

0

Сообщение от shmkv на первом этапе мы записали 13 14 59 и все, памяти уже переписано эквивалентно исходной последовательности

не очень понял суть вопроса...
Да, ты сделал три блока, отсортированных локально как бы, то есть внутри себя и записал их в файлы.
Далее открываешь одновременно все эти файлы, в данном случае с 13, 14 и 59 и читаешь из них (из каждого), первое значение, получается:
1
1
5
ищешь первое минимальное, - это один из первого файла, пишешь это значение (единицу) в результирующий файл и cдвигаешь ленту первого файла на одно значение и берёшь опять слепок ;)
Смари, тут просто хитрость, представь тре плёнки от фотоаппарата (ну раньше были плёночные фотоаппараты, в курсе? :D ) Вот ты кладёшь их на стол. Берёшь... ну не знаю, листочек А4 и вырезаешь прямоугольник в нём, что б в столбик там поместилось 3 слайда. Кладёшь этот листок на три плёнки свои на столе на начало плёнок. Видишь там в столбик три кадра в столбик (по кадру от каждой плёнке) (первые кадры), это как бы три значения. Ищешь минимальное значение и записываешь его в результирующий файл. После этого, ты рукой сдвигаешь ленту с кадрами, с которой ты "брал" кадр, влево на 1 кадр и смотришь опять в прямоугольное окно... и т.д.

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

Сообщение от Mr.X Ну так это и не программисты, а специалисты по другим вещам. Здесь же все типа программисты.

Алгоритмы и структуры данных требуются в 3..5 % вакансий программистов С++

0

Сообщение от Butt-Head Алгоритмы и структуры данных требуются в 3..5 % вакансий программистов С++

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

0