Перейти к основному содержанию
Информатикс
Поиск по форумам
Консультации
Время работы
- ◄ Жадный калькулятор
- Не удаётся отправить ни одной посылки ►
Режим отображения
Время работы
от Полина Тяпкина — Среда, 27 Март 2013, 17:55
Количество ответов: 2
А что в протоколе значит астрономическое время работы и просто время работы?
Постоянная ссылка
В ответ на Полина Тяпкина
Re: Время работы
от Александр Агуленко — Суббота, 30 Март 2013, 10:48
Астрономическое время работы — это время, которое была запущена Ваша программа.
Обычное время работы — это сумма времени, которое Ваша программа реально работала на ядрах процессора.
Постоянная ссылка
Показать сообщение-родителя
В ответ на Александр Агуленко
Re: Время работы
от Полина Тяпкина — Воскресенье, 7 Апрель 2013, 10:57
Спасибо
Постоянная ссылка
Показать сообщение-родителя
- ◄ Жадный калькулятор
- Не удаётся отправить ни одной посылки ►
◄ Электронная библиотека
Перейти на…
Как работать на сайте ►
Блог пользователя ioanisyan
Как измерить время выполнения программы в миллисекундах ?
|
11 лет назад,
Например, так:
Выведет время программы в секундах, с дробной частью. Обычно CLOCKS_PER_SEC=1000, поэтому можно и в целых числах. |
-
11 лет назад,
#
^
|
+8
Не очень точно, потому что clock() возвращает астрономическое время. При тестировании используется процессорное, а его изнутри программы я не знаю, как считать.
-
11 лет назад,
#
^
|
0
Да, конечно. Я не думаю, что надо точно. Ну, под виндой можно сделать GetCurrentProcess() и вперёд с песней.
-
11 лет назад,
#
^
|
+8
под линухой можно запускать через time
-
-
11 лет назад,
#
^
|
←
Rev. 6
→
+5
А разве clock() везде возвращает астрономическое время?
В linux, например, $man 3p clock говорит:
NAME clock - report CPU time used SYNOPSIS #include <time.h> clock_t clock(void); DESCRIPTION The clock() function shall return the implementation''s best approximation to the processor time used by the process since the beginning of an implementation-defined era related only to the process invocation.
-
-
11 лет назад,
#
^
|
←
Rev. 11
→
+8
Я не понял последнего утверждения. Как связаны целые числа и то, чему равно CLOCKS_PER_SEC?
Да и вообще говоря:
> man 3 clock
…
CONFORMING TO
C89, C99, POSIX.1-2001. POSIX requires that CLOCKS_PER_SEC equals
1000000 independent of the actual resolution.offtop: пока отформатировал этот несчастный вывод чуть не помер. Что я делаю не так? В пяти тильдах не форматируется, пришлось руками, через html-код всё выравнивать. …
-
11 лет назад,
#
^
|
0
Просили время в миллисекундах. Чтобы не домножать дабл на 1000 и творить чудеса, можно сделать всё в целых.
man/POSIX под Windows? Не, не слышал В MinGW 4.6.1 равен 1000.
-
11 лет назад,
#
^
|
0
Похоже я невнимательно читаю: где-то пропустил, что речь о windows-specific ситуации?
-
-
11 лет назад,
#
^
|
+27
Мне есть, чему у вас поучиться, Холмс!
-
-
11 лет назад,
#
^
|
+8
ну в таком случае и о С++ никто ничего не говорил:))
-
-
-
-
11 лет назад,
#
^
|
0
Спасибо, но при одинаковых тестов времена выполнениев отличаются, чего посоветуете ?
-
11 лет назад,
#
^
|
0
как раз речь о том, что использовать астрономическое время не совсем точно, оно сильно зависит от текущей загрузки системы. Процессорное — не зависит от того, что вы еще параллельно делаете
|
11 лет назад,
Под Windows можно использовать либо runexe (написано нами — Саратовским ГУ), либо run.exe (авторства ИТМО). Я рекомендую наш вариант он не запускает код в дебаге, а иногда запуск в debug приводит к очень странным (читай неправльным( измерениям. |
-
11 лет назад,
#
^
|
0
Ага, иногда на порядок-другой время работы изменяется. А не знаете, зачем запускать в debug?
-
11 лет назад,
#
^
|
0
Так они ловят некоторые events — типа, что программа создала другой процесс и видимо кое-что еще.
-
11 лет назад,
#
^
|
0
Кажется это чаще всего происходит при работе с динамическими структурами или большой рекурсией.
-
11 лет назад,
#
^
|
0
Кажется, утверждается, что под debug медленно работает delete. То есть если совсем много удаляется, то run.exe замедляет выполнение очень сильно. Кстати, интересно как они с этим борются на официальных соревнованиях. Представители ИТМО есть? Расскажете?
-
11 лет назад,
#
^
|
0
Вроде есть какой-то хитрый ключ в реестре
-
11 лет назад,
#
^
|
0
Интересно какой именно. Кстати, полезно-же опубликовать — иначе зачем run.exe вообще нужен? Ведь его важная задача определять время работы для околоолимпиадных целей, а там такие программы, где он будет лажать не редкость. Даже пользоваться как-то страшно. Или вот люди PCMS2 ставят, они это настраивают?
-
11 лет назад,
#
^
|
+19
Нужно прописать такой ключ
HKEY_LOCAL_MACHINESOFTWAREMicrosoftWindows NTCurrentVersionImage File Execution Optionsyour_exe_name.exe
-
11 лет назад,
#
^
|
0
Спасибо. Правильно я понимаю, что такое предполагается прописывать для каждого exe (напр., java, все интерпретаторы), а компилируемые переименовывать в какое-то хардкодное имя? your_exe_name.exe — это только имя файла, без пути? (например,
main.exe
).-
11 лет назад,
#
^
|
0
Да, именно так. Ну либо написать обертку, которая добавит в реестр ключ для запускаемого файла, запустит, а потом ключ удалит (можно даже на cmd, при помощи reg add и reg delete)
-
-
-
-
-
-
-
-
-
11 лет назад,
#
^
|
+7
runexe -h
, но если просто хотите измерить время, тоrunexe solution.exe
. Можноrunexe -i input.txt -o output.txt solution.exe
если хотите перенаправлять ввод/вывод на стандартный из файлов. Еще вариантrunexe -t 2s -i input.txt -o output.txt solution.exe
— это с ограничением по времени.-
11 лет назад,
#
^
|
+4
Для Farа очень удобно поставить ассоциацию с типом файлов *.exe и по нажатию например на F4, чтобы запускался runexe. Всегда так делаю))
-
11 лет назад,
#
^
|
0
Я как-то раз пробовал запускать runexe с указанием логина и пароля юзера, под правами которого я хотел чтоб программа запустилась. Но у меня это так и не получилось. Там видимо надо какие-то специальные привилегии настраивать?
Тот же вопрос относится и к run.exe от ИТМО…
-
11 лет назад,
#
^
|
+12
Для run.exe надо так — допустим, мы работаем под аккаунтом Jury и хотим запустить под аккаунтом invoker. Тогда Jury навешиваем привилегии «Increase quotas» (SeIncreaseQuota) и «Replace a process level token» (SeAssignPrimaryToken), а invoker — «Log on as batch job» в Administrative Tools — Local Security Settings — Local Policies — User Right Assignment. У меня вдобавок Jury имеет администраторские права, что небезопасно, но отнимать не пробовал; надо попытаться
-
-
-
-
11 лет назад,
#
^
|
0
Кстати, правильно ли я понимаю, что исходники файла /src/runlib/runlib32-static.lib закрыты? Если да, то можно ли узнать, в каких случаях выдаётся ошибка SECURITY_VIOLATION (т.е., за чем следит runexe)? Потому что, например, за работой с ФС вроде из общедоступных запускальщиков под Windows никто не следит.
-
11 лет назад,
#
^
|
+8
Проект открыт — первая ссылка в Google.
Однако там почти нет этого кода, для этого используются другие технологии: они местами точные, местами эвристические, поэтому мы их не публикуем.
-
-
5 лет назад,
#
^
|
+9
А планируется ли переезд runexe с закрытого хостинга на, скажем, GitHub?
|
11 лет назад,
Есть еще такая вещь, как QueryPerformanceCounter (вкупе с QueryPerformanceFrequency). Измеряет кол-во «тиков» процессора с момента запуска системы, поэтому выходит довольно точно. Не знаю, как в других средах, но как-то пробовал измерять время работы кода на Delphi, проблема была только одна — погрешность +/-0.5 ms (ибо на машине работают еще и другие программы, которые отнимают время). Ну, если совсем точно надо — можно посчитать раз 20 и найти среднее :)) |
|
11 лет назад,
ptime — меряет хорошо. Можно скопировать в папку с прогой, время работы которой хочется измерить. Перенаправление ввода-вывода и вызов программы (предварительно перейдя в папку с ней): ptime program < input.txt > output.txt. Без перенаправления так: ptime program. Из замеченных глюков — иногда файлы долго открываются (не у всех, в частности наблюдаю у себя на винде, но это сбои ФС), и порой 500 мс можно легко скинуть (это уже экспериментировать со своей системой надо). Но на большинстве машин такого не наблюдается, и время показывается «нормальное». |
|
11 лет назад,
Подскажите, как при помощи run.exe запретить создание дочерних процессов? Например, вот такой код
успешно выполняется. Время будет считаться до тех пор, пока блокнот не будет закрыт вручную. После этого, вердикт будет Idleness limit exceeded. Но хотелось бы, чтобы дочерние процессы убивались автоматически. |
Опрос показаний часов процессорного времени
Базовым средством для работы с часами процессорного времени является функция clock() (см. листинг 12.15). Она возвращает в качестве результата процессорное время, затраченное процессом с некоего момента, зависящего от реализации и связанного только с его (процесса) запуском. В случае ошибки результат равен ( clock_t ) (-1).
#include <time.h> clock_t clock (void);
Листинг
12.15.
Описание функции clock().
Чтобы перевести время, возвращаемое функцией clock(), в секунды, его следует поделить на константу CLOCKS_PER_SEC, которая определена в заголовочном файле <time.h> равной одному миллиону, хотя разрешающая способность часов процессорного времени в конкретной реализации может и отличаться от микросекунды.
Отметим, что если значения типа clock_t представлены как 32-разрядные целые со знаком, то менее чем через 36 минут ( процессорного времени ) наступит переполнение.
В листинге 12.16 показан пример использования функции clock(). Поскольку начало отсчета для часов процессорного времени не специфицировано, их показания опрашиваются в начале и конце измеряемого промежутка, а результатом измерения затраченного процессорного времени служит разность этих показаний.
#include <stdio.h> #include <time.h> int main (void) { time_t st; clock_t ct; double s = 0; double d = 1; int i; fprintf (stderr, "Начало выполнения циклаn"); (void) time (&st); ct = clock; for (i = 1; i <= 100000000; i++) { s += d / i; d = -d; } fprintf (stderr, "Процессорное время выполнения цикла: %g сек.n", (double) (clock - ct) / CLOCKS_PER_SEC); fprintf (stderr, "Астрономическое время выполнения цикла: %g сек.n", difftime (time (NULL), st)); return (0); }
Листинг
12.16.
Пример программы, использующей функции опроса показаний часов реального и процессорного времени.
Возможные результаты работы этой программы показаны в листинге 12.17. Процессорное время получилось больше астрономического из-за ошибок округления.
Начало выполнения цикла Процессорное время выполнения цикла: 15.19 сек. Астрономическое время выполнения цикла: 15 сек.
Листинг
12.17.
Возможные результаты работы программы, использующей функции опроса показаний часов реального и процессорного времени.
Для измерения времени выполнения простой команды можно воспользоваться служебной программой time (не входящей, правда, в обязательную часть стандарта POSIX-2001 ):
time [-p] команда [аргумент ...]
Она выдает в стандартный протокол астрономическое и процессорное время, прошедшее от запуска до завершения команды с указанными аргументами. Если задана опция -p, время выдается в секундах в виде вещественных чисел. Процессорное время подразделяется на пользовательское (затраченное самой командой) и системное (ушедшее на оказание системных услуг команде). Если предположить, что выполнимый файл приведенной выше программы называется my_tcex, то командная строка
выдаст в стандартный протокол примерно следующее (см. листинг 12.18):
Начало выполнения цикла Процессорное время выполнения цикла: 15.2 сек. Астрономическое время выполнения цикла: 15 сек. real 15.20 user 15.20 sys 0.00
Листинг
12.18.
Возможные результаты измерения времени работы программы, использующей функции опроса показаний часов реального и процессорного времени.
Если нужно измерить время выполнения конвейера или списка команд, их можно поместить в файл, превратив тем самым в простую команду, или воспользоваться конструкцией вида
time sh -c 'составная команда'
Оружием более крупного калибра является специальная встроенная в shell команда
Она выдает на стандартный вывод процессорное время, затраченное командным интерпретатором и порожденными им процессами. Например, после выполнения команд
my_tcex & my_tcex times на стандартный вывод может быть выдано: 0m0.010s 0m0.000s 0m30.410s 0m0.000s
Можно видеть, что сам командный интерпретатор практически не занимал процессор, а два порожденных им процесса в сумме потребили чуть меньше тридцати с половиной секунд ; время системных услуг в обоих случаях оказалось пренебрежимо малым.
Реализация описанных выше утилит time и times опирается на функцию times() (см. листинг 12.19). Она опрашивает данные о времени выполнения вызывающего процесса и порожденных процессов, завершение которых ожидалось с помощью функций wait() или waitpid(). В отличие от clock(), функция times() измеряет время в тактах часов, и переполнение 32-разрядного представления значений типа clock_t происходит не через полчаса, а примерно в течение года (если секунда делится на 60 — 100 тактов). Соответственно, для перевода результатов работы times() в секунды их нужно делить на sysconf ( _SC_CLK_TCK ), а не на CLOCKS_PER_SEC.
#include <sys/times.h> clock_t times (struct tms *buffer);
Листинг
12.19.
Описание функции times().
В качестве результата функция times() возвращает астрономическое время, прошедшее от некоторого момента в прошлом (например, от загрузки системы), но основные, содержательные данные, относящиеся к вызывающему процессу и его потомкам, помещаются в структуру типа tms, которая описана в заголовочном файле <sys/times.h> и, согласно стандарту POSIX-2001, должна содержать по крайней мере следующие поля:
clock_t tms_utime; /* Процессорное время, затраченное */ /* вызывающим процессом */ clock_t tms_stime; /* Процессорное время, затраченное системой */ /* на обслуживание вызывающего процесса */ clock_t tms_cutime; /* Процессорное время, затраченное /*завершившимися порожденными процессами */ clock_t tms_cstime; /* Процессорное время, затраченное системой */ /* на обслуживание завершившихся */ /* порожденных процессов */
Значения времени завершившихся порожденных процессов ( tms_utime и tms_cutime, а также tms_stime и tms_cstime ) добавляются, соответственно, к элементам tms_cutime и tms_cstime структуры родительского процесса при возврате из функций wait() или waitpid(). Это происходит рекурсивно: если порожденный процесс ожидал завершения своих потомков, то в упомянутых элементах структуры накопятся данные о времени выполнения поддерева процессов.
В качестве примера использования функции times() измерим время работы рассматривавшейся ранее программы, копирующей строки со стандартного ввода на стандартный вывод через сокеты адресного семейства AF_UNIX с помощью порожденного процесса (см. листинг 12.20).
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Программа копирует строки со стандартного ввода на стандартный вывод, */ /* "прокачивая" их через пару сокетов. */ /* Используются функции ввода/вывода нижнего уровня. */ /* Измеряется астрономическое и процессорное время */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #include <unistd.h> #include <stdlib.h> #include <stdio.h> #include <sys/socket.h> #include <sys/wait.h> #include <sys/times.h> #define MY_PROMPT "Вводите строкиn" #define MY_MSG "Вы ввели: " int main (void) { int sds [2]; char buf [1]; int new_line = 1; /* Признак того, что надо выдать сообщение MY_MSG */ /* перед отображением очередной строки */ clock_t st_ct; /* Данные об астрономическом и процессорном времени */ struct tms st_cpt; /* в начале работы программы */ clock_t en_ct; /* Данные об астрономическом и процессорном времени */ struct tms en_cpt; /* в конце работы программы */ long tck_p_sec; /* Количество тактов часов в секунде */ /* Опросим данные о времени начала выполнения */ if ((st_ct = times (&st_cpt)) == (clock_t) (-1)) { perror ("TIMES-1"); return (1); } /* Создадим пару соединенных безымянных сокетов */ if (socketpair (AF_UNIX, SOCK_STREAM, 0, sds) < 0) { perror ("SOCKETPAIR"); return (2); } switch (fork ()) { case -1: perror ("FORK"); return (3); case 0: /* Чтение из сокета sds [0] и выдачу на стандартный вывод */ /* реализуем в порожденном процессе */ while (read (sds [0], buf, 1) == 1) { if (write (STDOUT_FILENO, buf, 1) != 1) { perror ("WRITE TO STDOUT"); break; } } exit (0); } /* Чтение со стандартного ввода и запись в сокет sds [1] */ /* возложим на родительский процесс */ if (write (sds [1], MY_PROMPT, sizeof (MY_PROMPT) - 1) != sizeof (MY_PROMPT) - 1) { perror ("WRITE TO SOCKET-1"); } while (read (STDIN_FILENO, buf, 1) == 1) { /* Перед отображением очередной строки */ /* нужно выдать сообщение MY_MSG */ if (new_line) { if (write (sds [1], MY_MSG, sizeof (MY_MSG) - 1) != sizeof (MY_MSG) - 1) { perror ("WRITE TO SOCKET-2"); break; } } if (write (sds [1], buf, 1) != 1) { perror ("WRITE TO SOCKET-3"); break; } new_line = (buf [0] == 'n'); } shutdown (sds [1], SHUT_WR); (void) wait (NULL); /* Опросим данные о времени конца выполнения, */ /* вычислим и выдадим результаты измерений */ if ((en_ct = times (&en_cpt)) == (clock_t) (-1)) { perror ("TIMES-2"); return (4); } tck_p_sec = sysconf (_SC_CLK_TCK); fprintf (stderr, "Тактов в секунде: %ldn", tck_p_sec); fprintf (stderr, "Астрономическое время работы программы: %g сек.n", (double) (en_ct - st_ct) / tck_p_sec); fprintf (stderr, "Процессорное время, затраченное процессом: %g сек.n", (double) (en_cpt.tms_utime - st_cpt.tms_utime) / tck_p_sec); fprintf (stderr, "Процессорное время, затраченное системой: %g сек.n", (double) (en_cpt.tms_stime - st_cpt.tms_stime) / tck_p_sec); fprintf (stderr, "Аналогичные данные для порожденных процессов:n"); fprintf (stderr, "%g сек.n%g сек.n", (double) (en_cpt.tms_cutime - st_cpt.tms_cutime) / tck_p_sec, (double) (en_cpt.tms_cstime - st_cpt.tms_cstime) / tck_p_sec); return (0); }
Листинг
12.20.
Пример программы, использующей функцию times().
Если перенаправить стандартный ввод в какой-либо текстовый файл заметных размеров, а стандартный вывод — в другой файл, можно получить результаты, подобные тем, что показаны в листинге 12.21.
Тактов в секунде: 100 Астрономическое время работы программы: 1.19 сек. Процессорное время, затраченное процессом: 0.02 сек. Процессорное время, затраченное системой: 0.08 сек. Аналогичные данные для порожденных процессов: 0.09 сек. 1 сек.
Листинг
12.21.
Возможные результаты работы программы, использующей функцию times().
Прямое манипулирование часами процессорного времени возможно после обращения к функции clock_getcpuclockid() (см. листинг 12.22), позволяющей выяснить их идентификатор. Оговоримся, однако, что эта функция не входит в обязательную часть стандарта POSIX-2001 (она относится к продвинутым средствам реального времени).
#include <time.h> int clock_getcpuclockid (pid_t pid, clockid_t *clock_id);
Листинг
12.22.
Описание функции clock_getcpuclockid().
Идентификатор часов процессорного времени, обслуживающих заданный аргументом pid процесс, возвращается по адресу, специфицированному аргументом clock_id. Если значение pid равно нулю, имеется в виду вызывающий процесс. Признаком успешного завершения является нулевой результат; в противном случае возвращается код ошибки.
В листинге 12.23 показан пример употребления функции clock_getcpuclockid() и манипулирования часами процессорного времени. Возможные результаты выполнения этой программы — в листинге 12.24.
#include <stdio.h> #include <time.h> #include <sys/types.h> #include <errno.h> int main (void) { clockid_t clk_id; /* Идентификатор часов процессорного времени */ struct timespec tmsp; double s = 0; double d = 1; int i; if ((errno = clock_getcpuclockid ((pid_t) 0, &clk_id)) != 0) { perror ("CLOCK_GETCPUCLOCKID"); return (1); } if (clock_getres (clk_id, &tmsp) == -1) { perror ("CLOCK_GETRES"); return (2); } printf ("Разрешающая способность часов процессорного времени: %ld нсек.n", tmsp.tv_nsec); /* Измерим процессорное время выполнения цикла. */ fprintf (stderr, "Начало выполнения циклаn"); tmsp.tv_sec = tmsp.tv_nsec = 0; if (clock_settime (clk_id, &tmsp) == -1) { perror ("CLOCK_SETTIME"); return (3); } for (i = 1; i <= 100000000; i++) { s += d / i; d = -d; } if (clock_gettime (clk_id, &tmsp) == -1) { perror ("CLOCK_GETTIME"); return (4); } fprintf (stderr, "Процессорное время выполнения цикла: %ld сек. %ld нсек.n", tmsp.tv_sec, tmsp.tv_nsec); return (0); }
Листинг
12.23.
Пример программы, манипулирующей часами процессорного времени.
Разрешающая способность часов процессорного времени: 2 нсек. Начало выполнения цикла Процессорное время выполнения цикла: 15 сек. 350313054 нсек.
Листинг
12.24.
Возможные результаты работы программы, манипулирующей часами процессорного времени.
Обратим внимание на два момента. Перед началом измеряемого участка программы на часах процессорного времени были установлены нулевые показания, что, разумеется, не влияет на приоритет процесса и его планирование. Конечно, можно было обойтись без переустановки, запомнив показания часов в начале и конце измеряемого промежутка и произведя затем их вычитание, но технически это чуть сложнее; кроме того, нам хотелось применить функцию clock_settime(). Второй заслуживающий отдельного упоминания момент состоит в отсутствии необходимости выяснять идентификатор часов процессорного времени вызывающего процесса с помощью функции clock_getcpuclockid(): можно воспользоваться именованной константой CLOCK_PROCESS_CPUTIME_ID.
TheMrKn1Fe 0 / 0 / 0 Регистрация: 01.10.2018 Сообщений: 4 |
||||
1 |
||||
Программа не проходит по времени01.10.2018, 03:52. Показов 4198. Ответов 8 Метки нет (Все метки)
http://codeforces.com/problemset/problem/591/B — сама задача
Моя программа проходит 12 из 25 тестов, в остальных превышено время: Прошу помогите ускорить программу, либо укажите на исключения которые замедляют ее работу!
0 |
Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782 |
01.10.2018, 03:52 |
Ответы с готовыми решениями: Программа не проходит тесты по времени, посоветуйте как исправить Задача не проходит по времени И мое решения: Не проходит тесты по времени Оптимизация, алгоритм не проходит по времени 8 |
__ALPHA__ 298 / 156 / 87 Регистрация: 16.04.2018 Сообщений: 239 |
||||
01.10.2018, 09:32 |
2 |
|||
Попробуй это:
1 |
0 / 0 / 0 Регистрация: 01.10.2018 Сообщений: 4 |
|
01.10.2018, 14:43 [ТС] |
3 |
Ваше решение помогло, но только частично, теперь проходит 17 из 25 Тест Статус Балл Время работы Астрономическое время работы Используемая память
0 |
Semen-Semenich 4143 / 3067 / 1092 Регистрация: 21.03.2016 Сообщений: 7,721 |
||||
01.10.2018, 18:01 |
4 |
|||
из условия ‘В первой строке входных данных находятся два числа n и m’ а раз даны два значения значить задача предусматривает их использование в решении
0 |
0 / 0 / 0 Регистрация: 01.10.2018 Сообщений: 4 |
|
01.10.2018, 18:38 [ТС] |
5 |
Не знаю зачем дано первое число, но его использование никак не помогает
0 |
Black Fregat Фрилансер 3703 / 2075 / 567 Регистрация: 31.05.2009 Сообщений: 6,683 |
||||
01.10.2018, 21:40 |
6 |
|||
Сообщение было отмечено TheMrKn1Fe как решение Решение
0 |
0 / 0 / 0 Регистрация: 01.10.2018 Сообщений: 4 |
|
01.10.2018, 22:49 [ТС] |
7 |
Спасибо большое! Программа прошла все тесты
0 |
Garry Galler 5403 / 3827 / 1214 Регистрация: 28.10.2013 Сообщений: 9,554 Записей в блоге: 1 |
||||
01.10.2018, 23:47 |
8 |
|||
Немного быстрее — ~10% — работает translate:
0 |
Фрилансер 3703 / 2075 / 567 Регистрация: 31.05.2009 Сообщений: 6,683 |
|
02.10.2018, 01:03 |
9 |
Garry Galler, там по условию до 200 000 правил и до 200 000 символов в строке.
0 |
Длительность можно задавать не только в рабочих, но и в астрономических единицах. В этом случае график выполнения задачи не будет прерываться на выходные дни и праздники, задача будет выполняться и в нерабочее время тоже. Никакие изменения календарей такой задачи касаться не будут.
Злоупотреблять такими оценками не стоит, они уместны только если обусловлены технологическими особенностями задачи.
Для оценки длительности в астрономических единицах достаточно приписать перед буквенным обозначением единицы букву А (в русской версии программы) или E (в английской).
Например:
1ад – одни сутки
5ад – 5 суток
1 ан – ровно 7 суток
1амес – ровно 30 суток
C/C++: как измерять процессорное время +26
Программирование, C++, C
Рекомендация: подборка платных и бесплатных курсов Java — https://katalog-kursov.ru/
КДПВ
От переводчика:
Большинство моих знакомых для измерения времени в разного вида бенчмарках в С++ используют chrono
или, в особо запущенных случаях, ctime
. Но для бенчмаркинга гораздо полезнее замерять процессорное время. Недавно я наткнулся на статью о кроссплатформенном замере процессорного времени и решил поделиться ею тут, возможно несколько увеличив качество местных бенчмарков.
P.S. Когда в статье написано «сегодня» или «сейчас», имеется ввиду «на момент выхода статьи», то есть, если я не ошибаюсь, март 2012. Ни я, ни автор не гарантируем, что это до сих пор так.
P.P.S. На момент публикации оригинал недоступен, но хранится в кэше Яндекса
Функции API, позволяющие получить процессорное время, использованное процессом, отличаются в разных операционных системах: Windows, Linux, OSX, BSD, Solaris, а также прочих UNIX-подобных ОС. Эта статья предоставляет кросс-платформенную функцию, получающую процессорное время процесса и объясняет, какие функции поддерживает каждая ОС.
Как получить процессорное время
Процессорное время увеличивается, когда процесс работает и потребляет циклы CPU. Во время операций ввода-вывода, блокировок потоков и других операций, которые приостанавливают работу процессора, процессорное время не увеличивается пока процесс снова не начнет использовать CPU.
Разные инструменты, такие как ps
в POSIX, Activity Monitor в OSX и Task Manager в Windows показывают процессорное время, используемое процессами, но часто бывает полезным отслеживать его прямо из самого процесса. Это особенно полезно во время бенчмаркинга алгоритмов или маленькой части сложной программы. Несмотря на то, что все ОС предоставляют API для получения процессорного времени, в каждой из них есть свои тонкости.
Код
Функция getCPUTime( )
, представленная ниже, работает на большинстве ОС (просто скопируйте код или скачайте файл getCPUTime.c). Там, где это нужно, слинкуйтесь с librt, чтобы получить POSIX-таймеры (например, AIX, BSD, Cygwin, HP-UX, Linux и Solaris, но не OSX). В противном случае, достаточно стандартных библиотек.
Далее мы подробно обсудим все функции, тонкости и причины, по которым в коде столько #ifdef
‘ов.
getCPUTime.c
/*
* Author: David Robert Nadeau
* Site: http://NadeauSoftware.com/
* License: Creative Commons Attribution 3.0 Unported License
* http://creativecommons.org/licenses/by/3.0/deed.en_US
*/
#if defined(_WIN32)
#include <Windows.h>
#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
#include <unistd.h>
#include <sys/resource.h>
#include <sys/times.h>
#include <time.h>
#else
#error "Unable to define getCPUTime( ) for an unknown OS."
#endif
/**
* Returns the amount of CPU time used by the current process,
* in seconds, or -1.0 if an error occurred.
*/
double getCPUTime( )
{
#if defined(_WIN32)
/* Windows -------------------------------------------------- */
FILETIME createTime;
FILETIME exitTime;
FILETIME kernelTime;
FILETIME userTime;
if ( GetProcessTimes( GetCurrentProcess( ),
&createTime, &exitTime, &kernelTime, &userTime ) != -1 )
{
SYSTEMTIME userSystemTime;
if ( FileTimeToSystemTime( &userTime, &userSystemTime ) != -1 )
return (double)userSystemTime.wHour * 3600.0 +
(double)userSystemTime.wMinute * 60.0 +
(double)userSystemTime.wSecond +
(double)userSystemTime.wMilliseconds / 1000.0;
}
#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
/* AIX, BSD, Cygwin, HP-UX, Linux, OSX, and Solaris --------- */
#if defined(_POSIX_TIMERS) && (_POSIX_TIMERS > 0)
/* Prefer high-res POSIX timers, when available. */
{
clockid_t id;
struct timespec ts;
#if _POSIX_CPUTIME > 0
/* Clock ids vary by OS. Query the id, if possible. */
if ( clock_getcpuclockid( 0, &id ) == -1 )
#endif
#if defined(CLOCK_PROCESS_CPUTIME_ID)
/* Use known clock id for AIX, Linux, or Solaris. */
id = CLOCK_PROCESS_CPUTIME_ID;
#elif defined(CLOCK_VIRTUAL)
/* Use known clock id for BSD or HP-UX. */
id = CLOCK_VIRTUAL;
#else
id = (clockid_t)-1;
#endif
if ( id != (clockid_t)-1 && clock_gettime( id, &ts ) != -1 )
return (double)ts.tv_sec +
(double)ts.tv_nsec / 1000000000.0;
}
#endif
#if defined(RUSAGE_SELF)
{
struct rusage rusage;
if ( getrusage( RUSAGE_SELF, &rusage ) != -1 )
return (double)rusage.ru_utime.tv_sec +
(double)rusage.ru_utime.tv_usec / 1000000.0;
}
#endif
#if defined(_SC_CLK_TCK)
{
const double ticks = (double)sysconf( _SC_CLK_TCK );
struct tms tms;
if ( times( &tms ) != (clock_t)-1 )
return (double)tms.tms_utime / ticks;
}
#endif
#if defined(CLOCKS_PER_SEC)
{
clock_t cl = clock( );
if ( cl != (clock_t)-1 )
return (double)cl / (double)CLOCKS_PER_SEC;
}
#endif
#endif
return -1; /* Failed. */
}
Использование
Чтобы замерить процессорное время алгоритма, вызовите getCPUTime( )
до и после запуска алгоритма, и выведите разницу. Не стоит предполагать, что значение, возвращенное при единичном вызове функции, несет какой-то смысл.
double startTime, endTime;
startTime = getCPUTime( );
...
endTime = getCPUTime( );
fprintf( stderr, "CPU time used = %lfn", (endTime - startTime) );
Обсуждение
Каждая ОС предоставляет один или несколько способов получить процессорное время. Однако некоторые способы точнее остальных.
OS | clock | clock_gettime | GetProcessTimes | getrusage | times |
---|---|---|---|---|---|
AIX | yes | yes | yes | yes | |
BSD | yes | yes | yes | yes | |
HP-UX | yes | yes | yes | yes | |
Linux | yes | yes | yes | yes | |
OSX | yes | yes | yes | ||
Solaris | yes | yes | yes | yes | |
Windows | yes |
Каждый из этих способов подробно освещен ниже.
GetProcessTimes( )
На Windows и Cygwin (UNIX-подобная среда и интерфейс командной строки для Windows), функция GetProcessTimes( ) заполняет структуру FILETIME процессорным временем, использованным процессом, а функция FileTimeToSystemTime( ) конвертирует структуру FILETIME в структуру SYSTEMTIME, содержащую пригодное для использования значение времени.
typedef struct _SYSTEMTIME
{
WORD wYear;
WORD wMonth;
WORD wDayOfWeek;
WORD wDay;
WORD wHour;
WORD wMinute;
WORD wSecond;
WORD wMilliseconds;
} SYSTEMTIME, *PSYSTEMTIME;
Доступность GetProcessTimes( ): Cygwin, Windows XP и более поздние версии.
Получение процессорного времени:
#include <Windows.h>
...
FILETIME createTime;
FILETIME exitTime;
FILETIME kernelTime;
FILETIME userTime;
if ( GetProcessTimes( GetCurrentProcess( ),
&createTime, &exitTime, &kernelTime, &userTime ) != -1 )
{
SYSTEMTIME userSystemTime;
if ( FileTimeToSystemTime( &userTime, &userSystemTime ) != -1 )
return (double)userSystemTime.wHour * 3600.0 +
(double)userSystemTime.wMinute * 60.0 +
(double)userSystemTime.wSecond +
(double)userSystemTime.wMilliseconds / 1000.0;
}
clock_gettme( )
На большинстве POSIX-совместимых ОС, clock_gettime( )
(смотри мануалы к AIX, BSD, HP-UX, Linux и Solaris) предоставляет самое точное значение процессорного времени. Первый аргумент функции выбирает «clock id», а второй это структура timespec
, заполняемая использованным процессорным временем в секундах и наносекундах. Для большинства ОС, программа должна быть слинкована с librt.
Однако, есть несколько тонкостей, затрудняющих использование этой функции в кросс-платформенном коде:
- Функция является опциональной частью стандарта POSIX и доступна только если
_POSIX_TIMERS
определен в<unistd.h>
значением больше 0. На сегодняшний день, AIX, BSD, HP-UX, Linux и Solaris поддерживают эту функцию, но OSX не поддерживает. - Структура
timespec
, заполняемая функциейclock_gettime( )
может хранить время в наносекундах, но точность часов отличается в разных ОС и на разных системах. Функция clock_getres( ) возвращает точность часов, если она вам нужна. Эта функция, опять-таки, является опциональной частью стандарта POSIX, доступной только если_POSIX_TIMERS
больше нуля. На данный момент, AIX, BSD, HP-UX, Linux и Solaris предоставляют эту функцию, но в Solaris она не работает. - стандарт POSIX определяет имена нескольких стандартных значений «clock id», включая
CLOCK_PROCESS_CPUTIME_ID
, чтобы получить процессорное время процесса. Тем не менее, сегодня BSD и HP-UX не имеют этого id, и взамен определяют собственный idCLOCK_VIRTUAL
для процессорного времени. Чтобы запутать все ещё больше, Solaris определяет оба этих, но используетCLOCK_VIRTUAL
для процессорного времени потока, а не процесса.
ОС | Какой id использовать |
---|---|
AIX | CLOCK_PROCESS_CPUTIME_ID |
BSD | CLOCK_VIRTUAL |
HP-UX | CLOCK_VIRTUAL |
Linux | CLOCK_PROCESS_CPUTIME_ID |
Solaris | CLOCK_PROCESS_CPUTIME_ID |
- Вместо того, чтобы использовать одну из констант, объявленных выше, функция clock_getcpuclockid( ) возвращает таймер для выбранного процесса. Использование процесса 0 позволяет получить процессорное время текущего процесса. Однако, это ещё одна опциональная часть стандарта POSIX и доступна только если
_POSIX_CPUTIME
больше 0. На сегодняшний день, только AIX и Linux предоставляют эту функцию, но линуксовские include-файлы не определяют_POSIX_CPUTIME
и функция возвращает ненадёжные и несовместимые с POSIX результаты. - Функция
clock_gettime( )
может быть реализована с помощью регистра времени процессора. На многопроцессорных системах, у отдельных процессоров может быть несколько разное восприятие времени, из-за чего функция может возвращать неверные значения, если процесс передавался от процессора процессору. На Linux, и только на Linux, это может быть обнаружено, еслиclock_getcpuclockid( )
возвращает не-POSIX ошибку и устанавливаетerrno
вENOENT
. Однако, как замечено выше, на Linuxclock_getcpuclockid( )
ненадежен.
На практике из-за всех этих тонкостей, использование clock_gettime( )
требует много проверок с помощью #ifdef
и возможность переключиться на другую функцию, если она не срабатывает.
Доступность clock_gettime( ): AIX, BSD, Cygwin, HP-UX, Linux и Solaris. Но clock id на BSD и HP-UX нестандартные.
Доступность clock_getres( ): AIX, BSD, Cygwin, HP-UX и Linux, но не работает Solaris.
Доступность clock_getcpuclockid( ): AIX и Cygwin, не недостоверна на Linux.
Получение процессорного времени:
#include <unistd.h>
#include <time.h>
...
#if defined(_POSIX_TIMERS) && (_POSIX_TIMERS > 0)
clockid_t id;
struct timespec ts;
#if _POSIX_CPUTIME > 0
/* Clock ids vary by OS. Query the id, if possible. */
if ( clock_getcpuclockid( 0, &id ) == -1 )
#endif
#if defined(CLOCK_PROCESS_CPUTIME_ID)
/* Use known clock id for AIX, Linux, or Solaris. */
id = CLOCK_PROCESS_CPUTIME_ID;
#elif defined(CLOCK_VIRTUAL)
/* Use known clock id for BSD or HP-UX. */
id = CLOCK_VIRTUAL;
#else
id = (clockid_t)-1;
#endif
if ( id != (clockid_t)-1 && clock_gettime( id, &ts ) != -1 )
return (double)ts.tv_sec +
(double)ts.tv_nsec / 1000000000.0;
#endif
getrusage( )
На всех UNIX-подобных ОС, функция getrusage( ) это самый надежный способ получить процессорное время, использованное текущим процессом. Функция заполняет структуру rusage временем в секундах и микросекундах. Поле ru_utime
содержит время проведенное в user mode, а поле ru_stime
— в system mode от имени процесса.
Внимание: Некоторые ОС, до широкого распространения поддержки 64-бит, определяли функцию getrusage( )
, возвращающую 32-битное значение, и функцию getrusage64( )
, возвращающую 64-битное значение. Сегодня, getrusage( )
возвращает 64-битное значение, аgetrusage64( )
устарело.
Доступность getrusage( ): AIX, BSD, Cygwin, HP-UX, Linux, OSX, and Solaris.
Получение процессорного времени:
#include <sys/resource.h>
#include <sys/times.h>
...
struct rusage rusage;
if ( getrusage( RUSAGE_SELF, &rusage ) != -1 )
return (double)rusage.ru_utime.tv_sec +
(double)rusage.ru_utime.tv_usec / 1000000.0;
times( )
На всех UNIX-подобных ОС, устаревшая функция times( ) заполняет структуру tms
с процессорным временем в тиках, а функция sysconf( ) возвращает количество тиков в секунду. Поле tms_utime
содержит время, проведенное в user mode, а поле tms_stime
— в system mode от имени процесса.
Внимание: Более старый аргумент функции sysconf( )
CLK_TCK
устарел и может не поддерживаться в некоторых ОС. Если он доступен, функция sysconf( )
обычно не работает при его использовании. Используйте _SC_CLK_TCK
вместо него.
Доступность times( ): AIX, BSD, Cygwin, HP-UX, Linux, OSX и Solaris.
Получение процессорного времени:
#include <unistd.h>
#include <sys/times.h>
...
const double ticks = (double)sysconf( _SC_CLK_TCK );
struct tms tms;
if ( times( &tms ) != (clock_t)-1 )
return (double)tms.tms_utime / ticks;
clock( )
На всех UNIX-подобных ОС, очень старая функция clock( ) возвращает процессорное время процесса в тиках, а макрос CLOCKS_PER_SEC
количество тиков в секунду.
Заметка: Возвращенное процессорное время включает в себя время проведенное в user mode И в system mode от имени процесса.
Внимание: Хотя изначально CLOCKS_PER_SEC
должен был возвращать значение, зависящее от процессора, стандарты C ISO C89 и C99, Single UNIX Specification и стандарт POSIX требуют, чтобы CLOCKS_PER_SEC
имел фиксированное значение 1,000,000, что ограничивает точность функции микросекундами. Большинство ОС соответствует этим стандартам, но FreeBSD, Cygwin и старые версии OSX используют нестандартные значения.
Внимание: На AIX и Solaris, функция clock( )
включает процессорное время текущего процесса И и любого завершенного дочернего процесса для которого родитель выполнил одну из функций wait( )
, system( )
или pclose( )
.
Внимание: В Windows, функция clock( ) поддерживается, но возвращает не процессорное, а реальное время.
Доступность clock( ): AIX, BSD, Cygwin, HP-UX, Linux, OSX и Solaris.
Получение процессорного времени:
#include <time.h>
...
clock_t cl = clock( );
if ( cl != (clock_t)-1 )
return (double)cl / (double)CLOCKS_PER_SEC;
Другие подходы
Существуют и другие ОС-специфичные способы получить процессорное время. На Linux, Solarisи некоторых BSD, можно парсить /proc/[pid]/stat, чтобы получить статистику процесса. На OSX, приватная функция API proc_pidtaskinfo( )
в libproc
возвращает информацию о процессе. Также существуют открытые библиотеки, такие как libproc, procps и Sigar.
На UNIX существует несколько утилит позволяющих отобразить процессорное время процесса, включая ps, top, mpstat и другие. Можно также использовать утилиту time, чтобы отобразить время, потраченное на команду.
На Windows, можно использовать диспетчер задач, чтобы мониторить использование CPU.
На OSX, можно использовать Activity Monitor, чтобы мониторить использование CPU. Утилита для профайлинга Instruments поставляемая в комплекте с Xcode может мониторить использование CPU, а также много других вещей.
Downloads
- getCPUTime.c реализует выше описанную функцию на C. Скомпилируйте её любым компилятором C и слинкуйте с librt, на системах где она доступна. Код лицензирован под Creative Commons Attribution 3.0 Unported License.
Смотри также
Связанные статьи на NadeauSoftware.com
- C/C++ tip: How to measure elapsed real time for benchmarking объясняет как получить реальное время, чтобы измерить прошедшее время для куска кода, включая время, потраченное на I/O или пользовательский ввод.
- C/C++ tip: How to use compiler predefined macros to detect the operating system объясняет как использовать макросы
#ifdef
для ОС-специфичного кода. Часть из этих методов использовано в этой статье, чтобы определить Windows, OSX и варианты UNIX.
Статьи в интернете
- Процессорное время на википедии объясняет, что такое процессорное время.
- CPU Time Inquiry на GNU.org объясняет как использовать древнюю функцию clock( ).
- Determine CPU usage of current process (C++ and C#) предоставляет код и объяснения для получения процессорного времени и другой статистики на Windows.
- Posix Options на Kernel.org объясняет опциональные фичи и константы POSIX, включая _POSIX_TIMERS и _POSIX_CPUTIME.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Основная информация по работе на суперкомпьютере «Чебышёв»
На суперкомпьютере используется система управления очередями Cleo, информацию об основных командах смотрите ниже. Узлы суперкомпьютера разделены на несколько разделов (очередей). Основная очередь — regular. Есть раздел test, предназначенный для отладки приложений. Список очередей на кластере «Чебышёв» можно посмотреть на странице «Текущая конфигурация кластера»
Ваш домашний каталог является сетевым и доступен на вычислительных узлах.
На суперкомпьютере используется пакет mpi-selector для управления окружением компиляции и запуска. Перед началом работы Вам необходимо выбрать компилятор и реализацию MPI из списка доступных. После этого нужно открыть новую сессию на суперкомпьютер. Ваш выбор будет сохранён между сессиями.
Например, для компиляции программы компилятором Intel с IntelMPI, выполните команду:
mpi-selector —set intel_mpi_intel64-4.0.1.007
Обратите внимание, точные имена профилей могут отличаться.
Получить список активных подулей можно командой mpi-selector —list.
Запуск (точнее, постановка в очередь) осуществляется командой cleo-submit или mpirun. Команда cleo-submit настроена по умолчанию на запуск mvapich-приложений, если вы используете mpich, OpenMPI, IntelMPI или не используете MPI, укажите ключ -as mpich, -as openmpi, -as intel или -as single соответственно.
По умолчанию во всех командах используется очередь, указанная в переменной QS_QUEUE. Значение этой переменной можно изменить в файле ~/.bash_profile командой «export QS_QUEUE=queue_name».
Например, запуск MPI-приложения на 1024 ядра:
cleo-submit -np 1024 path/to/my/application
Часто используемые ключи команды cleo-submit:
-np NNN — число требуемых ядер (MPI-процессов)
-t ppn=NNN — число MPI-процессов на узел
-q NAME — имя раздела (очереди)
-maxtime MINS — лимит времени работы задачи в минутах
-stdout/-stderr/-stdin — перенаправление ввода/ошибок/вывода в файл
Например, если вам необходимо запустить задачу гибридную MPI+OpenMP программу на 512 ядер, но на каждом узле запустить только 2 MPI-процесса, используйте ключи -np 512 -t ppn=2. Для запуска в очереди test используйте ключ -q test.
Просмотр задач в очереди — командой tasks. С ключом -l будет выдана более подробная информация. Снять задачу со счёта или из очеред можно командой tasks с ключом -d. Подробнее о командах можно узнать в документации командой man имя_команды.
Если ваша задача требует немного временя для счёта, укажитя явно лимит её работы ключом -maxtime. В этом случае, задача может быть запущена до того, как она дойдёт до начала очереди, если ожидаемое время запуска других задач существенно не изменится.
Например, пусть на кластере свободно 8 процессоров, а в очереди уже стоит задача на 32 процессора (но все 32 процессора в ближайшие 7 часов не освободятся). Тогда если поставить в очередь короткую 4-процессорную задачу, указав максимальное время:
mpirun -np 4 -maxtime 10 program
то эта задача сразу пойдет на счет. Таким образом, вычислительные ресурсы будут распределяться более оптимально.
После постановки задачи в очередь пользователь может отключиться от терминала, а затем в любой момент подключиться к системе и просматривать результаты прежде запущенных задач. Командой cleo-attach можно подключиться к виртуальному терминалу задачи, как если бы она была запущена в этом терминале напрямую — это может быть нужно для интерактивных задач.
Просмотр результатов
По окончании работы задачи пользователю выдается сообщение на терминал (в дальнейшем будет организовано также оповещение по электронной почте). Выдача программы помещается в файл в рабочей директории с именем <задача>.out-<номер>. Кроме того, создается файл отчета <задача>.rep-<номер>, где указываются следующие данные: командная строка при запуске задачи, число процессоров, код возврата, имя выходного файла, рабочая директория, астрономическое время работы программы, имена узлов, на которых была запущена программа.