Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.
Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно отсортировать (размер файла до 16Gb, размер кратен четырем),
в argv[2] — имя файла, в который нужно записать отсортированные данные.
Ограничения:
1. Программа не может рассчитывать, что возможно выделить более 256Mb памяти.
2. Программа должна эффективно использовать несколько ядер.
Сразу скажу, что сделал изначально с ошибкой — сортирует файлы размером <= 256Mb либо размером кратным этому числу, т.е. файл размером 260Mb не будет отсортирован корректно, потеряется последний int(если sizeof(int) == 4). Но вопрос не в этом, программа компилируется и даже сортирует файл: 4G она обрабатывает за ~4 часа. Просьба покритиковать код, указать на явные ошибки(если есть) работы с потоками(до этой задачи никогда не работал с потоками вообще) ну и проблемы кода в целом.
добавил разметку — Кодт
12.06.10 19:15: Перенесено модератором из 'C/C++' — Кодт
18.06.10 15:10: Перенесено модератором из 'C/C++. Прикладные вопросы'. Пожалуй, собственно к языку реализации тема отношения не имеет. — Кодт
Здравствуйте, letsurf, Вы писали:
L>Но вопрос не в этом, программа компилируется и даже сортирует файл: 4G она обрабатывает за ~4 часа. Просьба покритиковать код
Критикую. 4 часа на сортировку файла в 4 Гб это писец, мягко говоря. В Яндекс тебя не возьмут. Выкини и перепиши по новой
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, letsurf, Вы писали:
L>>Но вопрос не в этом, программа компилируется и даже сортирует файл: 4G она обрабатывает за ~4 часа. Просьба покритиковать код
KP>Критикую. 4 часа на сортировку файла в 4 Гб это писец, мягко говоря. В Яндекс тебя не возьмут. Выкини и перепиши по новой
Здравствуйте, letsurf, Вы писали:
L>Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.
L>Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно отсортировать (размер файла до 16Gb, размер кратен четырем),
У тебя есть файл с 32-битными числами.
Таких чисел может быть up to 4 млрд.
Нужно вычислить индексы вхождения каждого числа в исходный файл.
Индексы вхождения можно записать в промежуточный файл.
Промежуточный файл размером 16Gb, где в каждые 4b записывается индекс вхождения соответствующего числа в исходный файл.
Потом на основе индексов вхождения собираем файл результата.
Здравствуйте, letsurf, Вы писали:
L>Доброго времени суток!
L>Недавно столкнулся с задачей:
L>(привожу задание как оно есть)
L>Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.
L>Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно отсортировать (размер файла до 16Gb, размер кратен четырем), L>в argv[2] — имя файла, в который нужно записать отсортированные данные.
L>Ограничения: L>1. Программа не может рассчитывать, что возможно выделить более 256Mb памяти. L>2. Программа должна эффективно использовать несколько ядер.
Запустить несколько процессов, которые будут читать из исходного файла отдельные непересекающиеся фрагменты. Размер фрагмента — 256Mb, так что получается 16 процессов. Прочитав фрагмент целиком в память напускаем на него qsort. Получаем отсортированный фрагмент исходного файла, сохраняем его на диск. Получаем 16 отсортированных фрагментов исходного файла.
Теперь остается "слить" промежуточные файлы в один — сортировка слиянием, тут проблем нет. Можно запустить один процесс, который будет сливать все 16 фрагментов, а можно в несколько этапов слияние делать. Например, запустить 8 процессов слияния, которые из 16 фрагментов сдалют 8 по 512Mb, потом из 8 — 4 и т.д. На этом этапе все упрется в производительность файловой системы — из фрагментов надо будет читать по 32бита.
Здравствуйте, alsemm, Вы писали:
A>Здравствуйте, letsurf, Вы писали:
A>Запустить несколько процессов, которые будут читать из исходного файла отдельные непересекающиеся фрагменты. Размер фрагмента — 256Mb, так что получается 16 процессов. Прочитав фрагмент целиком в память напускаем на него qsort. Получаем отсортированный фрагмент исходного файла, сохраняем его на диск. Получаем 16 отсортированных фрагментов исходного файла. A>Теперь остается "слить" промежуточные файлы в один — сортировка слиянием, тут проблем нет. Можно запустить один процесс, который будет сливать все 16 фрагментов, а можно в несколько этапов слияние делать. Например, запустить 8 процессов слияния, которые из 16 фрагментов сдалют 8 по 512Mb, потом из 8 — 4 и т.д. На этом этапе все упрется в производительность файловой системы — из фрагментов надо будет читать по 32бита.
Примерно так я и сделал, но, видимо, это не самый быстрый способ.
Здравствуйте, letsurf, Вы писали:
L>Здравствуйте, alsemm, Вы писали:
A>>Здравствуйте, letsurf, Вы писали:
A>>Запустить несколько процессов, которые будут читать из исходного файла отдельные непересекающиеся фрагменты. Размер фрагмента — 256Mb, так что получается 16 процессов. Прочитав фрагмент целиком в память напускаем на него qsort. Получаем отсортированный фрагмент исходного файла, сохраняем его на диск. Получаем 16 отсортированных фрагментов исходного файла. A>>Теперь остается "слить" промежуточные файлы в один — сортировка слиянием, тут проблем нет. Можно запустить один процесс, который будет сливать все 16 фрагментов, а можно в несколько этапов слияние делать. Например, запустить 8 процессов слияния, которые из 16 фрагментов сдалют 8 по 512Mb, потом из 8 — 4 и т.д. На этом этапе все упрется в производительность файловой системы — из фрагментов надо будет читать по 32бита.
L>Примерно так я и сделал, но, видимо, это не самый быстрый способ.
Это не способ небыстрый, а реализация кривая. Потому что если открыть исходный файл только один раз (static FileWrapper m_fileToSort), т.е. создать единственный дескриптор FILE*, то читать через него асинхронно из нескольких потоков очень тяжело.
Мне вообще непонятно, что у тебя в коде происходит. Т.е. может оно конечно и выдает корректный результат, но асинхронностью тут и не пахнет.
Здравствуйте, alsemm, Вы писали:
L>>Примерно так я и сделал, но, видимо, это не самый быстрый способ. A>Это не способ небыстрый, а реализация кривая. Потому что если открыть исходный файл только один раз (static FileWrapper m_fileToSort), т.е. создать единственный дескриптор FILE*, то читать через него асинхронно из нескольких потоков очень тяжело. A>Мне вообще непонятно, что у тебя в коде происходит. Т.е. может оно конечно и выдает корректный результат, но асинхронностью тут и не пахнет.
Исходный файл читается цепочками по 64Mb, которые сортируются qsort'ом и складываются на диск. Этот процесс не занимает много времени, основное же время у меня уходит на слияние этих цепочек.
Здравствуйте, letsurf, Вы писали:
L>Ограничения: L>1. Программа не может рассчитывать, что возможно выделить более 256Mb памяти. L>2. Программа должна эффективно использовать несколько ядер.
Просто как идея, не знаю на сколько будет (не)эффективно: cчитывать числа из исходного файла и записывать в n файлов, каждый их которых может уместить m 32-битных беззнаковых чисел. Таким образом в первый файл попадут числа из диапозона (0;m — 1), во второй (m;2*m — 1) и т.д. Теперь считываем в цикле содержимое мелких файлов, сортируем и пишем в выходной файл.
из очевидных недостатков это конечно крайне низний технологический уровень
-есть такая штука как stxxl — это как раз и есть stl для объемов данных которые в память не влезают, но вы ей не воспользовались
-RAII презрет, зачем эти голые CRITICAL_SECTION Enter\Leave, что нельзя было обертками воспользоваться из ATL или буста?
-файлы зачем-то читаются в память — нафиг это нужно? с файл мэппингом было бы гораздо проще
-зачем-то вручную создаются потоки — опять дикость. Гораздо лучше было бы воспользоваться ОМP
ошибок достаточно много, даже если вы и решили задачу правильно слив засчитан
Здравствуйте, rm822, Вы писали:
R>из очевидных недостатков это конечно крайне низний технологический уровень R>-есть такая штука как stxxl — это как раз и есть stl для объемов данных которые в память не влезают, но вы ей не воспользовались R>-RAII презрет, зачем эти голые CRITICAL_SECTION Enter\Leave, что нельзя было обертками воспользоваться из ATL или буста? R>-файлы зачем-то читаются в память — нафиг это нужно? с файл мэппингом было бы гораздо проще R>-зачем-то вручную создаются потоки — опять дикость. Гораздо лучше было бы воспользоваться ОМP
R>ошибок достаточно много, даже если вы и решили задачу правильно слив засчитан
Привет!
Преждевременная оптимизация и здесь тоже зло. Первым делом избавься от идеи многопоточности для первого варианта решения задачи. Очень легко наступить на грабли, получив два параллельных потока, работающих одновременно с диском.
К чему четыре потока чанксортеров, если они читают из файла под критической секцией? Только чтобы параллельно запустить сортировку в другом, который уже свой чанк прочитал? Это можно было бы сделать более прямым способом, да и не нужно, по крайне мере в первой версии — сортировка чанка вряд ли занимает существенное время, чтобы её сразу делать параллельно.
Чанксортер читает под критической секцией, потом сортирует и пишет в файл без оной — писать может параллельно с чтением другим чанксортером — io деградирует?
Не до конца понял, как происходит merge, но по-моему так: 2 куска читаются в память, затем сливаются std::merge-ом в память, затем сбрасываются на диск. Во-первых, читать в память такими кусками ни к чему, можно сливать по мере чтения. Тут можно сделать что-то вроде istream_iterator или переписать руками без использования merge. Можно, конечно, и читать в память кусками и сливать std::merge-ом по-старому, но не выделять память под массивы левой, правой и результирующей части в mergeTwoFilesIntoOne при каждом слиянии двух файлов! Ну и во-вторых, не стоит сливать файлы всего по два, тем более в двух merger-ах, которые параллельно насилуют диск и перегонять бедные int-ы по несколько раз из файлов в файл. Нужно слить сразу все чанки — смотри в сторону std::priority_queue.
Здравствуйте, Andruh, Вы писали:
A>К чему четыре потока чанксортеров, если они читают из файла под критической секцией? Только чтобы параллельно запустить сортировку в другом, который уже свой чанк прочитал?
Да, для этого.
A>Не до конца понял, как происходит merge, но по-моему так: 2 куска читаются в память, затем сливаются std::merge-ом в память, затем сбрасываются на диск.
все верно, именно это он и делает.
A>Можно, конечно, и читать в память кусками и сливать std::merge-ом по-старому, но не выделять память под массивы левой, правой и результирующей части в mergeTwoFilesIntoOne при каждом слиянии двух файлов!
ага, на это уже сам обратил внимание.
A>Ну и во-вторых, не стоит сливать файлы всего по два, тем более в двух merger-ах, которые параллельно насилуют диск и перегонять бедные int-ы по несколько раз из файлов в файл. Нужно слить сразу все чанки — смотри в сторону std::priority_queue.
Здравствуйте, vitali_y, Вы писали:
_>должно быть написано не "как 2^30 32-битных беззнаковых чисел" а "как 2^32 32-битных беззнаковых чисел" _>или где неточность?
нет, все верное написано, т.е. 2^30 32-битных числа занимают как раз 4Г