Расчет точного времени выполнения, а не фактического времени выполнения
Можно ли создать программу, которая, скажем, с помощью байтового кода, запускает вашу программу как обычно, с учетом общего времени выполнения, используя определенные значения времени выполнения каждой инструкции на ходу? Затем, как только ваша программа будет завершена, вы получите точное, независимое от системы значение для времени выполнения, без необходимости многократно запускать вашу программу и усреднять результаты или находить мин. Конечно, связь между этим и фактическим временем выполнения различается в зависимости от чрезмерного количества переменных, но все же кажется, что такая цифра была бы хорошей, по крайней мере, иметь возможность использовать.
Итак, для ясности, здесь есть три вопроса (извините, но это просто мешает ответить на вопросы для краткости), опираясь друг на друга:
-
Это возможно, или есть теоретический результат, который предотвращает это (остановка проблемы или что-то)?
-
Если это возможно, почему это никогда не используется? Это кажется ценным по многим практическим причинам.
-
Или есть тот, который существует, и я просто скучаю по нему?
Решение
Основная проблема заключается в том, что количество выполнений каждой инструкции, метода или чего-либо еще НЕ является надежным предиктором чего-либо … за исключением того, сколько времени потребуется для запуска той же программы на том же входе снова.
Чтобы получить полезный предиктор, вам нужна хорошая модель того, как время выполнения программы зависит от ее входных данных. Автоматическое создание такой модели не является проблемой.
-
Теорема Остановки говорит, что вы не можете определить априори будет ли какая-либо программа остановлена с заданным набором ввода.
-
На практике технология доказательства теорем не является задачей ни для чего, кроме действительно простых программ.
-
Попытка получить модель эмпирическим путем (то есть путем подбора кривой к экспериментальным результатам) не будет работать, потому что:
- Невозможно определить (автоматически), какие ключевые переменные для модели. Действительно, переменные могут даже не быть числовыми.
- Даже если вам это удалось, теперь у вас есть способ узнать, будет ли производительность программы соответствовать одной из классических кривых с любой степенью точности. Вы можете получить модель, но у вас есть способ узнать, насколько точной она будет.
Просто для иллюстрации рассмотрим проблему факторизации большого количества. Если число имеет небольшие факторы, то время вычисления будет коротким. Если этого не произойдет … в соответствии с Википедией, сложность вычислений в худшем случае наилучшего из доступных методов для разложения целых чисел:
O(exp(((64b/9)^(1/2).(log b)^(2/3)))
где b это количество бит в числе. Это трудно для больших значений b,
Так …
-
Аналитическое решение, которое могло бы дать нам полезный прогноз, было бы эквивалентно быстрому аналитическому решению, которое говорит о том, является ли число (определенно) факторизуемым, и насколько велики факторы. Это математически сложная проблема.
-
Эмпирическое решение не может существовать, потому что не существует полезной эмпирической модели … которая не предполагает сначала факторизации.
Другие решения
Реализация Java:
int start = System.currentTimeMillis();
//Code to be timed...
int end = System.currentTimeMillis();
System.out.println(end - start);
Если вы запускаете все программы на одном компьютере и используете время Процесса, а не реального времени выполнения, результаты должны быть очень точными. Взгляните на класс Proccess в .Net framework для простоты понимания этого (он содержит свойства, которые предоставляют вам UserTime и KernelTime самого процесса), также этот класс является хорошей оболочкой для API процесса OS.
Другой взгляд на анализ выполнения или полноты алгоритма дается нотацией O, которая потребует глубокого анализа кода, проблема в том, что каждая операция не занимает одно и то же время, вся эта теория создана для идеальной машины.
Чтобы сделать что-то подобное, вам понадобятся переводчики для всех языков, которые вы хотите поддерживать, и сделать все, что будет чрезвычайно сложным.