ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите решить задачу на С++
10 сообщений из 10, страница 1 из 1
Помогите решить задачу на С++
    #38793850
mershkovsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mershkovsql
Гость
Используя многопоточность, произвести сортировку файла размера 1111 мб.
В памяти при этом используя максимум 255 мб.
На выходе файл должен быть отсортирован побайтно, по возрастанию.
Задание необходимо реализовать на С(С++).
Генератор файла для сортировки необходимо написать самостоятельно.
Файл должен быть заполнен произвольными символами.
Сортировка файла должна производиться за время меньше 1 минуты.
...
Рейтинг: 0 / 0
01.11.2014, 17:55
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793868
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Организуешь пул потоков из пяти штук, которым разбрасываешь для внутренней сортировки
буфера по 50 мегабайт. Они эти буфера сортируют и сбрасывают во внешние файлы. Потом
образовавшиеся 23 файловых потока сортируешь слиянием. Возможно, тоже многопоточно.

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

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
01.11.2014, 18:28
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793927
mershkovsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mershkovsql
Гость
Dimitry Sibiryakov,
меня смущает как слиянием сортировать
...
Рейтинг: 0 / 0
01.11.2014, 20:57
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793929
mershkovsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mershkovsql
Гость
mershkovsql,

А вообще меня смущает все просто не понимаю видать тупой
...
Рейтинг: 0 / 0
01.11.2014, 21:00
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793930
Фотография Анатолий Широков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Анатолий Широков
Участник
mershkovsql,

Вообще передай привет преподавателю. Эту задачу можно решить, потребляя не более 255*sizeof(size_t) + const байт памяти с линейной сложностью (O(1111Мб)) в одном потоке.
...
Рейтинг: 0 / 0
01.11.2014, 21:02
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793945
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
mershkovsqlменя смущает как слиянием сортировать
Очень просто: сравниваешь два значения из входных потоков и пишешь в выходной меньшее из них.

Третий том Кнута к чтению рекомендую.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
01.11.2014, 21:32
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793949
Фотография Анатолий Широков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Анатолий Широков
Участник
это к вопросу о постановке задачи. зачем давать студентам решать задачу с помощью многопоточности, которая решается простым и элегантным способом без потоков:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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));
}
...
Рейтинг: 0 / 0
01.11.2014, 21:36
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38793976
mershkovsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mershkovsql
Гость
Анатолий Широков,

да забыл сказать они просили не считать байтов
...
Рейтинг: 0 / 0
01.11.2014, 22:22
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38794094
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mershkovsqlАнатолий Широков,

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

Второе. Тот кто давал задание и устанавливал лимиты времени скорее всего опирался на типовую конфигурацию.
На ноутах со слабенькими 2.5-блинчиками да еще и с мультипоточностью (сколько их будет? 4? 8? 16 потоков?)
ты просто просадишь I/O в ноль и не уложишся в минуту. А если делать в 1 поток - тогда зачем вообще потоки?
...
Рейтинг: 0 / 0
02.11.2014, 01:24
| Ответить | Цитировать | Написать  
Помогите решить задачу на С++
    #38794095
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
mershkovsql,
да как тут и сказали, корманная сортировка тут и никакой многопоточности не нужно.
ну можно разделить файл на N кусков, но тогда будет N *256 памяти а не 256.
...
Рейтинг: 0 / 0
02.11.2014, 01:31
| Ответить | Цитировать | Написать  
10 сообщений из 10, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите решить задачу на С++
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]