-2

是否可以创建一个程序，比如使用字节码，正常运行程序，并通过使用每条指令的定义运行时间来记录总运行时间？然后，一旦您的程序完成，您将获得一个准确的、与系统无关的运行时值，而无需一遍又一遍地运行您的程序并对结果进行平均，或者找到最小值。当然，这与实际运行时间之间的关系会因变量数量过多而有所不同，但至少可以选择使用这样的数字似乎还是不错的。

因此，为了清楚起见，这里有三个问题（对不起，但这只是为了简洁起见阻止了后续问题），相互建立：

  1. 是否有可能，或者是否有理论结果可以防止这种情况（停止问题或其他）？

  2. 如果可能，为什么从来没有使用过？由于许多实际原因，它似乎很有价值。

  3. 还是有一个存在而我只是想念它？

4

3 回答 3

0

Java实现：

int start = System.currentTimeMillis();

//Code to be timed...

int end = System.currentTimeMillis();
System.out.println(end - start);
于 2013-03-30T03:30:34.783 回答
0

如果您在同一台机器上运行所有程序并且使用进程的时间而不是实际运行时间，那么结果应该非常准确。查看 .Net 框架中的 Proccess 类，以便轻松理解这一点（它包含为您提供进程本身的 UserTime 和 KernelTime 的属性），这个类也是 OS proccess API 的一个很好的包装器。O 表示法给出了分析算法执行或复杂性的另一种方法，它需要对代码进行深入分析，问题是每个操作不需要相同的时间，所有这些理论都是为理想机器制定的。Maibe 做类似的事情，您将需要您想要支持的所有语言的口译员，并使所有这些都变得非常复杂。

于 2013-03-30T03:40:25.720 回答
0

The basic problem is that the number of times each instruction or method or whatever is executed is NOT a reliable predictor of anything ... except how long it will take to run the same program on the same input again.

To get a useful predictor, you need a good model of how the program's execution time depends on its inputs. Producing such a model automatically is not a tractable problem.

  • The Halting Theorem says that you cannot determine a priori whether any program is going to halt with a given input set.

  • In practice, theorem proving technology is not up to the task for anything but really simple programs.

  • Attempting to get model by empirical means (i.e. by trying to fit a curve to experimental results) is not going to work because:

    • It is not possible to work out (automatically) what the key variables are for the model. Indeed, the variables may not even be numeric.
    • Even if you managed that, you've now way of knowing if the program's performance is going to fit one of the classic curves with any degree of accuracy. You may get a model, but you have know way of knowing how accurate it will be.

Just to illustrate, consider the problem of factoring a large number. If the number has small factors, then the computation time will be quick. If it doesn't then ... well according to wikipedia, the worst case computational complexity of the best available method for factoring integers is:

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

where b is the number of bits in the number. That's intractable for large values of b.

So ...

  • A analytical solution which could give us a useful prediction would be equivalent to finding a fast analytical solution that says whether a number is (definitely) factorizable, and how large the factors are. This is a mathematically challenging problem.

  • An empirical solution cannot exist because no useful empirical model exists ... that doesn't involve first doing the factorization.

于 2013-03-30T04:38:34.327 回答