Помогите решить задачу на С++

Используя многопоточность, произвести сортировку файла размера 1111 мб.
В памяти при этом используя максимум 255 мб.
На выходе файл должен быть отсортирован побайтно, по возрастанию.
Задание необходимо реализовать на С(С++).
Генератор файла для сортировки необходимо написать самостоятельно.
Файл должен быть заполнен произвольными символами.
Сортировка файла должна производиться за время меньше 1 минуты.

Организуешь пул потоков из пяти штук, которым разбрасываешь для внутренней сортировки
буфера по 50 мегабайт. Они эти буфера сортируют и сбрасывают во внешние файлы. Потом
образовавшиеся 23 файловых потока сортируешь слиянием. Возможно, тоже многопоточно.

Какая часть тебя затрудняет?

Posted via ActualForum NNTP Server 1.5

Dimitry Sibiryakov,
меня смущает как слиянием сортировать

mershkovsql,

А вообще меня смущает все просто не понимаю видать тупой

mershkovsql,

Вообще передай привет преподавателю. Эту задачу можно решить, потребляя не более 255*sizeof(size_t) + const байт памяти с линейной сложностью (O(1111Мб)) в одном потоке.

mershkovsql
меня смущает как слиянием сортировать

Очень просто: сравниваешь два значения из входных потоков и пишешь в выходной меньшее из них.

Третий том Кнута к чтению рекомендую.

Posted via ActualForum NNTP Server 1.5

это к вопросу о постановке задачи. зачем давать студентам решать задачу с помощью многопоточности, которая решается простым и элегантным способом без потоков:

void sort(std::istream& in, std::ostream &out)
{
    size_t counter[256] = {0};
    char ch = 0;
    while( in.read(&ch, 1) )
        counter[static_cast<unsigned char>(ch)]++;
    for(unsigned char byte = 0; byte < 256; byte++ )
        for(size_t j = 0; j < counter[byte]; j++ )
            out.put(static_cast<char>(byte));
}

Анатолий Широков,

да забыл сказать они просили не считать байтов

mershkovsql
Анатолий Широков, да забыл сказать они просили не считать байтов

Первое. Данная задача (сортировка байтов в терабайтном файле) эффективно решается "Сортировкой подсчётом".
Это по сути генерация гистограммы и генерация выхода из нее.

Второе. Тот кто давал задание и устанавливал лимиты времени скорее всего опирался на типовую конфигурацию.
На ноутах со слабенькими 2.5-блинчиками да еще и с мультипоточностью (сколько их будет? 4? 8? 16 потоков?)
ты просто просадишь I/O в ноль и не уложишся в минуту. А если делать в 1 поток - тогда зачем вообще потоки?

mershkovsql,
да как тут и сказали, корманная сортировка тут и никакой многопоточности не нужно.
ну можно разделить файл на N кусков, но тогда будет N *256 памяти а не 256.