《计算机算法——设计与分析导论》 边读边记

Chapter 1

1.3 Mathematical Background
这段太……太勾起回忆了。这东西一看就是离散数学和概率统计 T T
对我来说不算是什么好的回忆，不过这些数学知识确实很重要。我得加把劲把数学赶上来才行。


Chapter 3

3.5.3 The Single-Assignment Paradigm
我们软工专业对算法的要求也真是太低了。课程里都没怎么多涉及算法分析。结果看到这个小节的时候觉得一懵：我手上这本不是编译器相关的书？
原来是我少见多怪了。为了写出更容易被证明的代码，需要尽量减少两种结构的使用：goto和赋值语句。在命令式语言中，赋值语句不太可能被去除，所以研究人员从去除goto着手而创立了结构化程序设计的领域。结构化的程序有助于控制流的分析，但对数据流还是没什么帮助。后来，研究人员发现为了能清晰的分析一个算法，并不是要避免所有的赋值语句，而只要避免“重写赋值”就行。也就是说一个变量只能被赋值一次。
在函数式语言中，SA的概念已经很常见了。不过一般就不把赋值称为赋值，而是成为“绑定”或者“定义”吧？
命令式语言本身可能难以避免对同一变量的多次赋值问题，不过在编译的时候却经常会为了更有效的分析数据流而采用SSA形式。而我之前对SA的认识一直就是与SSA相关联，所以一看到SA就以为是看到了编译相关的书了……


Chapter 10 Dynamic Programming

exercise 10.18, P478
本来是想找找这书上有没有解决longest common substring问题的现成的解决方案，可惜没有。唯一相关的内容就是这道题目了。放在这一章里，很明显就是要用动态规划来做了，于是会用个二维矩阵之类的数据结构吧。这个问题另外一种常见的解决方法是使用后缀树，不过后缀树也没有什么现成的实现可用，自己实现也挺麻烦的……挠挠头，放下了。

评论

4 楼 RednaxelaFX 2008-02-23  

...前面举的例子是示意...
编译命令式语言的时候,如果编译器的优化做得好,也会采用SSA形式的中间代码.这个时候优化器会完成相应的转换,不用我们手工做.

至于这本算法书,它说的是可以把自己自觉的以单赋值的方式来使用局部变量.这样就能比较清楚的观察局部作用域内的数据流,方便分析算法的性质和复杂度之类.

3 楼 lwwin 2008-02-23  

难道需要手动修改符号么……
嗯……应该是在一定的范围内部进行特殊处理……？

2 楼 RednaxelaFX 2008-02-23  

SA就是上面说的Single-Assignment啊，也就是单赋值。SSA是Static Single-Assignment。
当一个变量最多只被赋值一次的时候，就能比较清晰的分析数据流。编译的时候，为了让优化器能更好的理解程序的实际状况，会将中间代码转变为SSA形式的代码，这样就能很方便的找出冗余赋值、无用变量等状况。

例如说原本是这样的代码：

int x, y;
x = 1;
y = x + 1;
x = 0;

可以转变为：

int x1, x2, y1;
x1 = 1;
y1 = x1 + 1;
x2 = 0;

这样，即使在比较复杂的状况下也能够清晰的看出数据流动的路径。

1 楼 lwwin 2008-02-23  

“也就是说一个变量只能被赋值一次。 ”怎么想到了CD-R ……
当然CD-R多了会觉得太麻烦所以CD-RW诞生了-v-+，
PS另外CD-R有时候价格太贵了……

SA是啥FX大需要解释一下的……