1、空间换时间法则 这个东西，稍微有点程序经验的人应该都接触过，比如在设计数据时候冗余了部分数据，避免关联表查询，减少开销，实际上也减少了查询时间，所谓空间换时间。还比如，我们将一个有点开销的计算结果存储起来，避免下次再次运算，减少时间消耗，再如，CPU的设计，设置了高速缓存，一级缓存，二级缓存，主存（通常所说的内存），其实一个硬盘和一个CPU也可以干活，只是干得不怎么样，因为硬盘和CPU之间速度实在是差别太大了，如是就有人想把可能要用到的数据预先加载到高速缓存或者主存中，慢慢形成了今天的个人计算机架构。 2、以时间换空间法则 这个其实也是天天在用的一个法则，只是一般技术人员看到“压缩”二字的时候，没联想到那么多，压缩就是最典型的拿时间换空间的例子，就是不断的重复前面已经存储过的存储地址，用来避免存取真实的数据。 3、循环法则 大部分稍微有点经验的人不会在同一个函数中循环两次同样的变量，但是仅限于同一个函数，假如在一个函数里调用了另外一个函数，那么就不一定了，很多人为了看似解耦的一个操作，在两个函数对同一个变量做了多次的循环。循环法则有几个比较经典细则： 第一、将代码移除循环，这是最容易想到的，当然，可以移除的条件是，每次循环都执行同样的某次操作。 第二、合并测试条件，高效的内循环应该包含尽量少的测试条件，最好只有一个，因此，程序员尽量用一些退出条件来模拟循环的其他退出条件。 第三、哨兵法则，在数据结构边界上放一个哨兵以减少测试是否已经搜索结束的开销。 第四、展开循环，展开循环可以减少修改循环下标的开销，对于避免管道延迟，减少分支以及增加指令级的并行性也有很大帮助。 第五、删除赋值，赋值的开销实际上在整个程序的执行过程中占的开销可以忽略不计，但假如你要在一个循环十万次的循环中赋值，那么开销就不能不计了，尽可能的在循环中减少赋值吧。 第六，消除无条件分支，快速的循环中不应该包含无条件分支，通过旋转循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支。 第七、循环合并，如果你不小心做了傻事，那么合并两个对同一个变量循环操作吧 4、逻辑法则 利用等价的代数表达式。如果逻辑表达式的求值开销太大就将其替换为开销较小的等价代数表达式。 短路单调函数。如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值，那么一旦达到这个阈值就不在需要计算任何变量了。 对测试机条件重新排序。在组织逻辑测试的时候，应该是降低开销的，经常成功的测试放在高开销的，很少成功的测试前面。 5、过程法则 打破函数层次。对于（非递归地）调用自身的函数，通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间。 并行性。在底层硬件条件下，我们构建的程序应该尽可能多的挖掘并行性。 6、表达式法则 编译时初始化。在程序执行前，应该尽可能多的变量初始化。 利用等价的代数表达式。如果表达式的求值开销过大，就将其替换为开销更小的等价的代数表达式，比如换一种算法 消除公共子表达式。如果两次对同一个表达式求值，其所有变量都没有任何改动，那么我们可以用下面方法避免二次求值：存储第一次的计算结果并用其取代第二次求值。
UDP hole punching 翻译
3.3. UDP hole punching UDP打洞技术 The third technique, and the one of primary interest in this document, is widely known as “UDP Hole Punching.” UDP hole punching relies on the properties of common firewalls and cone NATs to allow appropriately designed peer-to-peer applications to “punch holes” through the middlebox and establish direct connectivity with each other, [...]
N-Gram学习笔记
统计语言模型 假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)： 这个概率的计算量太大，解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1)，等价类的数目远远小于不同历史的数目，即假定： N-Gram模型 当两个历史的最近的N-1个词（或字）相同时，映射两个历史到同一个等价类，在此情况下的模型称之为N-Gram模型。 N-Gram模型被称为一阶马尔科夫链。 N的值不能太大，否则计算仍然太大。 根据最大似然估计，语言模型的参数： 其中，C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数 平滑技术的引入 传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求： N>>K 其中K为随机变量能够取到的值的个数。 实际语言模型中往往无法满足这个要求。 例如：词性标注问题，共有140个可能的标记，考虑当前词前后两个词的影响的三阶模型。 K=140*140*140=2,744,000 给定一个10万词左右的人工标注训练集，即 N=100,00，可见训练数据显得非常不足。 假设k泛指某一事件，N(k)表示事件k观察到的频数，极大似然法使用相对频数作为对事件k的概率估计： p(k)=N(k)/N 在语言模型中，训练语料中大量的事件N(k)=0，这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。 这种零值的概率估计会导致语言模型算法的失败，例如：概率值作为乘数会使结果为0，而且不能做log运算。 计数等价类 根据对称性原理，事件除了出现次数之外不应具有细节特征，即所有具有相同计数r=N(k)的事件k（事件出现的次数称为事件的计数）应当具有相同的概率估计值，这些计数相同的事件称为计数等价，将它们组成的一个等价类记为计数等价类Gr。 对于计数为r的计数等价类，定义nr为等价类中成员的个数，pr为等价类中事件的概率，R是最大可能出现的计数次数，则 交叉检验 交叉检验就是把训练样本分为m份，其中一份作为保留部分，其余m-1份作为训练部分。训练部分作为训练集估计概率pr，保留部分作为测试集进行测试。 我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计，即使对数似然函数最大化： 使用拉格朗日乘子解决约束条件下的最大值问题，即： 对pr求偏导，得到交叉检验估计： 如果测试部分也作为保留部分的话，就是典型的极大似然估计： 留一估计 留一方法是交叉检验方法的扩展，基本思想是将给定N个样本分为N-1个样本作为训练部分，另外一个样本作为保留部分。这个过程持续N次，使每个样本都被用作过保留样本。 优点：充分利用了给定样本，对于N中的每个观察，留一法都模拟了一遍没有被观察到的情形。 对于留一方法，pr的极大似然估计为： Turing-Good公式 因为nRpR与1相比一般可以忽略，留一估计公式可以近似为： 留一估计可以利用计数r=1的事件来模拟未现事件，对于未现事件有如下估计： 这个公式就是著名的Turing-Good公式。 空等价类 留一估计中要求么个nr均不为0，在实际问题中当r=5时，这个要求通常都不能满足，即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序： 对应的出现r(l)次的事件的个数记为nr(l)，在进行留一估计时，使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1，留一估计公式变为： 式中对空的等价类没有估计概率，因为空等价类并没有对应任何有效事件。 Turing-Good估计的优缺点和适用范围 缺点：( 1 )无法保证概率估计的“有序性”，即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似，好的估计应当保证pr<=r/N。 优点：其它平滑技术的基础。 适用范围：对0<r<6的小计数事件进行估计。 约束留一估计 单调性约束：pr-1<=pr；折扣约束：p<=r/N。 约束留一估计：让计数估计r*=pr•N处于距其最近的绝对频数之间： 在这个约束下，单调性约束自然满足。 计算方法：计算m时检查每个pr是否满足约束，不然就用约束的上下界进行裁剪，然后重新计算m，一直迭代下去直到所有pr满足约束。 折扣模型 [...]
代码格式规范的List
《代码大全》是本好书啊，推荐所有有志于改善自己的程序，或者在编码上寻找进一步提高的人应该仔细研究研究。以下是摘抄自《代码大全》第二版中谈到关于怎样的代码格式更适合人类阅读，更能令人愉悦的Check List。对照List进行自检和反省，令人欣慰的是List中80%以上我都做到了，在我的上一个项目中做得比较失败，由于时间的原因，很多注释没有加上，逻辑也不够清晰。在重构中解决，借此反省。 一般问题： 格式化主要是为了展现代码的逻辑结构吗？ 2、你的布局方案能统一运行吗？ 3、 你的布局方案能让代码易于维护吗？ 4、你的布局方案是否有利于代码的可读性？ 控制结构的布局 1、你的代码中避免begin-end 或对｛｝的双重缩进了吗？ 2、相邻的块之间用空行分割了吗？ 3、对复杂表达式格式化时考虑到可读性吗？ 4、对只有一条语句的块布局始终如一吗？ 5、case语句与其他控制结构的格式化保持一致了吗？ 6、对goto语句格式化是否让其显眼了呢？ 还好目前PHP只有5.3以上版本才会有goto 单条语句的布局： 1、为逻辑表达式、数组下标和子程序参数的可读性使用了空格了吗？ 2、不完整的语句在行末似乎以明显又错的方式结束吗？ 3、后续行按照标准数码缩进了吗？ 4、每行顶多只有一条语句吗？ 这一点是团队中比较头痛的问题，很多人不按照这个规则来做，结果它成了一种风气 5、所写的每个语句都没有副作用吗？ 6、每行顶多只声明一个数据吗？ 注释布局： 1、注释与其所注释的代码所尽量相同吗？ 2、注释风格便于维护吗？ 子程序的布局： 1、你对每个子程序的参数格式化方式便于看懂、修改、注释吗？ 2、采用空行分割子程序各部分了吗？ 4、文件中子程序用空行清楚分开了吗？ 5、在没有更好的组织形式的场合，所有子程序都按字母排列了吗？ 这一点我没有做到，没有做到是没有想到这一点，以后编码注意了……
程序语言评估标准
1、可读性。判断一个语言的优劣的一个最重要的标准是用它写的程序要好读，好懂。 一种语言的整体简单性极大的影响着他的可读性。一种具有大量基本结构的语言较只有少量基本结构的语言要难学得多，当然，过少也会非常难学，汇编就是如此。 2、正交性。正交性是指使用该语言中一组相对少量的基本结构，经过相对少的组合步骤，可以构成该语言的控制结构与数据接哦股。而且，它的基本结构的任何组合都是合法和有意义的。 3、控制语句。在20世纪50年代和60年代，一批程序设计语言由于缺乏控制语句，导致很差的可读性。随后的语言都兴起了结构化程序设计的革命。尤其是人们普遍意识到滥用goto会降低程序设计的可读性。 4、数据类型和数据结构。在程序设计语言中给出定义数据类型和数据结构的合理机制，是语言可读性的又一个重要辅助。 5、可写性。可写性是程序设计语言的在应用领域产生程序的难以程度的一种度量。大多数影响可读性的语言特征可以影响可写性。 6、支持抽象。抽象指的是以合法的省略许多细节的方式，来定义并且使用复杂结构或复杂运算的能力。 7、表达性。语言的表达性可以指语言中几种不同特征。一种是具有一些功能很强的运算符。一种是程序语言具有相对方便，非繁琐的方式来说明运算。 8、可靠性。如果一个程序在任何条件下的运行都能 达到他的说明标准。我们称这饿程序是可靠的。 9.代价。第一是训练程序员使用这种语言的代价。第二是使用这种语言来编写程序的代价。第三是编译程序的代价。第四是程序运行的代价。