| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сортировка огромных данных |
| Автор: Enelar 3.10.2010, 21:56 |
| Есть массив например структур размером x байт(пусть 50). Размер массива террабайт 10-20. Вопрос как это чудо отсортировать. Пусть у нас будет оперативка 2 гига и свободное место террабайт. |
| Автор: djamshud 3.10.2010, 22:06 |
| Встречный вопрос, откуда возьмется этот массив, если для него нет места? Ну а вообще тут спасет т.н. компрессия без потери качества, т.е. в простейшем случае - сохранение не всех данных, а только уникальных плюс число раз их упоминания. |
| Автор: okkonst 3.10.2010, 23:06 | ||
Я бы поэксперементировал с разреженными файлами http://ru.wikipedia.org/wiki/Разрежённый_файл. Соответственно, 2 файл-мэппинга, один - изначально полностью разреженный, второй - полностью забитый, данные постепенно перетекают из первого во второй. Может получиться... Вообще, ерунду гоню. Какая разница, сколько у тебя свободного места? Массив один, просто в нем записи перемещаются. Погляди, например, http://ru.wikipedia.org/wiki/Quicksort То есть, тебе нужно свободного места только для одной записи. |
| Автор: Pavia 3.10.2010, 23:29 |
| Enelar, Используй сортировку слияниями. http://ru.wikipedia.org/wiki/Сортировка_слиянием Правда сортироваться будет пару месяцев. Так что лучше закозать кластер. |
| Автор: okkonst 4.10.2010, 00:25 | ||
Угу. И как ты предлагаешь сливать массивы при имеющемся 1 терабайте свободного места из потребных 15? |
| Автор: Pavia 4.10.2010, 00:40 |
| okkonst, Есть такая замечательная процедура как Truncate она обрезает файл без его перемещения. Сливать с конца файла порциями да хоть по 100мбайт. А потом переворот. Перевороты можно делать виртуально меня знак сортировки. |
| Автор: okkonst 4.10.2010, 01:05 |
| А в чем тут принципиальный выигрыш перед той же быстрой сортировкой? А геморроя значительно больше. А с учетом использования FileMapping можно значительно выиграть за счет уменьшения числа дисковых операций, причем, об этом будет думать сама ось, а ей виднее |
| Автор: Pavia 4.10.2010, 01:13 | ||
| okkonst, Винда не поддерживает 10тб память. Так что придется тебе проецировать по частям. А даже если и поддерживало бы то при памяти в 2Гб имели бы кучу промахов. Т.е дисковых операций больше причем на порядки. Сортировка слияниями как раз нацелена на уменьшения дисковых операций. Добавлено через 2 минуты и 37 секунд
Не надо думать что в ОС реализованы все алгоритмы. К чему бы им тогда каждый год выпускали новую ОС? |
| Автор: okkonst 4.10.2010, 01:26 | ||||||
Как раз, 2-я частями, со скольжением "окон отображения" к опорному элементу
Ну, может, не знаю. На первый взгляд, мне показалось иначе
Речь о том, что лучше ОС никто не знает, что свопить. Ну, или, скажем так, МАЛО кто |
| Автор: Akina 4.10.2010, 07:39 | ||||||
Это 20*2^40/50=4.4*10^11 элементов. При сортировке слиянием в 2 хода это получаются блоки по 660 тыс. элементов, 33 мегабайта - вполне сносно. Только надо понимать, что на диске нужно иметь пустое пространство не менее, чем объём исходных данных. Иначе придётся усложнять процесс.
Только при условии что объём свободного пространства меньше объёма данных. И то - ты прав, переворот виртуальный, при двухпроходке на первой стадии, при трёхпроходке на второй.
Если свободного места недостаточно - потребуется трёхпроходное слияние. Но и при 1 терабайте свободного места и 20 терабайтах исходных данных получается вполне ничего... Добавлено через 5 минут и 59 секунд PS. Но я не могу представить себе пока практическую ценность подобного занятия. |
| Автор: maxim1000 4.10.2010, 09:00 |
| реализовать быструю сортировку, только на файле (двунаправленную итерацию по элементам и обмен там сделать несложно) когда сортируемые части массива будут становиться достаточно маленькими, можно попробовать читать их в память и сортировать там для ускорения |
| Автор: Enelar 5.10.2010, 00:08 |
| Ситуация очень простая. В течении нескольких лет в фаилы сливали инфу. Теперь скинули на один сервер у меня задача отсортировать. Я тут подумал решает либо swap раздел, где можно с файлом работать как с оперативкой - меняя любой байт, либо отрезать от файлов по кусочкам. Ответ на вопрос как свести количество дисковых операций - сортировка слиянием? спасибо. P.S время не очень играет я сказал что раньше месяца не рассчитывайте. |
| Автор: Pavia 5.10.2010, 12:42 | ||
Во первых сортировка слиянием работает последовательно с файлами. Так что тут понятно что операций будет минимум. А чтобы их еще уменьшить надо сливать не 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 блоков процессор может не потянуть, скорости не хватит. |
| Автор: Enelar 5.10.2010, 22:53 |
| Да, спасибо. Теперь нужно узнать как отрезать фаил и где достать 2 бесперебойника (на всякий). |
| Автор: baldina 6.10.2010, 00:14 | ||
эта инфа в отдельных файлах в беспорядке или как-то (например частично) упорядочена? |
| Автор: Enelar 6.10.2010, 01:56 |
| По времени. Там записывалась пара данных a = b a получается от клиента и зависит от параметра на нем b получается из а по неизвестному алгоритму(программой чужой конторы). Нужно отсортировать по b Ну еще несколько параметров которые не играют роли. |
| Автор: gcc 6.10.2010, 07:51 |
| еще есть unix sort, он отсортирует хитро, но конечно не быстро... примерно как я понял 120 гиг за 12 часов вот http://forum.vingrad.ru/index.php?showtopic=309203&view=findpost&p=2208331 обсуждали задачу от yandex (яша предлагал unix sort) |
| Автор: W4FhLF 8.10.2010, 07:53 | ||
Буквально сегодня наткнулся на интересную разработку, код только недавно открыли: http://code.google.com/p/back40computing/wiki/RadixSorting Сортировка 32х битных пар <key, value> на GPU со скоростью 780 млн. значений / сек (это на топовой вид.хе GTX480). Самый быстрый в мире показатель для одиночного программируемого устройства. |
| Автор: Pavia 8.10.2010, 10:10 |
| W4FhLF, Для чисел сортировка линейна. 32х битных пар <key, value> сортировка я так понимаю по ключу. Значит 32/8 имеем 4 прохода. Пропускная способность памяти компьютера<-> видео карта 20Гбайт/с*8 =160Гбит/с поделим на 64бит key+ value и на 4 прохода и на 2 операции чтение запись. 312.5м операций в секунду. В видео карте память имеет скорость выше 370 гбит/с. 722 миллион операций в секунду. Молодцы разработчики выжали максимум. Это не так интересно. В базах данных используется 128битные ключи. Да и определяет скорость самое медленное устройство. Правда продвинутые базы данных хранят всё в памяти. |
| Автор: W4FhLF 8.10.2010, 10:34 |
| Pavia, понятно, что bottleneck будет на I/O HDD. Просто инфа интересная, решил поделиться |
