Есть массив например структур размером x байт(пусть 50). Размер массива террабайт 10-20.
Вопрос как это чудо отсортировать.
Пусть у нас будет оперативка 2 гига и свободное место террабайт.

Встречный вопрос, откуда возьмется этот массив, если для него нет места?

Ну а вообще тут спасет т.н. компрессия без потери качества, т.е. в простейшем случае - сохранение не всех данных, а только уникальных плюс число раз их упоминания.

Я бы поэксперементировал с разреженными файлами http://ru.wikipedia.org/wiki/Разрежённый_файл. Соответственно, 2 файл-мэппинга, один - изначально полностью разреженный, второй - полностью забитый, данные постепенно перетекают из первого во второй. Может получиться... 

Вообще, ерунду гоню. Какая разница, сколько у тебя свободного места? Массив один, просто в нем записи перемещаются. Погляди, например, http://ru.wikipedia.org/wiki/Quicksort То есть, тебе нужно свободного места только для одной записи.

Это сообщение отредактировал(а) okkonst - 3.10.2010, 23:13

Enelar, 
Используй сортировку слияниями.

Сортировка_слиянием

Правда сортироваться  будет пару месяцев.
Так что лучше закозать кластер.

Это сообщение отредактировал(а) Pavia - 3.10.2010, 23:31

Угу. И как ты предлагаешь сливать массивы при имеющемся 1 терабайте свободного места из потребных 15?

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

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

Это сообщение отредактировал(а) okkonst - 4.10.2010, 01:07

okkonst, Винда не поддерживает 10тб память. Так что придется тебе проецировать по частям. А даже если и поддерживало бы то при памяти в 2Гб имели бы кучу промахов. Т.е дисковых операций больше причем на порядки. Сортировка слияниями как раз нацелена на уменьшения дисковых операций.

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

Не надо думать что в ОС реализованы все алгоритмы. К чему бы им тогда каждый год  выпускали новую ОС?

Как раз, 2-я частями, со скольжением "окон отображения" к опорному элементу



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



Речь о том, что лучше ОС никто не знает, что свопить. Ну, или, скажем так, МАЛО кто  

Это 20*2^40/50=4.4*10^11 элементов. При сортировке слиянием в 2 хода это получаются блоки по 660 тыс. элементов, 33 мегабайта - вполне сносно.
Только надо понимать, что на диске нужно иметь пустое пространство не менее, чем объём исходных данных. Иначе придётся усложнять процесс.

Только при условии что объём свободного пространства меньше объёма данных. И то - ты прав, переворот виртуальный, при двухпроходке на первой стадии, при трёхпроходке на второй.

Если свободного места недостаточно - потребуется трёхпроходное слияние. Но и при 1 терабайте свободного места и 20 терабайтах исходных данных получается вполне ничего...

Добавлено через 5 минут и 59 секунд
PS. Но я не могу представить себе пока практическую ценность подобного занятия.

Это сообщение отредактировал(а) Akina - 4.10.2010, 07:45

реализовать быструю сортировку, только на файле (двунаправленную итерацию по элементам и обмен там сделать несложно)

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

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

Ответ на вопрос как свести количество дисковых операций - сортировка слиянием? спасибо.
P.S время не очень играет я сказал что раньше месяца не рассчитывайте.

Во первых сортировка слиянием работает последовательно с файлами. Так что тут понятно что операций будет минимум. А чтобы их еще уменьшить надо сливать не 2 блока, а как можно больше.  К примеру 8.  Соответственно в алгоритме сортировки $O(n*Log_8(n))$ логарифм будет иметь основание 8 тем самым 2^38 данных понадобится всего 13 проходов против 38 (при скорости чтения диска 100мб\с один проход это день). 
Разбиваем все данные на файлы по 0.5 гигабайта.
Сортируем эти кусочки в памяти. Потом берем по 8 файлов и начинаем сливать.
Чтение и запись делать асинхронно, небольшими кусочками по 1-8 мбайт. Возможно организовать кэш с предвыборкой 8 ассоциативный.
Для повышения надежности вести логирование.  Было бы достаточно место можно без него. Перед тем как  что-то удалить записать на диск.
После прочтения делаешь конкатенацию файлов.  
При сливании 8 буферов смотришь в каком блоке наименьшее число больше наименьших чисел из других блоков. Max min(a[8]) сливаешь все числа которые выше этого числа потом читаешь буфер из этого файла.

Добавлено через 2 минуты и 2 секунды
PS. Больше 8 блоков процессор может не потянуть, скорости не хватит.

Да, спасибо. Теперь нужно узнать как отрезать фаил и где достать 2 бесперебойника (на всякий).

эта инфа в отдельных файлах в беспорядке или как-то (например частично) упорядочена?