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

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

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

Ошибка времени выполнения C++
Измерение времени выполнения потока C++
C++ Подсчет времени выполнения сортировки
C++ Ошибка времени выполнения.
функция определения времени выполнения C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
26.01.2013, 14:01     Контроль времени выполнения программы #3
Цитата Сообщение от Hrobak Посмотреть сообщение
Лимит времени иногда может быть вызван использованием cin или cout в циклах; если требуется ввести/вывести более 10000 строк, то лучше использовать scanf/printf.
Пока scanf разбирает строку с форматом каждый раз, всё время кончится. А вот
C++
1
cin.sync_with_stdio(false)
может быть полезно.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 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
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 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++
C++ Ошибка времени выполнения (terminate)

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

Или воспользуйтесь поиском по форуму:
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     Контроль времени выполнения программы
Ответ Создать тему
Опции темы

Текущее время: 22:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru