0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
|
||||||||||||||||
1 | ||||||||||||||||
Подскажите место с ошибкой в оптимизированном коде15.09.2018, 00:35. Показов 3936. Ответов 5
Метки нет (Все метки)
Прохожу курс по c++, стоит задача оптимизировать код электронной книги, в которой выводится мотивационное сообщение с процентом от всех людей, которых обогнал читатель при ограничении в кол-во запросов 10^6, номера страниц меньше 1000, а номера пользователей не превосходят 10^5.
Изначальный код, правильный, но медленный:
P.s: Ф-ция main:
0
|
15.09.2018, 00:35 | |
Ответы с готовыми решениями:
5
Не могу разобратся с ошибкой в приведенном ниже коде!!! Подскажите с ошибкой подскажите с ошибкой в программе Помогите разобраться с ошибкой в коде удаления первого слов и первой буквы |
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
|
|
25.09.2018, 13:31 [ТС] | 3 |
Kuzia domovenok, да с ним тоже делал, но не приняло, пришлось такие извращения вытворять
0
|
25.09.2018, 13:36 | 4 |
Vakarine, это неверный подход к решению проблем. Вы чего-то не поняли, получили ошибку и вместо её исправления делаете что-то ещё, исходя из неверного понимания. Например непонимания условия.
Сделай map Лучше покажи полное условие.
0
|
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
|
|
25.09.2018, 20:29 [ТС] | 5 |
Kuzia domovenok, не, решение у меня работало нормально, но время работы было слишком большим. Условие смогу отправить только через ≈5 часов
Добавлено через 6 часов 26 минут Kuzia domovenok, Условие Разработайте систему стимулирования чтения электронных книг. Для простоты будем считать, что книга всего одна, но её одновременно читают много людей. Необходимо следить за прогрессом чтения у всех пользователей и выводить мотивирующие уведомления. А именно, ваша программа должна обрабатывать следующие события: READ user page — сохранить факт того, что пользователь под номером userдочитал книгу до страницы page. Если ранее такой пользователь не встречался, необходимо его добавить. Гарантируется, что в рамках одного пользователя номера страниц в соответствующих ему событиях возрастают. CHEER user — сообщить пользователю user, какая доля существующих пользователей (не считая его самого) прочитала меньшую часть книги, чем он. Если этот пользователь на данный момент единственный, доля считается равной 1. Если для данного пользователя пока не было ни одного события READ, доля считается равной 0, а сам пользователь не учитывается при вычислении долей для других пользователей до тех пор, пока для него не случится событие READ. Формат входных данных В первой строке вводится количество запросов Q — натуральное число, не превосходящее 10^6. В следующих Q строках в соответствии с описанным выше форматом вводятся запросы. Гарантируется, что все вводимые числа целые и положительные, при этом номера пользователей не превосходят 10^5, а номера страниц не превосходят 1000. Формат выходных данных Для каждого запроса CHEER user выведите единственное вещественное число от 0 до 1 — долю пользователей, прочитавших меньше страниц, чем user. Формат вывода этого числа должен быть в точности таким же, как в опубликованном ниже медленном решении. Ограничения 4 секунды на выполнение всех запросов. Все описанные в условии гарантии действительно справедливы для всех тестов, на которых будет запускаться ваша программа. Проверять корректность тестов не нужно.
0
|
3390 / 1913 / 571
Регистрация: 09.04.2015
Сообщений: 5,365
|
|||||||||||
28.09.2018, 12:19 | 6 | ||||||||||
Эффективная организация данных обеспечивает до 90% быстродействия обработки.
Ваш подход по построению связных списков является очень существенным тормозом в быстродействии. Мое мнение в классе для хранения данных надо создать два массива: 1. массив пользователей (допустим Users), тип данных unsigned int или unsigned short из 10^5 элементов (или на один больше если устранить пересчет номеров пользователя и допустить номера пользователей от 0 до 10^5 включительно). В этом массиве храниться сколько страниц прочитал пользователь, определяемых по событию READ Имя/номер пользователя нигде не хранится, а определяется номером элемента массива. Исходное состояние инициализируется нулем в конструкторе, и обозначает что данный пользователь прочитал 0 страниц. 2. массив страниц книги (допустим Pages), тип данных unsigned long или long из 1000 элементов (по максимальному числу страниц в книге). В этом массиве хранится для каждой страницы в порядке очередности, сколько пользователей их уже прочитали. Исходное состояние инициализируется нули в конструкторе, и обозначает что никто еще ничего не читал. Сразу необходимо отметить одну особенность элемента Pages[0], из-за условия то в этом элементе по сути будет хранится число пользователей, которые начали читать книгу. Функции конструктора ясны по выше приведенным описаниям. Обработка события READ сводится к увеличению на единицу числа прочитанных страниц
PS Часто по таким подходам в организации хранения данных (без динамических массивов) мне пытаются указать, что происходит избыточное занятие памяти, однако если сравнить например Вашу модель данных и сколько она занимает памяти при числе пользователей хотя бы половина от максимальной, то избыточности уже и незаметно. А по скорости обработки выигрыш должен быть большой.
0
|
28.09.2018, 12:19 | |
28.09.2018, 12:19 | |
Помогаю со студенческими работами здесь
6
Программа завершается с ошибкой, подскажите почему Объясните пожалуйста одно место в коде Как отследить место ошибки в коде? Как передать текст из textbox в определенное место в коде Найти в коде место, где происходит обращение к function Почему блок с fixed занимает место над блоком, который идёт в коде за ним? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |