Lec10.

Search

• ordered - binary - log n
• unordered - liner - n

Divide & conquer(分治)

• split the problem into several sub-problem of the same type
• solve independently
• combine solutions

MergeSort(归并排序)

• divide list in half.
• continue until we have single lists.
• merge of the sublists

复杂度:n(每一次要操作的数的个数)logn(归并的次数)
适用的场合:要归并的元素不是很复杂而且归并的操作简单

Hashing:

• 牺牲空间来换取时间效率
• hard to create(需要寻找一个好的哈希函数)

Python语法.Exception:

• unhandle
• handle:捕获可以预期的异常并且处理.

Exception vs Assert

• 断言是一种测试,保证断言的语句为真才能继续执行下去
• 异常保证程序在出现预期的出错的时候可以处理它

使用异常的原因:为了保证在异常出现的时候可以正确的捕获和处理它,而不是使得异常向别的地方抛出并且扩散,使得错误无法正确的定位(难以Debug).

Lec11.

Testing && Debugging:

Validation:(验证过程)

• process to uncover problems & inciease confidence
• Testing & Reasoning

Debugging:

• process of ascertaining why program failing
• function(程序是否按照希望的那样完成了操作) & performance(为什么程序运行的效率低)

Defensive programing:(防卫性程序)

• abet validation & debugging
• 使用断言(assert)来尽早发现程序中的问题,给模块添加注释和说明

Testing:

• examine input/output pairs
• Unit testing:单独测试程序中的每个部分:
  • Functions classes
• integration testing(集成测试):把整个程序组合起来看能否正常运行
  • overall program

在做集成测试之前要对每个单元先做单元测试保证其正确.

Test suite(测试集):

• small enough:保证可以运行完测试集中的数据
• large enough:保证我们对程序有足够的信心

Myth:

1. bugs crawl into programs
2. bugs breed into programs(bug不会繁殖)

Goal: Not to eliminate one bug, is to move towards a bug-free program:不只是要去消除一个bug,而是要让程序中没有bug出现(消除一个bug做的不好,会带入更多的bug).

最好的debug工具:

• print statement
• reading,阅读代码是最重要的debug技能
• be systematic:形成系统化的调试
• reduce search space(缩减问题的空间来定位问题)
  • localize source of problem

如何形成系统化的测试?

• study program text
  • how could it have produced this result(阅读代码并且搞清楚程序为什么会产生这个结果)
  • is it part of family:是不是在整个系统中重复犯了同一个错误,然后一次性修复一系列相同的问题
  • how to fix it?
• scientific method
  • study avaliable data:test results(所有的测试结果),program test
  • form hypothesis
  • design & run repeatable experiment
  • refute hypothesis
  • useful intermediate results
  • expected result(自己对实验的预期结果)

设计一个好的测试:

• find simplest input:找到最简单的输入并且在程序中缩小问题的范围然后定位
• binary search:如果每次能排除掉一半的数据或者代码,定位问题的速度就会很快

Lec12.

调试的一些技巧(习惯):

• 参数的顺序问题
• 拼写
• 初始化变量
• object vs value equality
• aliasing: deep vs shallow copy
• side-effects:副作用
• Keep record of what you tried:记录你做过的操作
• Reconsider assumption:重新思考你的猜测
• Debug code, not comments
• Get help, explain:向别人获取帮助,并且向别人解释你这段程序的作用
• walk away
• haste makes waste:欲速则不达,在修改之前好好考虑清楚修改引起的变化
• code should not always grow:不能依靠增加代码的方式来修复bug
• make sure that you can revert:确保你可以还原你的代码,如果修改失败,最起码可以回到问题的起点重新开始.

optimization problem:(最优化问题)

• a function to maximize(min):最大化或者最小化一个函数
• a set of constraints(一系列的约束条件)

经典的最优化问题:

1. 最短路
2. 旅行商问题(TSP)
3. bin packing(装箱问题)
4. sequence alignment(序列调整)
5. Knapsack(背包问题)
6. problem reduction(问题约束):把新的问题规约到老的问题上,解决它

continuous knapsack(连续背包):->Greedy algorithm:每一步都选择最优的策略,但是局部最优叠加并不一定导致全局的最优

0/1 knapsack(01背包):
最大化的函数:sum(i=1,n)=Pi*Xi
约束条件:sum(i=1,n)=Wi*Xi <= C
对于暴力来说复杂度是指数级增长,不适用于这个问题

dynamic programming:(动态规划)

• overlapping sub-problems(重叠子问题)
• optimal sub-structure(最优子结构)

从求Fibnacci序列来看什么是重叠子问题:fib(0),fib(1),fib(2)…都被重复计算==>重叠子问题

Lec7

Python数组:

解释: L2 = L1 ==> 创建了一个L2和L1进行绑定,事实是L1和L2绑定了同一个对象,所以在通过L1改变了该对象的时候,L2也会发生变化,其实不是L1,L2的变化而是他们共同绑定的对象的变化.
Dictionaries(字典):

• mutable
• not ordered
• generalized indexing

Pseudo code(伪代码):利用伪代码来控制程序流,拆分模块以及搞清对数据的操作

模块性和封装:不需要关心内部的具体实现,只需要调用就可以

efficiency-orders of growth(算法复杂度,运行效率):

• 为什么我们需要考虑效率:因为问题的复杂度的增长速度远比计算机的发展更快
• choice of algorithm:在遇到问题时,能够选择现有的算法并使得解决问题的效率加快
• map problem into class of algorithm:将问题映射到一类算法

Space & Time:

• how much memory to complete
• what is it of basic steps needed as a function of the input size

Random access model:假定我们在读取任意一块内存区域的时候花费的时间是恒定的(理想状态)

• best case -> Min
• worst case -> Max
• expected case -> Avg

Lec8

例子 整数a的b次幂的计算:

Iterative exponent:

1
2
3
4
5
6

def exp1(a,b):    
    ans = 1    
    while (b>0):        
        ans += a        
        b -= 1    
    return ans

总共进行了2+3b步
O(b) -> liner

复杂度增长:

• Asymototic notation
• Big O notation - upper limit to growth

Recursive exponent:

1
2
3
4
5

def exp2(a,b):    
    if b == 1:        
        return a    
    else:        
        return a*exp2(a,b-1)

分析递归式程序的复杂度:

1
2
3
4

t(b) = 3 + t(b-1)     
     = 3 + 3 + t(b-2)     
     = 3*k + t(b-k)     
     Done b-k = 1

==> O(b)

二分:

1
2

a ** b = (a*a) ** (b/2) -> b even       
       = a*(a**(b-1)) -> b odd

1
2
3
4
5
6
7

def exp3(a,b):    
    if b == 1:        
        return a    
    if (b%2)*2 == b:        
        return exp3(a*a, b/2)    
    else:        
        return a*exp3(a,b-1)

==> O(log b)

1
2
3
4
5

b even t(b) = 6+t(b/2)
b odd  t(b) = 6+t(b-1)    
     ==>t(b) = 12 + t(b/2)            
             = 12k + t(b/2**k)        
    k = log2(b)

汉诺塔:

• 经典的递归
• O(2**n) -> 指数爆炸

Lec9

二分查找算法:
思想:

• 1.确定first, last, mid=(first+last)/2
• 2.判断如果mid是要找的值==>找到,否==>小于找左边,大于找右边
• 3.mid=first || mid=last goto 1

缺点: 列表(list)不能用二分查找(效率低,复杂度变成线性复杂度)

Generalize:

1. pick the mind point
2. check to see if this is answer
3. if not, reduce to smaller problem.Repeat

Question:

• should we sort before search? ==>
  liner search n || sort & search nlogn+logn
• can we sort in sub-liner time? - No
• how fast can we sort? — nlogn

Amortize the cost:(平摊花费),如果只搜索一次的话,liner search效率更高,如果搜索多次的话,那么先排序就会体现优势在平摊了排序的花费,而查找的效率是logn.

排序算法

• 选择排序 循环不变量:数组被分成2部分,pre和suff,前部分在排序中是有序的部分,每次只对后部分进行排序到有序为止.
• 冒泡排序

前言

许久未写博客,最近将环境迁移到linux之后在看课程的时候想要记一点笔记,就拾起了Markdown,在尝试了各种的Markdown编辑器都不是很称心之后又想起了自己的博客,就打算着把博客重用起来顺便拿来保存笔记也是个不错的想法,但又想着只用来记笔记有点浪费就想着写一些杂事在上面,正好最近开始了一个Group的讨论,在看完之后又冒出了很多的想法和讨论,就有了这篇杂想.

由一篇博客说起

本文是由对于代码之谜（一）- 有限与无限的讨论所引起的一些想法的记录,在博客中作者提出了一个问题: 负数的绝对值可能等于自己吗? 当然既然作者提出了这个问题,肯定不能轻易的说不或者是了,

我要告诉你方法,而不是答案

在看完之后当然会有一种恍然大悟的感觉,但是所依据的概念和方法又是如此的简单:计算机数的表示,而最小的负数的反码和补码相同这个结论的得出也是自然而然的,但是在没有人提问的情况下,却很难把这二者结合在一起来看.

有限和无限

这篇文章的标题中便提到了这个关键词:有限和无限,作者在文中也抛出了关于在经典数学中的绝对值的定义:

从原点到点A的距离，称为A的绝对值，它是一个非负数

在下面的讨论中,看到了一个能与之对应的关于计算机的绝对值的理解:

其实这整数可以理解成是一个环，取绝对值可以看成把这个环压扁，把其中两面的数都映射到正数的那一面上

