Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Ded_Vasilij
231 / 213 / 15
Регистрация: 01.09.2012
Сообщений: 2,103
#1

Контроль времени выполнения программы - C++

26.01.2013, 09:51. Просмотров 1288. Ответов 6
Метки нет (Все метки)

Добрый день. У меня маленькая проблемка. Есть задача.
Задача А - Гистограмма
Ограничение времени: 1 с
Ограничение памяти: 1024 M
Вовочка ломает систему безопасности Пентагона. Для этого ему понадобилось узнать, какие символы в секретных зашифрованных посланиях употребляются чаще других. Для удобства изучения Вовочка хочет получить графическое представление встречаемости символов. Поэтому он хочет построить гистограмму количества символов в сообщении. Гистограмма это график, в котором каждому символу, встречающемуся в сообщении хотя бы один раз, соответствует столбик, высота которого пропорциональна количеству этих символов в сообщении.
Формат входных данных
Входной файл содержит зашифрованный текст сообщения. Он содержит строчные и прописные латинские буквы, цифры, знаки препинания (“.”, “!”, “?”, “:”, “-”, “,”, “;”, “(”, “)”), пробелы и переводы строк. Размер входного файла не превышает 10^4 байт. Текст содержит хотя бы один непробельный символ. Все строки входного файла не длиннее 200 символов.
Формат результата
Для каждого символа c кроме пробелов и переводов строк выведите столбик из символов “#”, количество которых должно быть равно количеству символов c в данном тексте. Под каждым столбиком напишите символ, соответствующий ему. Отформатируйте гистограмму так, чтобы нижние концы столбиков были на одной строке, первая строка и первый столбец были непустыми. Не отделяйте столбики друг от друга. Отсортируйте столбики в порядке увеличения кодов символов.
Собственно говоря проблема только в ограничениях. как составить гистограмму, посчитать количество символов за линейное время я знаю. Вопрос такой: как проконтролировать ограничения по памяти и времени выполнения.
Эта задача была предложена на олимпиаде по программированию. Там была автоматическая система проверки. И на все мои попытки впихать ей свое решение писала либо "время выполнения больше одной секунды", либо ошибку там какую то. давно было не помню.
Код чуть позже выложу. подскажите как проконтролировать время выполнения программы.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.01.2013, 09:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Контроль времени выполнения программы (C++):

Подсчёт времени выполнения программы - C++
Здравствуйте, помогите разобраться, не получается подсчитать время выполнения программы. Вот код: #include <time.h> #include...

ускорение времени выполнения программы - C++
здравствуйте. решал олимпиадную задачу: ...Он берет произвольное положительное число А и выписывает на доске арифметическую прогрессию...

Организовать контроль времени работы программного обеспечения - C++
Консольное приложение Win32 Текст задачи: Организовать контроль времени работы программного обеспечения. Исходные параметры: текущее...

Контроль числа запусков программы - C++
Друзья, как в exe файле записать возможное кол-во числа запусков программы. Может кто-нибудь сталкивался с такой задачей. или владеет...

Измерение времени выполнения - C++
Подскажите пожалуйста как измерить время выполнения чего-то с наносекундной точностью. std::chrono::high_resolution_clock::time_point...

Оптимизация времени выполнения - C++
Доброго времени суток. Есть следующая задача. Задача олимпиадная, потому учитывается время выполнения, нужно вложится в 1секунду. Мой код...

6
Hrobak
289 / 169 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
26.01.2013, 13:50 #2
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <ctime>
 
int main()
{
    clock_t start = clock();
    ...
    std::cout<<static_cast<long double>(clock()-start)/CLOCKS_PER_SEC<<std::endl;
    return 0;
}
Можно еще исполнять свой код на сервисах типа ideone. Лимит времени иногда может быть вызван использованием cin или cout в циклах; если требуется ввести/вывести более 10000 строк, то лучше использовать scanf/printf.
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
26.01.2013, 14:01 #3
Цитата Сообщение от Hrobak Посмотреть сообщение
Лимит времени иногда может быть вызван использованием cin или cout в циклах; если требуется ввести/вывести более 10000 строк, то лучше использовать scanf/printf.
Пока scanf разбирает строку с форматом каждый раз, всё время кончится. А вот
C++
1
cin.sync_with_stdio(false)
может быть полезно.
1
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.01.2013, 15:24 #4
Это олимпиадная задача. Ограничение по времени там обычно выбирается с хорошим запасом. Делается это для того, чтобы сразу отсечь решения "в лоб". Поэтому если олимпиадная задача на проверяющем сервере не укладывается по времени, то это означает только одно: ваш алгоритм гов неэффективный, придумывайте другой. Практически гарантированно дело не во вводе-выводе, не в кешах или в чём-то ещё. У себя на машине проверять таймлимит иначе, чем по бинарной шкале "ответ получен сразу" — "программа всё ещё думает", имеет смысл только в одном случае: если у вас машина, компилятор, ключи, операционка и т. д. идентичны проверяющему серверу, и при этом ваша программа не в пять раз быстрее таймлимита, а вы очень хотите втиснуться в него на последней миллисекунде.
0
Hrobak
289 / 169 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
26.01.2013, 15:33 #5
~OhMyGodSoLong~, достаточно часто олимпиадная задача падает по времени из-за ввода/вывода. Если вводится будет к примеру 10^10 чисел, то даже с запасом времени (20 секунд TL) при использовании cin задача упадет.
На недавнем CF раунде некоторые решения упали из-за cin/cout.
Но в конкретном случае думаю суть не в этом, тем не менее без кода ТС несколько затруднительно объяснить, где у него ошибка
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.01.2013, 15:37 #6
Тут задача не в том, чтоб гистограмму посчитать, а в том, чтоб её вывести. Потому что вывод в лоб — это O(n2): найти максимум, а потом выводить по строке, пробегая каждый раз по массиву с гистограммой и проверяя больше-меньше на элементах. А ведь можно отсортировать массив, глянуть, когда там добавляются новые столбики в строках...
0
Hrobak
289 / 169 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
26.01.2013, 15:58 #7
Даже в лоб по времени должно пройти. Во первых, O(n^2) -сильно завышенная оценка, но даже и с ней в одну секунду должно влезть. Создаем вектор из 255 элементов, каждый со значением 0. Потом, когда считываем символ, инкрементируем элемент вектора с индексом кода символа. Удаляем все нулевые элементы из вектора. Ищем максимальный и, как вы говорили, пробегаем по вектору с гистограммой. Учитывая ограничения на входной файл (не более 10000 байт, то есть не более 10000 символов), такой способ здесь кажется вполне приемлемым. Тем более задачи "А" обычно не требуют особой фантазии и/или знания специфичных алгоритмов.
0
26.01.2013, 15:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2013, 15:58
Привет! Вот еще темы с ответами:

Ошибка времени выполнения. - C++
Вот код: void Add_Kod ( _kod*&amp; KodBuf, int a, char* buf, char* buf2) { if(a==1) { KodBuf = new _kod; KodBuf.ch = *(buf);...

Ошибка времени выполнения - C++
Я пишу проэкт в Visual Studia 2008 на C++. У меня есть несколько проблем. Во-первых, когда я собираю финальную версию (release) и...

оценку времени выполнения алгоритма на С++ - C++
оценить время работы алгоритма для матриц размерностей от 5 на 5 (верхний предел может быть больше), результаты измерений записать в файл ...

Подсчет времени выполнения функции - C++
Делаю 2 вида сортировки, не знаю как подсчитать их время. #include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;conio.h&gt; using namespace...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru