Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Hrobak
288 / 168 / 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.
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
26.01.2013, 14:01     Контроль времени выполнения программы #3
Цитата Сообщение от Hrobak Посмотреть сообщение
Лимит времени иногда может быть вызван использованием cin или cout в циклах; если требуется ввести/вывести более 10000 строк, то лучше использовать scanf/printf.
Пока scanf разбирает строку с форматом каждый раз, всё время кончится. А вот
C++
1
cin.sync_with_stdio(false)
может быть полезно.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.01.2013, 15:24     Контроль времени выполнения программы #4
Это олимпиадная задача. Ограничение по времени там обычно выбирается с хорошим запасом. Делается это для того, чтобы сразу отсечь решения "в лоб". Поэтому если олимпиадная задача на проверяющем сервере не укладывается по времени, то это означает только одно: ваш алгоритм гов неэффективный, придумывайте другой. Практически гарантированно дело не во вводе-выводе, не в кешах или в чём-то ещё. У себя на машине проверять таймлимит иначе, чем по бинарной шкале "ответ получен сразу" — "программа всё ещё думает", имеет смысл только в одном случае: если у вас машина, компилятор, ключи, операционка и т. д. идентичны проверяющему серверу, и при этом ваша программа не в пять раз быстрее таймлимита, а вы очень хотите втиснуться в него на последней миллисекунде.
Hrobak
288 / 168 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
26.01.2013, 15:33     Контроль времени выполнения программы #5
~OhMyGodSoLong~, достаточно часто олимпиадная задача падает по времени из-за ввода/вывода. Если вводится будет к примеру 10^10 чисел, то даже с запасом времени (20 секунд TL) при использовании cin задача упадет.
На недавнем CF раунде некоторые решения упали из-за cin/cout.
Но в конкретном случае думаю суть не в этом, тем не менее без кода ТС несколько затруднительно объяснить, где у него ошибка
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.01.2013, 15:37     Контроль времени выполнения программы #6
Тут задача не в том, чтоб гистограмму посчитать, а в том, чтоб её вывести. Потому что вывод в лоб — это O(n2): найти максимум, а потом выводить по строке, пробегая каждый раз по массиву с гистограммой и проверяя больше-меньше на элементах. А ведь можно отсортировать массив, глянуть, когда там добавляются новые столбики в строках...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2013, 15:58     Контроль времени выполнения программы
Еще ссылки по теме:

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

Оптимизация [сокращение времени выполнения] - C++
Всем привет! В общем стояла такая задача: Посчитать среднее количество букв в предложении, состоящем из символов &quot;A-Z&quot;, &quot;a-z&quot;, &quot;0-9&quot;,...

Подсчет времени выполнения процедуры - C++
Такой вопрос- необходимо получить время выполнения процедуры сортировки массива. Для этого я использовал следующее выражение void...

Уменьшение времени выполнения цикла - C++
Нужна помощь, мне надо засечь время выполнения цикла, который инициализирует элементы массива. А потом надо как-то развернуть цикл и...

Подсчет времени выполнения сортировки - C++
Подскажите, пожалуйста, как написать в программе, чтобы подсчитывало время выполнения сортировки? Там как-то надо ввести &quot;clock time&quot; ...


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

Или воспользуйтесь поиском по форуму:
Hrobak
288 / 168 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
26.01.2013, 15:58     Контроль времени выполнения программы #7
Даже в лоб по времени должно пройти. Во первых, O(n^2) -сильно завышенная оценка, но даже и с ней в одну секунду должно влезть. Создаем вектор из 255 элементов, каждый со значением 0. Потом, когда считываем символ, инкрементируем элемент вектора с индексом кода символа. Удаляем все нулевые элементы из вектора. Ищем максимальный и, как вы говорили, пробегаем по вектору с гистограммой. Учитывая ограничения на входной файл (не более 10000 байт, то есть не более 10000 символов), такой способ здесь кажется вполне приемлемым. Тем более задачи "А" обычно не требуют особой фантазии и/или знания специфичных алгоритмов.
Yandex
Объявления
26.01.2013, 15:58     Контроль времени выполнения программы
Ответ Создать тему
Опции темы

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