程序员必知的算法和数据结构:2500字性能总结|C#教程

金沙澳门官网网址:www.js333com

VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > c#教程 >
  • 程序员必知的算法和数据结构:2500字性能总结

本站最新发布   C#从入门到精通
试听地址  
/eschool/CSharp奥门金沙网址/

在这一章节,我们将要学习一个编程非常重要的事情:成本(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 = 512true; 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.

 

相关教程
        
Baidu
sogou