Вычисление точного времени выполнения, а не фактического времени выполнения

Question

Можно создать программу, которая, скажем, с байтовым кодом, запускает вашу программу как обычно, сохраняя подсчет общего времени выполнения, используя определенные промежутки времени каждой команды, так как вы идти? Затем, как только ваша программа закончится, у вас будет точное, независимое от системы значение для времени выполнения, без необходимости многократно запускать вашу программу и усреднять результаты или находить мин. Разумеется, связь между этим и фактическим временем выполнения отличается в зависимости от избыточного количества переменных, но все же кажется, что такая цифра была бы хорошей, по крайней мере, иметь возможность использовать.

Итак, для ясности, есть три вопроса здесь (извините, но это только предотвращает последующие вопросы для лаконичности), опираясь друг на друга:

1. Является ли это возможно, или есть теоретический результат, предотвращает это (проблема с остановкой или что-то еще)?

2. Если это возможно, почему это никогда не используется? Это кажется ценным по многим практическим причинам.

3. Или есть один, который существует, и я просто пропустил его?

Answer 1

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

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

• Остановка теорема говорит, что вы не можете определить, априори собирается ли какая-либо программа, чтобы остановить с данным входным набором.

• На практике технология доказательства доказательств не соответствует задаче ни для чего, кроме действительно простых программ.

• Попытка получить модель эмпирическим путем (т.е. подстраиваться кривую к экспериментальным результатам) не будет работать, потому что:

  • Это не возможно работать (автоматически), что ключ переменные для модели. Действительно, переменные могут даже не быть числовыми.
  • Даже если вам это удалось, теперь у вас есть возможность узнать, будет ли производительность программы соответствовать любой из классических кривых с любой степенью точности. Вы можете получить модель, но у вас есть способ узнать, насколько она будет точной.

---

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

O(exp(((64b/9)^(1/2).(log b)^(2/3))) 

где b это количество битов в количестве. Это невозможно для больших значений b.

Итак ...

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

• Эмпирическое решение не может существовать, потому что не существует полезной эмпирической модели ... которая не включает в себя прежде всего факторизацию.

Answer 2

реализация Java:

int start = System.currentTimeMillis(); 

//Code to be timed... 

int end = System.currentTimeMillis(); 
System.out.println(end - start); 

Answer 3

Если запустить все программы в той же машине и использовать время от Proccess не реальное время работы результаты должны быть очень accurrate. Взгляните на класс Proccess в .NET Framework, чтобы легко понять это (он содержит свойства, которые дают вам UserTime и KernelTime самого процесса), и этот класс является хорошим драйвером для API pro proxy. Другим взглядом на анализ выполнения алгоритма или его завершенности является нотация O, которая потребует глубокого анализа кода, проблема с которой заключается в том, что каждая операция не занимает одно и то же время, вся эта теория затухает для идеальной машины. Maibe для чего-то подобного вам потребуются переводчики для всех языков, которые вы хотите поддержать, и сделайте все, что будет чрезвычайно сложным.