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

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

Log–logplot. 绘制log图也是衡量运行时间的一种方法,因为是log级别的,所以与上面说的经验公式没有本质区别,如下图右所示,取完对数后,输入数据大小与运行时间的对数变为线性关系。

数学分析 总的运行时长受到两个主要指标影响:

  • 执行每一个语句的成本
  • 执行每一个语句的次数

其中,第一个是系统属性,后面一个是算法的属性。假如我们知道了程序中所有指令的这两个属性值,那么两者相乘求和后便是整个程序的运行时间。

主要的挑战是确定第二个指标,即语句的执行次数。一些语句是很容易分析出执行次数,比如将count 设置初始值为 0,在 ThreeSum.count()中仅仅执行一次。

但是,有些需要更高层次的推理演算才能得到语句的执行频次,比如 if 语句被执行的次数恰好为:n(n-1)(n-2)/6.

4波浪线符号

我们用波浪线符号形成更加简单的近似表示。首先,我们用数学表达式的主项作为波浪线的近似表示。写作:∼g(n) . 表示为算法的时间复杂度,当它被 f(n) 除的时候,随着 n 的增大,g(n) 接近1. 我们也可以写 g(n) ~ f(n) 表示,随着 n 的增大g(n) / f(n) 接近1。

在这个表示下,我们忽略表达式中次要项。例如,在 ThreeSum.count()中的 if 语句的执行次数用波浪线表示为:∼n3/6. 因为 n(n-1)(n-2)/6 = n3/6 –n2/2+ n/3,当被n3/6 相除时,随着 n的增长,等于1.

我们专注于那些执行次数最多的指令,有时指内层循环。在 ThreeSum.java 程序中,我们可以合理地推理出内层循环以外的指令相对来说不重要。

5增长的阶数(order of growth)

分析一个程序的运行时长时,关键的一个点是大多数程序的运行时长满足关系:T(n) ~cf(n),此处c是一个常数,f(n)是一个关于时间的增长阶次函数。对于一些典型的程序,f(n)是一个函数,例如: log2n, n, nlog2n, n2 , n3

再看ThreeSum.java程序,增长的阶数等于 n3 , 常数c的值取决于执行指令的成本和次数的细节上,但是我们通常不需要算出精确值。刚才说加倍输入数据个数,运行时长变为原来8倍,具体推导公式如下:

下面详细列出程序的增长阶数的典型例子:

6内存消耗

除了需要考虑时间成本,我们也要注意内存消耗。内存消耗在Java程序中很好地被定义,但是java程序可以编译在各种不同配置环境的计算设备上,内存消耗因实现方式不同而不同,在这里讨论java中三种类型的内存消耗。

原生类型(Primitive types) 例如,因为java int数据类型是整数值的集合,取值范围位于:−2,147,483,648 ~ 2,147,483,647,所占的字节数为4个。如下图所示为主要原生类型所占的内存字节数:

对象(objects) 为了确定一个对象的内存消耗,我们需要求以下两者的和:

  • 每一个实例的内存消耗
  • 每一个对象关联的头部消耗,典型的是8个字节

例如,一个复数对象消耗内存为32个字节,其中16个字节被头部所占,另外,每个double变量各占8个字节。

对一个对象的引用通常消耗8个字节的内存。当一个数据类型包含一个对象的引用时,我们必须单独分配8个字节用于存储引用关系,每个对象的头部消耗16个字节,还包括此对象的实例变量所耗内存。

数组和字符串(Arraysand strings) 在java中,数组是通过objects被实现的,典型的实现方法:带有2个实例变量,一个指针指向第一个元素的首地址,另一个指向元素长度。对于原生类型,含有 n个元素的数组用24字节的头部信息,另外包括存储一个元素需要的字节数乘以元素个数。典型的例子如下:

原文发布于微信公众号 - Python与机器学习算法频道(alg-channel)

原文发表时间:2018-07-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]矩阵乘法

本次的题目来源于C语言网比赛栏目八月月赛第一题,记得去试试看看自己能不能AC哦!!! 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: ...

36050
来自专栏阮一峰的网络日志

关于2的补码

问一个基本的问题。 负数在计算机中如何表示? 举例来说,+8在计算机中表示为二进制的1000,那么-8怎么表示呢? 很容易想到,可以将一个二进制位(bit)专门...

29330
来自专栏AI派

Numpy 修炼之道 (13)—— 将python函数向量化

想要实现将python函数向量化,Numpy中的vectorize 和frompyfunc函数都可以满足要求。

44970
来自专栏小樱的经验随笔

HUST 1588 辗转数对

1588 - 辗转数对 时间限制:1秒 内存限制:128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b),我们可以通过一步将这个数对...

34690
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K50
来自专栏Java成神之路

计算字符串相似度算法——Levenshtein

Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。

90810
来自专栏Python区块链

人工智能实现程序员“防”BOSS?刷脸就发短信,8行代码人脸报警

如今一个攻城狮就能搞定人脸的深度进修算法,这要多感激打动国外开源框架,虽然达不到旷世face++和诸多人脸公司的深度,可是实际应用已经没有太大压力。下图就是te...

470120
来自专栏书山有路勤为径

分治算法之归并排序

分治算法: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的解后进行合并,就可得到原问题的解。

8310
来自专栏SimpleAI

Python高级特性——为什么都说Python高效

本微教程根据廖雪峰python教程中的部分内容,配合我个人的学习经历进行总结整理。

12940
来自专栏Crossin的编程教室

【每周一坑】罗马数字转换

罗马数字是欧洲在阿拉伯数字传入之前使用的一种数码,现在的使用已经非常少了,大概偶尔会在钟表、文章中的标号等地方还能见到。 罗马数字采用七个罗马字母作数字、即 I...

41370

扫码关注云+社区

领取腾讯云代金券