Algorithm_Execution_time_and_cost [英] Algorithm_Execution_time_and_cost

问题描述

我正在学习如何使用算法在Java中编程，我的问题是是否有办法知道哪种算法比其他算法更快?我怎么知道算法成本，哪一种算法最有效.我在网络上阅读了很多，但是我唯一能找到的就是很多奇怪的公式，但是没有关于如何实现它们的示例.例如，如果我有2种算法:冒泡排序和插入排序，如何计算每个算法的执行时间，以及如何知道哪种算法最快，最好用.请有人给我一个例子，或者至少给我展示一个易于理解的方式，我将不胜感激.或者如果有我可以使用的软件，那也将非常方便.

I''m learning how to program in java using algorithms, my question is is there a way to know what algorithm is faster than others? How can I know an algorithm cost, and which will be the most effective. I''ve read a lot on the web about it but the only thing I could find is lots of weird formulas but no examples on how to implement them. For example if I have 2 algorithms : Bubble sort and Insertion sort how can I calculate the execution time of each of them and how can I know which one will be fastest and best to use. please if someone can give me an example or at least show me and understandable way to know it I''d appreciate it. or if there''s a software that I could use for that purpose, that would be handy as well thanks.

推荐答案

在一般情况下，从理论上讲是不可能的计算执行时间，因为问题的行为通常是不可预测的.特别是，在一般情况下，甚至无法预测程序是否已完成执行或将永远运行，因为已证明停顿问题，请参见 ^ ]，另请参见 http://en.wikipedia.org/wiki/Computability_theory [ ^ ].如果无法确定运行时间是否是无限的，则不可能预先比较不同算法的执行时间.

这是一般情况.在简单的情况下，在某些假设下这是可能的.使用算法计时的实验有助于在比较中获得一个相当不错的主意.关于算法速度比较，有足够的文献.用于比较排序算法( http://en.wikipedia.org/wiki/Sorting_algorithm [ http://www.devx.com/vb2themax/Article/19900 [ ^ ].

这是一篇有关用Java实现的算法分析的有趣文章: http://www.cs.cmu.edu/~pattis/15-1XX/15-200/lectures/aa/lecture.html [ http://en.lmgtfy.com/?q=comparison+speed+of+ sorting + algorithms + java [ ^ ].

—SA

In a very general case, it is theoretically impossible to calculate executing time, because the behavior of the problem is in general case unpredictable. In particular, in general case it is even impossible to predict if the program finished execution or will run forever, as it is proven Halting problem, see http://en.wikipedia.org/wiki/Halting_problem[^], see also http://en.wikipedia.org/wiki/Computability_theory[^]. If it is impossible to tell if run time if infinite or not, it is impossible to compare time of execution of different algorithms in advance.

This is in general case. In simple cases, this is possible under certain assumption. Experiments with algorithm timing helps to get a pretty good idea on the comparisons. There enough literature on algorithm speed comparison. For comparison of sorting algorithms (http://en.wikipedia.org/wiki/Sorting_algorithm[^]), see for example: http://www.devx.com/vb2themax/Article/19900[^].

This is an interesting article on analysis of algorithms implemented in Java: http://www.cs.cmu.edu/~pattis/15-1XX/15-200/lectures/aa/lecture.html[^].

Try to Google to get more information:
http://en.lmgtfy.com/?q=comparison+speed+of+sorting+algorithms+java[^].

—SA

您有很多选择.
原谅我的Java，距我使用它已经有一段时间了.

您可以在代码中添加计时器.

You have a number of options.
Forgive my Java, it has been a while since I have used it.

You can add timers into your code.

long nStartTime = System.nanoTime();
Sort();
long nEndTime = System.nanoTime();
System.out.println("Execution Time: %fns", nEndTime - nStartTime);

这仅作为一般指南，不能依赖.
这是因为它测量了开始和结束之间的时间，但是多任务操作系统将在算法的开始和结束之间将您的程序从CPU切换出并返回几次，在此期间定时器仍在运行. br/> 通过一次不执行任何操作，然后再次进行繁重的负载(例如转换影片或基准测试)，可以轻松观察到这一点.

我没有使用过它，但是我听说其中一个Java IDE(也许是NetBeans或Eclipse)有一个探查器，您可以使用该探查器来分析特定的功能.这基本上与先前的解决方案相同.我不确定这是否与上述解决方案有相同的问题.

最终的解决方案需要Unix/Linux系统，OSX也可以正常工作.
制作一个仅包含您的算法的程序，并进行代码测试.

This only works as a general guide, and cannot be relied upon.
That is because this measures the time between start and end, however multi-tasking operating systems will have switched your program out of the CPU and back in several times between the start and end of the algorithm, during which the timer is still running.
This can be observed easily by running once with nothing else running, and then again under heavy load such as converting a movie or benchmarking.

I havn''t used it, but I heard that 1 of the Java IDEs (perhaps NetBeans or Eclipse) has a profiler, which you can use for profiling specific functions. This is essentially the same as the previous solution. I am not sure if this has the same problem as the solution above.

A final solution requires a Unix/Linux system, OSX may work as well.
Make a program that only contains your algorithm, and code to test it.

static void main(String []args) {
    //load data into an array or whatever
    Sort();
}

然后运行此代码两次，第一次注释掉对Sort()的调用，并从Unix shell运行命令time java MySort，以执行加载初始数据的时间.
接下来取消对Sort()的调用的注释，然后重新编译并运行相同的time java MySort命令.

time命令提供了Real，System和User时间.
实时是您在第一个解决方案中所观察到的，它计算出该进程不在CPU中的时间.
用户时间是执行代码所花费的时间.
系统时间是执行系统命令(包括文件读/写)所花费的时间.
算法的总时间是用户和系统时间的总和.这是您用来评估脚本效率的方法.参见 Wikipedia [

Then run this code twice, the first time comment out the call to Sort() and run the command time java MySort from the Unix shell to time execution time of loading the initial data.
Next uncomment the call to Sort() and recompile and run the same time java MySort command.

The time command gives Real, System and User times.
The Real time is what you would observe with the first solution, which counts time that the process is not in the CPU.
The User time is how long it took to execute your code.
The System time is how long it took to execute system commands, including file read/write.
The total time of your algorithm is the sum of User and System times. This is what you should use for evaluating the efficiency of your script. See Wikipedia[^] for more details on the Unix time command.

The execution time of your algorithm is the total time of the loading sorting minus the total time of the loading only.
(user_sort + system_sort) - (user_load + system_load)

这篇关于Algorithm_Execution_time_and_cost的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！