Generally we compare algorithms by
■ Implementing and debugging them
■ Analyzing their basic properties
■ Formulating a hypothesis about comparative performance
■ Running experiments to validate the hypothesis
These steps are nothing more than the time-honored scientific method, applied to the study of algorithms.
Suppose you have implemented several sorting algorithms, to validate this hypothesis, we use SortCompare to perform the experiments. We use Stopwatch to compute the running time. The implementation of time() shown here does the job for the basic sorts in this chapter. The “randomly ordered” input model is embedded in the timeRandomInput() method in SortCompare, which generates random Double values, sorts them, and returns the total measured time of the sort for the given number of trials. Using random Double values between 0.0 and 1.0 is much simpler than the alternative of using a library function such as StdRandom.shuffle() and is effective because equal key values are very unlikely. The number of trials is taken as an argument both to take advantage of the law of large numbers (the more trials, the total running time divided by the number of trials is a more accurate estimate of the true average running time) and to help damp out system effects.
public class Stopwatch { private final long start; /** * Create a stopwatch object. */ public Stopwatch() { start = System.currentTimeMillis(); } /** * Return elapsed time (in seconds) since this object was created. */ public double elapsedTime() { long now = System.currentTimeMillis(); return (now - start) / 1000.0; } }
/** * Replace this line with class description. * <p/> * User: George Sun * Date: 9/15/13 * Time: 9:45 PM */ public class SortCompare { public static void main(String[] args) { String alg1 = args[0]; String alg2 = args[1]; int N = Integer.parseInt(args[2]); int T = Integer.parseInt(args[3]); double t1 = timeRandomInput(alg1, N, T); double t2 = timeRandomInput(alg2, N, T); StdOut.printf("For %d random Doubles\n %s is: ", N, alg1); StdOut.printf(" %1f times faster than %s\n", t2 / t1, alg2); } public static double timeRandomInput(String alg, int N, int T) { double total = 0.0; Double[] a = new Double[N]; for (int t = 0; t < T; t++) { for (int i = 0; i < N; i++) { a[i] = StdRandom.uniform(); } total += time(alg, a); } return total; } public static double time(String alg, Comparable[] a) { Stopwatch timer = new Stopwatch(); switch (alg) { case "Insertion": Insertion.sort(a); break; case "Selection": Selection.sort(a); break; case "Shell": Shell.sort(a); break; case "Merge": Merge.sort(a); break; case "Quick": Quick.sort(a); break; case "Heap": Heap.sort(a); break; case "InsertionSentinel": InsertionWithSentinel.sort(a); break; default: System.err.println("No algorithm specified, end."); break; } return timer.elapsedTime(); } }
相关推荐
很经典的一篇分析和比较蒙哥马利模乘不同的实现方式的文章
Comparing different supervised machine learning algorithms for disease prediction
comparing of autofocus algorithms
Secure comparing two sets is an important problem in secure multiparty computation. The research on privately determining whether two sets are equal has not been investigated. This study solves the ...
Java sorting objects with equals and hashcode override
Increased quantitative information about the algorithms, giving you a basis for comparing them Over 1000 new exercises to help you learn the properties of algorithms Whether you are learning the ...
multiway radix sorting, randomized BSTs, splay trees, skip lists, multiway tries, B trees, extendible hashing, and much more * Increased quantitative information about the algorithms, giving you a ...
比较算法 比较算法类的课程材料 第 1 课 - 搜索和简单递归 介绍是如何计算几个搜索算法和一些著名的递归怪物的复杂性。 第 2 课 - 数据结构 链表、二叉树、堆和数组之间的区别。 第 3 课 - 排序 ...
we give some experimental results comparing a few of the algorithms discussed in this paper. Keywords: Boosting algorithms, multiclass classification, output coding, decision trees
Abstract: With the development of engineering technology and the improvement of mathematical model, a large number of optimization ...the algorithm was verified by comparing with other algorithms
Abstract: With the development of engineering technology and the improvement of mathematical model, a large number of optimization ...the algorithm was verified by comparing with other algorithms.
hash code comparing objects in java collections.
We address the problem of comparing samples from two probability distributions, by proposing statistical tests of the null hypothesis that these distributions are equal against the alternative ...
Characterizing and Comparing Phylogenies from their Laplacian Spectrum
随书前言如下:Learn Data Structures and Algorithms with Go covers topics related to simple and advanced concepts in computer programming. The primary objective is to choose the correct algorithm and ...
Attention Flows:Analyzing and Comparing Attention Mechanisms in Language Models
老外比较的各种低功耗无线技术, 有Bluetooth low energy, zigbee 等目前热门的技术。
论文 Comparing Linear Discriminant Analysis and Support Vector Machine. 2002. 欢迎下载。
Comparing Media Codecs for Video Content
Comparing with the generator.docxComparing with the generator.docx