Время выполнения алгоритма в Pascal

[IvanUsach]

Здравствуйте. Есть вопрос: как в Паскале узнать время, за которое выполнился алгоритм? Не могли бы подсказать? Вроде надо подпрограмму составлять?
И ещё, просветите новичка, пожалуйста: что такое трудоемкость алгоритма и как её узнать (в том же Паскале)?
Спасибо.

[ИСН]

Дёрните gettime() два раза - до и после. И никаких подпрограмм.

[IvanUsach]

Однако, ругается почему-то: Unknown identifier

[ewert]

Эта процедура -- из юнита DOS, который надо подключить.

[Йа Гринько]

IvanUsach в сообщении #181457 писал(а):

что такое трудоемкость алгоритма и как её узнать (в том же Паскале)?

Трудоемкость алгоритма, это функция от размера входных данных,
описывающая необходимое для выполнения количество элементарных операций.
Например трудоемкость QuickSort $n\log n$, где $n$ число элементов массива.
А элементарная операция здесь - перестановка

Трудоемкость алгоритма не зависит от того языка на котором вы его реализуете,
а подсчет трудоемкости задача в общем случае нетривиальная.

[Danila88]

Можно "схалтурить" :
создать .bat-файл такого содержания:
time> time.txt
program.exe
time> time.txt
а потом брать разность времён... (только это эффективно для "долгих" программ-порядка 1 мин), впрочем не обращайте внимания...

[ewert]

не нужно халтурить. Упомянутая процедура (базирующаяся наверняка на стандартных прерываниях) задачу вполне решает. Надо только её подключить.

--------------------------------------------------------------
(там, если мне не отшибает память -- точность отсчёта порядка одной миллисекунды)

[Danila88]

Может-некорректно, но всегда интересовало- ведь время вызова процедуры (или чего-то в этом роде) наверняка больше одной mls, смысл измерять с такой точностью?

[ewert]

почему больше? программа ведь компилируется, а время вызова любой процедуры (уже сидящей после компиляции в оперативной памяти) -- ничтожно мало.

[Danila88]

ewert писал(а):

а время вызова любой процедуры (уже сидящей после компиляции в оперативной памяти) -- ничтожно мало.

Это и хотелось уточнить.

Добавлено спустя 1 минуту 27 секунд:

Спасибо.

[PAV]

ewert писал(а):

почему больше? программа ведь компилируется, а время вызова любой процедуры (уже сидящей после компиляции в оперативной памяти) -- ничтожно мало.

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

Добавлено спустя 3 минуты 14 секунд:

К тому же, результат примитивного измерения времени выполнения может быть неточным из-за загрузки процессора другими потоками, выполняемыми параллельно или в фоне, а также узкими местами, связанными с вводом-выводом данных на диск или на экран.

[ewert]

Параллельность потоков -- это действительно проблема (для измерения), поскольку -- внешняя по отношению к программе. А вот ввод-вывод сами по себе к делу не относятся.

Что касается многократных вызовов -- тоже не по делу. Если мы, например, пытаемся оценить время работы самой процедуры, то существенно лишь, чтобы время вызова было много меньше времени исполнения. Т.е. чтобы тело процедуры было мало-мальски содержательным.

(я вообще-то по натуре не программист, но -- опыт показывает)

[PAV]

Речь шла вроде о том, что мы оцениваем время работы программы, замеряя момент ее старта и завершения. Проблема заключается в том, что накладные расходы могут результат этого измерения исказить.

Допустим, что программа заключается в многократном выполнении тела некоторого цикла, причем одна итерация цикла занимает очень малое время. Какой-нибудь метод последовательных приближений. Количество итераций достаточно велико, так что общее время выполнения программы, скажем, измеряется в десятках секунд. Для контроля того, как работает программа, можно, например, на каждой итерации выводить на экран номер этой итерации или же какую-нибудь дополнительную информацию. Последние несколько цифр номера итерации мелькают на экране очень быстро, но первые вполне видны. Мой опыт показывает, что на этом шаге если выводить данные не на каждой итерации, а, скажем, на каждой сотой или тысячной, то ускорение времени будет вполне заметным даже "на глаз". При том, что содержательная часть ровно такая же. Это пример накладных расходов от частого вывода на экран.

Аналогично могут быть накладные расходы от операций работы с диском. Могу привести пример из собственной практики. Необходимо было провести работу с некоторыми данными, которые были записаны в файлы. Файлы были небольшого размера и их было много. Программа работала реально медленно. Потом я склеил все данные в один огромный файл (размером в несколько гигабайт). Разумеется, для работы с ним пришлось применять специальные функции ОС. Ускорение от этой процедуры было на один-два порядка. Причина - в накладных расходах, связанных с процедурами открытия-закрытия файла.

Еще один пример, который я также реально наблюдал, связан с кешем жесткого диска. Прочитанные данные хранятся в этом кеше и при повторном чтении грузятся гораздо быстрее. При этом программа, подобная предыдущей, при двух последовательных запусках работала существенно разное время.

С многократными вызовами простых и сравнительно бессодержательных процедур и необходимостью их оптимизации я также сталкивался.

Что же касается проблем измерения времени, связанных с паралеллизмом, то это, конечно, проблема, в том смысле, что это нельзя учесть средствами самой программы. Но операционная система при распределении процессорного времени между потоками аккуратно подсчитывает, кто сколько получал, и имеются специальные функции, которыми можно у ОС спросить, сколько реально процессорного времени было выделено заданному потоку. Так что это решено.

Все это я к тому лишь, что существует ряд технических деталей, которые могут повлиять на время выполнения программы и исказить картину, если задача стоит о практической оценке трудоемкости чистого алгоритма.

[ewert]

вот, кстати, я буквально в этот момент на коленке пытаюсь запрограммировать нечто теплопроводное. И как раз с целью определить трудоёмкость. Т.е. вопрос фактически таков: можно ли будет потом встроить эту программку в некий продукт так, чтоб он мог работать в режиме "реального времени" -- или будет тормозить?

А поскольку коэффициент теплопроводности задан принципиально ступенчатым образом (область разбита на кирпичики) -- его нахождение становится не вполне тривиальным. Поэтому я просто выделил итерацию на каждом узле в отдельную процедуру -- обращение к ней в любом случае потребует много меньше времени, чем собственно работа.

Ну это к слову. А спросить хотелось вот о чём. У меня несколько дней назад почему-то перестались запускаться все ДОСовские приложения из-под ФАРа. (в т.ч. и сам ФАР -- при попытке запустить его из-под себя как вторую копию). Система срывается -- выводится сообщение, что ей там чего-то не в жилу и что через минуту перезагрузится.

Под Тотал Командером вроде работать можно, но -- тоже с некоторыми заморочками.

Что бы это могло быть?

[PAV]

Еще раз выскажу мнение, что любой серьезный анализ производительности и поиск узких мест должен основываться на профилировании.

А второй вопрос - это в данной теме оффтопик. Можете задать его отдельной темой. Но в любом случае вряд ли можно на него содержательно ответить, если Вы не напишете, о какой ОС идет речь и как именно она ругается.