-
C#教程之程序员必知的算法和数据结构：2500字性能总结
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
在这一章节，我们将要学习一个编程非常重要的事情：成本(cost)，这是无论何时编码，你都要去思考的一件事。为了研究程序运行的成本，我们必须遵循科学的方法(Scientific method)来研究我们所写的程序。我们也会应用数学分析(mathematical analysis)去推理形成精确的成本模型。
1科学方法(Scientific method)
以下5个步骤总结了此方法，依次为如下，我们设计的实验必须是可以重现的，我们形成的假设必须是具有真伪的。
2观察(Observations)
测试程序运行的精确时间有时是困难的，但是我们有许多辅助工具。在这里，我们简化程序运行时间的模型，考虑各种输入情况，并测试每种情况下的运行时间，编写的这个程序名称为：Stopwatch.java，如下所示：
1public class Stopwatch {
2
3 private final long start;
4
5 public Stopwatch() {
6 start = System.currentTimeMillis();
7 }
8
9 public double elapsedTime() {
10 long now = System.currentTimeMillis();
11 return (now - start) / 1000.0;
12 }
13
14 public static void main(String[] args) {
15 int n = Integer.parseInt(args[0]);
16
17 // sum of square roots of integers from 1 to n using Math.sqrt(x).
18 Stopwatch timer1 = new Stopwatch();
19 double sum1 = 0.0;
20 for (int i = 1; i <= n; i++) {
21 sum1 += Math.sqrt(i);
22 }
23 double time1 = timer1.elapsedTime();
24 StdOut.printf("%e (%.2f seconds)\n", sum1, time1);
25
26 // sum of square roots of integers from 1 to n using Math.pow(x, 0.5).
27 Stopwatch timer2 = new Stopwatch();
28 double sum2 = 0.0;
29 for (int i = 1; i <= n; i++) {
30 sum2 += Math.pow(i, 0.5);
31 }
32 double time2 = timer2.elapsedTime();
33 StdOut.printf("%e (%.2f seconds)\n", sum2, time2);
34 }
35}
对于大多数程序，首先我们能想到的量化观察是它们有问题的大小( problem size)区别，这个表征了计算复杂度或计算难度。一般地，问题大小既可以指通过输入数据的大小，也可以指通过命令行参数输入值。直觉上，运行时间应该会随着问题大小而增加，但是增加的程度怎么度量，这是我们编程运行程序时常遇到的问题。
3具体例子
为了阐述方法，我们先引入一个具体的编程问题：ThreeSum，它是在给定的含有 n 个元素的数组中找出三元组之和等于0的个数。这个问题最简单的一个解法：枚举，代码如下：
1public class ThreeSum {
2
3 // print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
4 public static void printAll(int[] a) {
5 int n = a.length;
6 for (int i = 0; i < n; i++) {
7 for (int j = i+1; j < n; j++) {
8 for (int k = j+1; k < n; k++) {
9 if (a[i] + a[j] + a[k] == 0) {
10 StdOut.println(a[i] + " " + a[j] + " " + a[k]);
11 }
12 }
13 }
14 }
15 }
16
17 // return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
18 public static int count(int[] a) {
19 int n = a.length;
20 int count = 0;
21 for (int i = 0; i < n; i++) {
22 for (int j = i+1; j < n; j++) {
23 for (int k = j+1; k < n; k++) {
24 if (a[i] + a[j] + a[k] == 0) {
25 count++;
26 }
27 }
28 }
29 }
30 return count;
31 }
32
33 public static void main(String[] args) {
34 int[] a = StdIn.readAllInts();
35 Stopwatch timer = new Stopwatch();
36 int count = count(a);
37 StdOut.println("elapsed time = " + timer.elapsedTime());
38 StdOut.println(count);
39 }
40}
我们在这里主要关心的是输入数据大小与运行时长的关系。我们循着如下的思路分析两者间的关系：
加倍假设(Doubling hypothesis) 对于大量的程序而言，我们能很快地形成如下假设：假如输入数据的个数加倍，运行时间怎么变化。
经验分析(Empirical analysis) 一种简单的实现加倍假设的方法是使输入数据的个数加倍，然后观察对运行时长的影响。如下所示为一个简单的通过加倍输入个数，测试运行时长的程序：DoublingTest.Java.
1public class DoublingTest {
2
3 public static double timeTrial(int n) {
4 int[] a = new int[n];
5 for (int i = 0; i < n; i++) {
6 a[i] = StdRandom.uniform(2000000) - 1000000;
7 }
8 Stopwatch s = new Stopwatch();
9 ThreeSum.count(a);
10 return s.elapsedTime();
11 }
12
13
14 public static void main(String[] args) {
15 StdOut.printf("%7s %7s %4s\n", "size", "time", "ratio");
16 double previous = timeTrial(256);
17 for (int n = 512; true; n += n) {
18 double current = timeTrial(n);
19 StdOut.printf("%7d %7.2f %4.2f\n", n, current, current / previous);
20 previous = current;
21 }
22 }
23}
再回到ThreeSum.java程序中，我们生成一系列随机数，填充到输入数组中，每一个时步都加倍输入元素个数，然后观察到每一次程序所运行的时间都会大致增加8倍，这个就可以让我们下结论说输入数据加倍后运行时间增加了8倍。如下图中左侧视图所示，当输入大小为4K时，运行时长为64T，当输入带下为8K时，运行时长变为原来的8倍：512T.