很有意思不是吗,我记得在大一的导论课上,我也在书本上看到过类似的图片,一个由数字构成的环,从0开始到8结束又回到了0,当时的图片是为了说明计算机的数字这一个概念,和这个解释如此的一致,我们现在当然可以想当然的说:计算机中的数字是有限的,而数学中的数字是无限的,从而结束这一个讨论,但是为什么从一开始进入计算机的世界的时候,就被人告知,计算机的数字表示是有限的,但是在实际的coding中,我们却自然而然的把计算机的世界和数学世界等同起来.

计算机这个上帝

这个话题是由最近在看的MIT的CS入门课上,教授在讲到关于浮点数的精度的时候提到的,他说:

我们在计算机的世界中创造事物,甚至把计算机(解释器)当成了上帝,想当然的以为他是对的,然后在其之上工作,但是我们不应该仔细想想:为什么他是对的

似乎就像是一场哲学思辨一样,我们似乎也进入了计算机的哲学世界,开始考虑这个上帝,他真的如我们所想一样吗,还是说,我们所想的上帝和真实存在的上帝是不一致的呢?我更倾向于后者,所以这也使我在很多原本自己为的不容置喙的事情上开始了一些思考,我的代码这么写一定是对的吗?为什么是对的呢?我想这就是MIT的教授和这篇博客所要传达给我们的一些理念,仔细想想为什么.在不断的质疑的过程中不断的重塑自己的知识体系和对计算机的认识,似乎就和科学的发展一样,在不断的质疑,提出观点和继续的质疑中才能得到不断的进步.

有限和无限

这当然不是上面的标题的重复(当然也算是),我想来讨论的是计算机所处的有限的世界和数学所代表的无限的世界的不统一之处,当然人类在数学上从有限走向无限也花费了很多的时间,但是计算机作为(可能吧)数学发展比较成熟的时期的产物,却没有获得在抽象层面上的优雅,当然这是因为物理世界的限制,也可能是人类认知上的限制,所以我们似乎也有理由来幻想这样的计算机,像数学一样可以走向无穷和抽象.

(似乎有点扯远)这里讲的有限和无限似乎更像是一种程序员的方法论(或者说计算机观)和现实世界的一种冲突,在讨论中无限和有限也确实有很多可以深究的地方,但是我们确实还做不到用计算机来讨论无穷小,无穷大之类的有很高的抽象层面的东西(我们只能用更高的精度来模拟:exp),所以似乎计算机或是程序员,在用代码也好解释器也好这样有限的东西来对抗物理世界中的无限的数据或者对象,在大数据的今天更甚(似乎在今天已经离不开大数据这个词了,虽然我个人比较抵触,但是这里还是用了一下).我眼前似乎展现了这么一副景象:程序员就如同斯巴达三百勇士一样拿着自己的武器站在温泉关,抵挡着在他们看来无穷的敌人.

无限和有限,似乎是不可调和的一对,但在SICP课程的学习中,却使我在现在有了一些联想:Stream,我们不应该把数据或者对象看成是一块或者是一堆,而应该看成是流,河流,在我们需要的时候,从数据链的一头抽出一个我们需要的数据,另一头就会自动填充:

1
2
3

         -------     -------     --------  
数据---->|  proc|--->|proc  |--->|   proc|---->抽出         
         -------    --------     --------

这似乎是一个很不错的解决方案(看起来).

之所以会写上面的这些文字,是因为在讨论开始的问题的时候,我就发现,无限和有限这一对,不仅会在数字的表示方法这一点上来刁难(或者说折磨)我们,似乎他体现在计算机的方方面面,我们能处理的始终是一个有限的对象,而我们的工具也是有限的,虽然我们无法设想几百年之后的人是怎么编程的,可能就像几千年前的人也无法理解无穷大一样,但是我想的是:在我们使用有限的工具处理有限的问题的时候,我们应该要仔细的思考一下.我们很容易将数学的思维代入计算机,这当然是好的,会帮助我们解决问题,可是似乎也会在某些地方,在那些并不那么和谐统一互相协调的地方,让我们坠入矛盾的深渊.

总结

• 写博客确实是一种锻炼,在行文和构思甚至表达上,总是会感觉词不达意,或者说脑中是思维风暴,但是写出来却是一潭死水,但是练习还是有益处的.
• 就像一开始说的,数学是一条无限延伸的轴,而计算机是一个会头尾相接的环,两者都有其美的地方(现在我很着迷的一点在于fixed point[不动点]).
• 这场讨论和思辨使得我更加审慎的来看待与我相伴的计算机,使我在coding的时候更加多的进行思考.
• 还有一点就是,在看过了足够多的事物之后,发现他们的本质是想通的,CS入门课,SICP,上面提到的文章,这也使得我更深思于计算机的本质:什么是几十年的发展以来没有变的.

呓语到此也完结了.