Здравствуйте, vitali_y, Вы писали:
_>еще неточность "Пусть у нас на диске есть файл размером 4 гигабайта" должно быть "Пусть у нас на диске есть файл размером от 4 гигабайт"?
ну размер от 4 до 16GB — тогда переполнения при сортировке подсчетом не будет — точнее DWORD хватит — идея скорее всего тут такая.
сколько ваш алгоритм работает — как понимаю 16 GB файл читается с диска примерно 10 минут,
т.е. чисто эмпирически — программа которая тратит максимум минут 20 — рабочая программа — если значительно больше — выбран неправильный способ.
могу ошибаться...
_>>еще неточность "Пусть у нас на диске есть файл размером 4 гигабайта" должно быть "Пусть у нас на диске есть файл размером от 4 гигабайт"? L>по-русски, я думаю, правильно будет "4 гигабайта"
имел ввиду "от 4" — вообщем это не важно — просто мне нравятся однозначные формулировки, что бы лишних вопросов не возникало.
Здравствуйте, WolfHound, Вы писали:
К>>Индексы-то зачем? Нужны счётчики, раз это сортировка подсчётом. WH>Гы. Произвольный доступ убъет всю производительность.
Конечно, убьёт.
Всё равно, индексы-то зачем?
Устраивать 4 миллиарда забегов по исходному файлу, что ли?
ну и идея практической реализации:
мы ограничены 256MB — т.е. для подсчета используем некий хеш (хеш-таблицу),
где наименее востребованные во времени данные сбрасываем на диск либо упаковываем — тут нужно подумать — чтобы разные крайние случаи обрабатывались эфФективно —
т.е. случай 16GB и все числа встречаются по 1 разу — ну и близкие...
"2. Программа должна эффективно использовать несколько ядер."
— ну а этим тебя запутали.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, WolfHound, Вы писали:
К>>>Индексы-то зачем? Нужны счётчики, раз это сортировка подсчётом. WH>>Гы. Произвольный доступ убъет всю производительность.
К>Конечно, убьёт.
Не убъет если подсчитывать за проход 256к индексов (в памяти).
Здравствуйте, letsurf, Вы писали:
L>Доброго времени суток!
L>Недавно столкнулся с задачей:
L>(привожу задание как оно есть)
L>Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.
Предлагаю следующее решение. Но оно будет платформозависимым.
Открываем файлмэппинг.
Фаза 1
Файл делим на некие куски, размер куска кратен странице памяти, надо подобрать наилучший размер. Эти куски сортируем независимо друг от друга, открывая на кусок view и сортируя его, прямо-таки в самом файле, конечно, испортив его. Получаем набор отсортированных кусков. Сортировку можно провести многопоточно.
Фаза 2
Закрываем все view. Открываем новые view, каждый — на начало своего куска, размер ViewSize = 4 Кб (может, можно и больше, надо подсчитать). Имеем, т.о. массив указателей на начала кусков.
Проходим по этому массиву, ищем минимальный элемент по указателю. Найдя — заносим его в результат, продвигаем указатель во view, а если при этом выходим за размер view, то переоткрываем view на следующий ViewSize. В общем, слияние упорядоченых последовательностей.
Очень быстро не будет, но и не 4 часа, я думаю. Доступ везде последовательный в Фазе 2. По памяти — можно уложить в 256 Мб (и даже меньше) , если правильно подобрать размеры.
PD>Проходим по этому массиву, ищем минимальный элемент по указателю. Найдя — заносим его в результат, продвигаем указатель во view, а если при этом выходим за размер view, то переоткрываем view на следующий ViewSize. В общем, слияние упорядоченых последовательностей.
Тут можно и похитрее. Проходим по этому массиву, находим все минимальные элементы (заносим в некий дополнительный список/массив номера view, где они встречались), после чего заносим в выходной файл это число столько раз, сколько оно встретилось, после чего продвигаем указатели во всех view, где оно встретилось). Так можно сократить число проходов.
SC>>И плодить страхокод с прагмами?
D>сомнительное замечание. Прагмы тем и хороши, что можно их убрать и должен остаться корректный код.
Хм, вообще, далеко не любую прагму можно убрать, я бы не поставил на работоспособность кода, из которого убрали #pragma pack к примеру.
Ну да ладно, а зачем вообще прагмы посреди кода? Да еще такие загадочные, типа
#pragma omp parallel for private(w) reduction(+:sum) schedule(static,1)
Task-based модель Tbb гораздо дружественее к С++, не требует от компилятора поддержки всякого нестандартного и дает более изящный код. Не говоря уж о о том, что пул потоков Tbb работает пошустрее, чем Omp в реализации MSCV(по крайней мере, на тот момент когда я в последний раз пользовался Omp). Наличие исходников Tbb тоже помогает, c openMP иногда просто неожиданно начинается непонятно что и ты никак не можешь узнать что именно. Я один раз целый день убил, пытаясь понять почему у меня все потоки имеют идентификатор ноль. Оказалось, MKL развлекается.
Короче, не-не-не, я однозначно отказался от OpenMP в пользу Tbb и ничуть об этом не жалею.
SC>И плодить страхокод с прагмами? Уж лучше православный С++-ный TBB.
Мне на ваши религиозные убеждения пофиг, у меня и у коллег никаких проблем с прагмами не было
Здравствуйте, vitali_y, Вы писали:
I>>>это задачка на radix sort _>>вряд ли.
_>да это классическая задача на radix sort, ну и сортировка подсчетом тут используется
Здравствуйте, letsurf, Вы писали:
L>Доброго времени суток!
L>Недавно столкнулся с задачей:
L>(привожу задание как оно есть)
L>Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.
Пробовал делать это задание
-Radix sort рулит, но требует столько же дополнительной памяти, сколько сортируемый массив => 1 chunk = 256мб/2
-merge из chunk'ов можно делать c с помощью кучи aka priority_queue
-тормозит общение с диском. fread/fwrite из MSVC с мьютексом на каждый вызов необходимо заменит на велосипед.
На реализации ассинхронности и многопоточности без использования левых библиотек я сломался
D14>Пробовал делать это задание D14>-Radix sort рулит, но требует столько же дополнительной памяти, сколько сортируемый массив => 1 chunk = 256мб/2 D14>-merge из chunk'ов можно делать c с помощью кучи aka priority_queue D14>-тормозит общение с диском. fread/fwrite из MSVC с мьютексом на каждый вызов необходимо заменит на велосипед. D14>На реализации ассинхронности и многопоточности без использования левых библиотек я сломался
похоже что ты неправильно понял как пользовать числовую сортировку,
ну и как всегда не внял правилу, что преждевременная оптимизация зло.
такие задачи решаются на листике бумаги — потом проверяется реализация.
по-рабоче-крестьянски — смысл такой:
1) понадобится дополнительное место на диске объемом в исходный файл;
2) выбирается основание системы счисления — пусть N — чтобы хватило отведенных 256MB оперативки;
3) сортировка делается в несколько (точнее в N) проходов
проход 1:
a) пробежался по файлу — вычитал все младшие разряды в ОП (в отведенные 256MB)
b) отсортировал получившийся массив с помощью сортировки подсчетом;
c) выписал отсортированные по младшему разряду числа во вспомогательный файл;
проход 2:
a) пробежался по вспомогательному файлу — вычитал второй разряд в ОП (в отведенные 256MB)
b) отсортировал получившийся массив с помощью сортировки подсчетом;
c) выписал отсортированные по второму разряду числа во 1 файл;
...
в этом алгоритме в данной реализации — узкое место это диск,
какой бы многоядерный не был у тебя процессор — тут ты существенного ускорения не получишь —
тут в задаче "заковырка" — для любителей многопроцессорности.
хотя этап b) можно распараллелить — если бороться за каждую секунду.
держись товарищ не ломайся
большая просьба, раз ты озаботился реализацией, если все же есть желание убедиться, что это работает —
а это работает именно так — задача то классическая —
поделись исходником со всеми
Перекуём баги на фичи!
