谈谈开源软件，谈谈质量

2013-10-06

Life

开源软件的基本概念最早可追溯到1955年IBM为了交换编程资料、深入研究IBM操作系统而开发的“IBM用户组分享”。在几十年后，1997年Eric Raymond发表了《大教堂与市集》——开源软件运动的圣经，以大教堂和市集这生动的比喻，阐述了商业封闭软件和自由软件的开发模式，并以Linux和Fetchmail为案例讨论了开源软件的优势。至今，20多年过去了，开源软件取得了不朽的成就，像Linux，Java，Eclipse，Android，Apache，Hadoop，Git，Nginx，Python，Node.js等，都是优秀的开源软件。

开源软件vs自由软件

开源软件

开源软件的定义，是由Bruce Perens(Debian创始人之一)于1997年基于Debian Free Software Guidelines提出，开源软件即公开源代码的软件，允许用户使用，修改，拷贝，合并，出版发行，再散布，贩售软件及软件副本，同时开源软件允许版权持有人在软件协议的规定之下保留一部分权利。

open source describes a broad general type of software license that makes source code available to the general public with relaxed or non-existent copyright restrictions.[more…]

1998年Eric.S.Raymond和Perens成立了OSI(Open Source Initiative), OSI规定开源软件需要遵守OSI支持的许可证，例如Apache License, BSD license, GNU General Public License, GNU Lesser General Public License, MIT License, Eclipse Public License和Mozilla Public License，如果软件源代码本身开源，但是限制用户的修改和再发行等权利，或者程序源码不可读、质量低造成用户难以自由使用，也只能是“Source Available Software”，不是开源软件。

自由软件

相对于开源软件，我们常提到自由软件，大多数开源软件也是自由软件，但二者不能混谈。自由软件, 是1983年由美国麻神理工人工智能实验室研究Richard Stallman提出，并于1984年发起了自由软件运动，建立了自由软件基金会(FSS)，启动了GNU工程。他提出了Copyleft的思想，并为Copyleft提出了GPL许可证，GPL是该运动的精髓。自由软件的定义有FSS在1986年正式提出：
software is free software if people who receive a copy of the software have the following four freedoms.

Freedom 0: The freedom to run the program for any purpose.

Freedom 1: The freedom to study how the program works, and change it to make it do what you wish.

Freedom 2: The freedom to redistribute copies so you can help your neighbor.

Freedom 3: The freedom to improve the program, and release your improvements (and modified versions in general) to the public, so that the whole community benefits.

Freedoms 1 and 3 require source code to be available because studying and modifying software without its source code can range from highly impractical to nearly impossible.

开源软件和自由软件区别

如果硬要区别开源软件和自由软件，可以说二者的出发点不同，用Richard Stallman的话说”Open source is a development methodology; free software is a social movement”.

开源软件出发点是程序本身，旨在通过开源，让更多的人合作开发，Linus定律指出”Given enough eyeballs all bugs are shallow.”,开源致力于提高程序的质量，是一种集市的开发模式.

自由软件可以看做一种哲学和道德观念，强调用户的自由，如果一个软件卖给一个用户的只是二进制代码，而没有源代码，妨碍了用户自由使用、学习的权利，这就是不道德的。Richard Stallman认为软件不应该用来剥削和压榨利润，应该给用户自由的权利。自由软件一定是开源的，自由软件可以看做是开源软件的子集，开源软件中存在一些软件是限制用户再发售软件的权利，这就不是自由的。但大多数软件是自由开源软件FOSS。

The term “open source” software is used by some people to mean more or less the same category as free software. It is not exactly the same class of software: they accept some licenses that we consider too restrictive, and there are free software licenses they have not accepted. However, the differences in extension of the category are small: nearly all free software is open source, and nearly all open source software is free.

—–Free Software Foundation

自由软件常用的许可证是GPL和BSD，现在的更多的FOSS接受MIT或者BSD的许可证，而不太接受自由软件协议GPL，因为在GPL下，再次开发的软件必须是GPL的，不能作为商业用途，代码的传染性太高，也算是一种对自由的限制。

开源软件的优势

1.较低的维护成本，快速的Bug修复

正如Linus定律所述: “如果有足够多的眼睛，所有的错误都是浅显的。”更多的开发者，则可以更快的修复Bug。程序员如果找到Bug，不比像商业软件中那样，先上报、再审批、再决定Bug修复方法，再修复，效率较低，而开源社区的程序员们则可以快速响应修复问题。并且，开源软件的开发者们都是自主自愿的做贡献，软件的维护成本基本为零。

2. 自由和透明性

开源软件让开发者可以自由地使用和学习源代码，可以按自己的需求修改源代码，可以学习别人的代码，提高自己的技能。同时也可以了解软件的运作机制，修复bug，为开源软件做出贡献，提高自己在科技界的知名度。这是开发者的快乐所在。

3. 为公司打开市场

IBM公司在开源软件Eclipse上投入上亿美元，开发了这个高质量的Java IDE，打败了竞争对手，推广了自己的产品，赢得了市场；Joyent公司发布开源的Node.js, 一个基于Chrome V8引擎的开发web应用的开发平台，曾一度成为GitHub上的Top Star，并受MicroSoft, Linkedln，eBay等大公司的亲睐，相信Joyent这家云服务提供商也拓宽了自己的市场。在软件有了市场后，便可以通过对软件的互补物品，如技术支持，存储空间，广告等方面获得利润。

4. 吸引更多优秀的工程师

一个公司进行一个开源项目，可以吸引到更多的人才。很多工程师，喜欢为开源社区工作，提高自己在科技界的声望，帮助他们找到更好的工作。而如果有公司支持开源项目，他们也乐意去那里工作。

开源软件的质量不太理想

开源软件承诺并鼓励开发更高质量，更高可靠性，更加灵活，更低成本的软件，让用户得到更多的自由，而我们也看到像Linux，GNU Project, Apache Project, Python, Chromium, Mozilla, Android都是高质量的开源软件，然而开源软件并不保证一定高质量，在ohloh(开源和自由软件的在线字典)上的60多万的开源软件的质量没有那么理想，高质量的开源软件是榜样，但不能把开源和高质量等同。
Robert在《软件工程的事实与谬误中》给出了质量的定义，即7个属性的集合：可靠性，可移植性，效率，可用性（人类工程学），可测试性，易理解性和可修改性。
开源软件在质量方面的劣势如下：

1. 可用性不理想

商业软件，如Windows，Adobe Photoshop，Office，Dropbox，Skype，iTune等，都有对应的开源软件，如Ubuntu，GIMP，Open Office，Cabos，CuteCom，Songbird，同时也是免费的。开源软件的开发者们缺乏在可用性，HCI方面的设计经验，常常会去模仿工业界的商用软件的设计，缺乏自主创新，这也就解释了几乎每一个商业软件的都有一个开源软件与之对应。模仿的结果是可用性和用户满意度不高，对于不懂技术的普通用户，如果经济允许，购买商用软件会比用开源带来更多的方便。

2. “早发布，常发布”造成缺乏成熟的设计

开源社区，有优秀的程序员，但少有优秀的设计师。开源软件让开发者合作开发，其本质是大量的开发者为软件免费修复bug。开源软件还没有设计好，就草率的发布，势必会降低软件的质量，软件最终会失控。而很多时候，软件设计的重要性等同甚至大于代码的重要性，如HCI设计，需要专业的设计师。而开发者们都喜欢去实现算法，编写代码，在可用性上只按自己的喜好进行设计，造成在细节方面做得不如商业软件。

3. 文档质量不高

很多时候拿到一份源代码，看文档比看源码更有效率，文档是交流的利器。然而，开源软件的文档质量并没有商业软件那么理想。商业软件有好的技术文档和用户手册，但开源软件的开发者宁可写代码，也不太喜欢写文档。我曾经参与过Joomla项目，Joomla的文档就让人很头疼。

4. 软件变得越来越复杂而难以控制

太多的人参与，太多的意见，开发者们按自己的需求，自己对”好软件”的定义开发，让软件越来越复杂，集成和版本控制的成本增加，这些都源于对用户需求没有一个清晰的定义，不满足用户的需求，或者过多冗余的功能，会造成软件的质量下降。

5. 开发人员管理困难

好的软件往往需要一个或多个优秀的开发者全职在一起工作，一起开发、维护和改善软件。当开发者遍布世界各地，便很难保证开发者会全职为软件做贡献。而很多优秀的开源软件是大公司支持的，软件的贡献者同时也是公司的全职员工，这也是这些开源软件可以高质量的一个原因。

开源软件和商业软件之间的平衡

软件开发没有能带来数量级增长的银弹，开源和商业软件各有优势，如何选择是需要仔细考虑的。

1. 根据用户的需求来决定用开源软件或者商业软件

开源软件，开放源代码，开发者对此更感兴趣，如果应用是面向开发者的软件，对可用性和HCI要求不高，如编程语言（Python），服务器，IDE，平台软件，可以考虑用开源软件，让大量的开发者合作开发，可以提高软件的质量。

如果用户是不关心技术的普通用户，且如果有对软件保密性、安全性、高可靠性等方面的需求，采用商业软件的开发方法更好，例如金融理财软件，邮件系统，铁路系统等。
如果用户对软件的交付日期有要求，不要用开源软件，开源很难控制开发进度。

2. 如果采用开源软件，当心GPL

很多开源软件受GPL的保护，而如果你需要二次开发的开源软件，在GPL下，则你开发的软件也必须在GPL下，这会损害你的专利权利，并且软件不能出售。

3. 考虑个人的需求和公司的需求

如果对于开发者个人，需要提高自己在软件界的声望，想锻炼自己的能力，让CV更加好看，多参与和贡献开源软件是一个好方法。

如果一个公司，想扩大自己的市场影响力，想以开源软件的方法获得商业利益，则可以采用开源软件。

但如果个人或者公司想创新，实现创新的idea，并保有自己的专利权利，打算以出售软件来赚钱，那么就要采用商业软件的开发方法。

总之，有了开源软件，我们就多了一种软件的开发方法，开源软件为软件的世界带来了很多生机，像GitHub现在全球最大的开源社区，每天都有世界各地的开发者合作交流。商业软件还是开源软件，我们都要从自己的需求出发来决定。

一些参考资源

When Free Software Isn’t (Practically) Better

Why free software has poor usability, and how to improve it

The Problems of Open Source

Corporate Open Source Considerations

Open Source Sucks

Open Source Rocks

The Top 50 Proprietary Programs that Drive You Crazy — and Their Open Source Alternatives

Open Source Software: The Hidden Cost of Free

统计学的基本概念和方法

2013-10-03

Life

如果这本书读完《统计学的基本概念和方法》，一本价值500页的书，最后给忘记了，我会为我这几天的功夫感到遗憾，姑且高兴高兴把报告亮出来。谈谈感想。

前言

“统计学是用以收集数据、分析数据和由数据得出结论的一组概念、原则和方法。” 这是埃维森在本书中给统计学下的定义。而在读完本书后，我觉得统计学不仅仅是那些曾经学习的数学定义和公式，本书用大量的例子有趣地说明了统计就在生活中，如政府部门的政策和评估、人口调查、医学、心理学、和法学等等领域，统计学都有重要的角色。而如何正确的收集数据，如何选择合适统计分析方法，以及如何用怀疑的眼光来看待一些社会生活中的统计结论，不盲从以及冷静的分析，是我觉得本书给我的一大益处。

总的来说，统计学可以说是在各种随机的数据中寻找寻找规律性的方法。统计学家所做的许多工作都是为了回答四个问题：

问题1：在数据中，变量之间是否有关系？

问题2：变量之间的关系有多强？

问题3：总体中是否存在该关系？

问题4：观测到的关系是一种因果关系吗？[more…]

纵观本书，为了回答这四个问题，首先要定义需要观测的变量并收集数据；对数据进行整理，用圆饼图、条形图、点图或直方图等，形象地对数据做出表示；计算汇总统计量，如均值，方差，标准差等；从原始数据做出初步猜测，所观测的变量之间是否有关系；为了验证猜想，运用公式，计算变量之间的相关系数，如对于数量型变量的分析，还需计算出线性回归公式；接着，对总体中是否存在该关系做出假设，如零假设是总体中不存在这些关系，再运用假设检验的方法拒绝零假设，即统计上显著，从而可以将样本的结论推广到总体，假设检验中会用到z，t，χ2, F分布；最后，对于因果关系，这是很难回答的，统计上相关未必有因果关系，这需要综合考虑多方面的因素才能下结论，然而否定因果关系是容易的，可以通过引入第三方变量造成变量中的关系消失来否定因果关系。

数据的收集

统计结果是基于：数据的收集和统计方法的运用。

而正确的进行数据收集是对后期得出正确的统计结论的重要保障。而实践中我们由于成本、社会道德等原因，很难进行全部总体的普查，一般是进行抽样，这样可以节约成本，加快数据收集过程，提高效率并减少偏差。一个合适的能够被用来推广到总体的统计样本叫随机样本。首先我们要定义清楚总体是什么，即采样的种群，是所有成年人或者某公司所有员工；其次我们要选择正确的采样方法的保证采样的随机性，如概率采样，分层采样和聚类采样；最后，我们要决定采样规模，样本数越大，抽样误差越小。例如调查总体中样本的百分比，往往要求误差在3%以内，那么需要至少1200个响应者。

实际中，采样会遇到很多问题，对人的研究比研究土豆难得多，例如组织问题，心里问题，道德问题和成本问题等，都应在进行数据抽样前多加考虑。

数据描述

在得到采样数据后，我们一般会采用表的形式来记录数据，而为了展现统计结果，图是分析数据的一种极富有信息的方法，直观易于理解。

分类变量

一般采用圆饼图和条形图来展现。当类别不是很多时，圆饼图表达更易于表达出每一个类别的相对大小。但是圆饼图用于显示每一组有多少个观测数时不是很好。

而条形图，优势在于可以显示每一个组的观测数，可以有相同高度不同宽度的条形图，也可以选择不同高度和相同宽度的条形图。

度量变量

度量变量一般用点线图，茎叶图，盒形图，直方图，散点图和时间序列图来展现。

点线图：在一条连续的线上表明一个小的数据阵，原始值得以保留，适合展现小规模数据的分布和变化。盒形图：对数据进行了简化，取5个值，最大值，最小值，中位数，25%和75%分位数来构成。表明了两个极值和中间值的范围，在分析若干组数据时很有用。但无法恢复原始数据。直方图：用矩形的面积表示变量值的观测和相对数量，可用于显示大量的观测数据，但是无法保持原始值。茎叶图：适合展现小数据集，但不适合展现数据变化范围小的数据。散点图：可以用于表现变量之间的关系，在回归分析中常用到，表现了数据的分布和变化。时间序列图：在横轴上均匀的显示时间，纵轴上是变量的值，可以展现多个变量的数据。

地图作图

根据数据，按区域在地图上染色，标识数据，如人口分布等。但地图可能会误导，地图上面积小，但是人口密度大，但面积和人口密度不成正比。

如何选择正确的图呢？Edward Tufte定义了图优性：图要能够在最短的时间内用最少的笔墨，在最小的空间里给观众最多的思想。在统计图选择中，我们面临两个矛盾：数据的简化和数据的完整，我们需要在简单化受益和信息的丢失之间权衡。

分析统计量

平均数

数据的统计量计算需要正确的方法。平均数包括众数，中位数和均值。众数适用于分类变量，特别是有多个值的分类变量，如宗教、种族的划分。中位数：一组数据中的中间值，不受极值的影响，当数据出现非对称分布时应该用中位数，例如收入、房子价格。但中位数只是中间点的数据，但没有充分利用数据。均值：在对总体进行点估计时常用均值，均值可以充分地利用观测数据，但均值容易受极值的影响。如果均值和中位数差不多，采用均值，但如果非常不同，采用中为数据，对于非对称数据，采用中位数更好。
变差

极差：很容易受极端值的影响，为了避免这种影响，我们可以采用四分位数极差。

标准差：度量数据在平均意义上和均值的偏离。
标准误差：多个样本均值的标准差，一般比某一组观察值的标准差小。
标准得分=(观察值 - 均值) / 标准差，可以对不同的观察值进行比较。

重要的概率分布

统计的样本一般假定是随机样本，对于随机样本的分析，需要计算概率，概率可以从等可能事件，相对频数和主观概率中得到。而了解概率的分布是在进行参数假设检验等分析中重要的一步。

离散型变量的概率分布

主要有几何分布和二项分布，主要在分类变量且样本数量很少时才很方便。对有很少的样本而可能性很多的分析，可以采用Poisson分布。

连续型变量的概率分布

主要有z（标准正太分布），t，χ2, F分布。标准正态分布是一个钟形曲线，均值=0，标准差=1，曲线下面有95%的面积在-1.96~1.96之间。一般假设检验和参数估计中会计算出标准的z值再查表得到概率。t分布，又叫学生分布，和正态分布很像，是最常用的统计分布，t分布的前提是总体要符合正态分布，根据自由度选择t分布。χ2, F分布都是有偏的，取值从0开始，按自由度选择。

p值：即极端概率发生的概率，p值在说明统计显著方面很重要。

统计推断：估计和假设检验

对样本的分析最终需要做出一个关于总体的估计。

点估计

在估计总体均值时一般采用样本均值而不是中位数或众数来估计。

区间估计

只给出一个点是不够准确的，总要说明误差范围。在来自不同样本的多个置信区间当中包含未知总体参数的区间所占的百分比称为置信水平。我们一般采用95%的置信区间，意思不是该区间中包含真值的概率，而是多次抽样中有95%的置信区间包含未知总体参数的值。可以通过增加样本容量或降低置信水平来获得较短的置信区间。一般对于1200个响应者，抽样误差可控在-3%~3%，且置信水平是95%.

统计显著

显著是在本书开端就提出的问题，统计显著是对参数假设检验而言的，一个检验的显著水平a是抽样所得的数据拒绝了本来是正确的零假设的概率。p值越小越显著。一般p取0.05，但对于双边检验p=0.025。

假设检验可以进行总体均值的检验（t检验），总体比例检验(z检验)。当然也可以采用计算置信区间的方法，如果零假设中的相关参数值在置信区间，就不拒绝。

变量间的关系

对于从试验和观测中得到的数据，我们最终关心的是变量之间的关系问题。因此统计量的计算，数据的描述，统计推断都在为回答变量之间的关系做铺垫。四个重要的关系问题：问题1：在数据中，变量之间是否有关系？问题2：变量之间的关系有多强？问题3：总体中是否存在该关系？问题4：观测到的关系是一种因果关系吗？

前三个问题，可以通过统计方法得到准确的结论，但是因果关系确很难回答，我们在判断因果关系时：(1) 用常识进行推断. (2) 主意自变量和因变量的发生顺序。(3) 即使自变量发生在因变量之前，但当引入第三个变量，自变量和因变量的关系消失，他们也没有因果关系。然而，统计关系强，确实可以反映可以从多大程度上用自变量去估计因变量。

变量分为三类：分类型变量，顺序型变量和数量型变量，不同的变量，分析方法不同。

1. 两个分类型变量的关系： χ2分析

常用列联表来表示分类型变量。

变量间是否有关系？可以通过观察数据的百分比分布得出。

变量之间的关系强度？通过公式计算相关系数。

总体中是否有这个关系？通过 χ2分析得到p值，进而拒绝零假设。

因果关系？分类变量的统计关系，不能说明因果关系。

2. 两个数值型变量的分析：回归分析和相关分析

回归分析描述的是一个或多个自变量的变化是如何影响因变量的方法。相关分析描述的是两个数值型变量的关系强度。在对数值型变量的回归分析前，需要观察散点图，如果数据很分散，则变量的关系就很弱，同时回归分析时需要抛弃极端值。

回归分析重要参数如下

回归方程y = a + bx， b即回归系数，表示自变量变化1，因变量的变化值。

相关系数r：r^2表示自变量在决定因变量的取值变化效应中所占的比例，其他的变化影响来自残差变量。

总平方和=⨊(观测值 - 平均值)^2 = 残差平方和 + 回归平方和

残差平方和=⨊(估计值 - 观测值)^2

回归平方和 = ⨊(估计值 - 平均值)^2

r^2 = 回归平方和 / 总平方和

回归方程是否能对总体做出估计？需要进行相关分析，置信区间的计算，相关分析中采用t假设检验。

3. 一个数值型变量和一个分类型变量的关系

变量：分类型变量，因变量：数值型变量。例如地区和犯罪率的关系。对于关系强度的计算，需要计算总平方和，残差平方和以及自变量效应的平方和。

总平方和(TSS)=⨊⨊(观测值 - 平均值)^2 = 残差平方和 + 回归平方和

残差平方和(RSS)=⨊⨊(观测值 - 组均值)^2

分类变量平方和(CSS) = ⨊⨊ni(组均值 - 平均值)^2 (ni—每组中的观测值数量)

相关系数R ^ 2 = 回归平方和 / 总平方和

采用F检验进行分析。

在书中，还提到配对数据的差异检验，如分析各个地区犯罪率与年份的关系，配对数据检验采用t检验，有时如果无法确定总体是正态分布，可以采用符号检验，但符号检验采用二项分布，如果数据量大不太合适。

4. 两个顺序型变量的分析：秩方法

顺序型变量很少出现，尽管有些变量如富裕程度，看上去是分类型变量，但是富裕程度有低、中、高的顺序，如果采用分类型变量的χ2分析，数据就不能充分利用。

一般地，当一个数量型变量和一个顺序型变量出现时，都作为顺序型变量来分析，反之不行。

当一个分类型变量和一个顺序型变量进行分析时，都看做分类型变量来分析。

(1) 用词作为两个顺序型变量

例如：学生对数学的掌握程度(一般、中等、较好)与老师上课的有趣程度(一般、中等，较好)的关系，书中给的例子是政党身份的强弱与对总统选举感兴趣的程度的关系。

系数 γ 度量两个取值为词的顺序变量的相关程度。

γ = （相同的次序 - 不同的次序）/ （相同的次序 + 不同的次序）

可以将 γ转化为z值，进行检验，根据p值拒绝零假设。

(2) 用数字作为两个顺序性变量

例如：马刺队和灰熊队2011年和2012年的排名关系，或者一个人的经济地位与人的能力的关系。

采用Spearman rs相关系数来度量两个取值为数量的顺序变量的相关程度。一般将rs转化为t变量进行检验。

5. 多元分析

多元统计分析考虑两个或两个以上的变量对一个因变量的相关的影响。多元分析可以通过引入控制变量，来观察自变量和因变量的关系，如果关系消失，则否定因果关系。

(1) 三个分类型变量

偏Φ，是当控制变量取特定值时，度量自变量和因变量之间的相关程度。可以认为是对每一个控制变量的值，得出的自变量和因变量的相关系数Φ的平均值。例如：控制性别，研究收入和投票的关系。

(2) 多个数值型变量间的关系

采用多元回归分析，计算每一个自变量的偏归系数，构造回归方程。

相关系数R是因变量的实际值和回归方程预测值之间关系的强度。R^2是所有自变量共同解释因变量差异的总和。

一般将R转化为F比，进行假设检验其统计上的显著性。

(3) 因变量是数量型变量，自变量是两个分类型变量.

采用双因子方差分析，由于双因子方差分析可以考虑两个分类变量各自效应之外的交互效应，所以优于单因子方差分析。交互效应，即两个自变量对因变量的联合作用。
交互效应大于每个因变量各自效应的总和。通过研究交互效应和残差效应的F比，可以得出两个分类变量对因变量的统计显著性。

总结

在读完本书后，我觉得这么多统计方法，并没有带来很乐观的统计现状。统计从收集数据到分析得出结论，每一步都可能误用，而大多数误用不是故意的，且有些别有用心的人会对用一些方法对统计结果进行有意的歪曲，统计中需要警惕：

1. 数据收集中的危险，研究者往往会在数据收集的随机性上打折扣，例如研究成年人的购物兴趣，研究者为了方便会选取一些积极性较高的大学生，样本是随机的，但样本的结果只能说明大学生的购买兴趣，统计推断只能把他推广到它产生的总体。

2. 调查的环境，调查的身份，提问的方式，被访者是否在一个舒适和私下的环境下接受采访，也会对数据产生影响。

3. 问题的内容和提问的时机，例如薪水问题如果提问不当，被访者会很反感。

4. 结果的记录方式，如果一个人吸烟的兴趣是4分，两个相同分数的人对分数的理解是不同的。而且大多数研究场合下人们都会对回答有某种程度的夸张。

5. 分析方法的误用，统计推断的误用，例如收入的平均数应该用中位数而不是均值；用最小二乘法计算回归方程，而不是绝对值，双边假设检验的p=0.025，而不是0.05。

6. 数字的错误解释，如Benz公司广告说过去15年来被注册的他们公司的车种97%仍然在使用，其实97%中也包含近几年来注册的新车，消费者总是会被误导。

总之，任何有收集经验数据的场合都需要统计方法，而统计的结果依赖于数据和分析方法。统计很神奇，可以从混乱与随机中找到规律，而我们要做地是不被规律所误导，不盲从详细各种社会统计，官方统计，要拥有一双怀疑的眼睛。

找一个数组中第2小的元素

2013-09-12

Algorithm

找出一个数组中的最小元素或者最大元素，遍历是最优解,即O(n)，我想这是会编程的人都会的简单算法。而如何找出第二小的元素呢，先排序，然后再选么，这样的算法最优也是O(n * lg n)，还是一次遍历来的更快，思想如下：

假定数组A有n个元素,元素可以有重复：

1. 初始化一个数组res[2]，变量i, i为遍历时使用。

2. 当n为奇数时, res[0] = A[0], res[1] = A[1], i = 1;

3. 当n为偶数时, res[0] = min {A[0], A[1]}, res[1] = max{A[0], A[1]}, i = 2;

4. 接下来每次取数组A中的两个元素，较小的元素如果小于res[0]比较，则res[1] = res[0], 再赋值 res[0] = small；

5. 如果res[0] == res[1]或者较大的元素小于res[1], 则res[1] = large;[more…]

以上算法可以O(3n/2 - 2)时间，即O(n)的时间内选出第二小的元素。

Github Source Code
[java]
public int selectSecondSmallest() {
int[] res = new int[2];
int n = data.length;
int i = 2;
if (n % 2 == 0) {
i = 2;
if (data[0] < data[1]) {
res[0] = data[0];
res[1] = data[1];
} else {
res[0] = data[1];
res[1] = data[0];
}
} else {
i = 1;
res[0] = data[0];
res[1] = data[1];
}
for ( ;i < n; i += 2) {
int large = getLarge(data[i], data[i + 1]);
int small = getSmall(data[i], data[i + 1]);
if (small < res[0]) {
res[1] = res[0]; // Maybe res[0] is the second minimum, don’t forget the tiny step
res[0] = small;
} else if (small < res[1]) {
res[1] = small;
continue;
}
if (large < res[1] || res[0] == res[1]) {
res[1] = large;
}
}
System.out.println("The smallest is " + res[0]);
System.out.println("The second minimun is " + res[1]);
return res[1];
}
[/java]

后记

这个算法很简单，但是算法导论的答案给的太复杂了，用了树的算法，这么诡异而复杂，算是领教了。这个算法可以扩展到找第i个小的元素。

Warshall's Algorithm for Cycle Dectection

2013-09-09

Algorithm

今天上系统分析与设计课，老师提到了Warshall算法做函数调用关系的Cycle Detection, 想起当年的离散，这一章还真没有什么印象了。翻开陈年旧书看看，就跟看见陌生人一样，基础还是需要在加强一下啦。今天上课提到的几个点，比如死锁，Dijkstra Algorithm，DFS，Unix多级反馈调度，Android卡顿缘由等，自己没能第一时间想出来，就留作以后闲暇时光google的题目吧。现在花了一个小时，用Java把Warshall算法实现了，总觉得用一个小时是不是有点长了。

Warshall算法要义：

邻接矩阵: 表示图关系的矩阵，看看离散数学就懂了
传递闭包：从邻接矩阵的每一个顶点出发，求出的所有顶点的到达情况，该矩阵就是传递闭包。说是闭包是因为它满足自反性、对称性和传递性。
Warshall算法就是从邻接矩阵中求出传递闭包。[more…]

例如:

邻接矩阵为：

[0, 1, 0, 0,

1, 0, 1, 0,

0, 0, 0, 1,

0, 0, 0, 0]

传递闭包为：

[1, 1, 1, 1

1, 1, 1, 1,

0, 0, 0, 1,

0, 0, 0, 0]

算法很简单，直接上一个代码描述：
[java]
public void warshallDetect(int[] matrix) {
closure = matrix;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (closure[i, k] == 1 && closure[k, j] == 1) {
```
 closure[i, j] = 1
```
}
}
}
}
}
[/java]
程序的意思是：
M(0): 初始矩阵，从每一点到另一个点不能有中间节点，即最初的矩阵。

M(1): 在M(0)基础上，从每一个顶点出发，让第1个顶点作为中间节点，检测是否有关系。

M(2): 在M(1)基础上，从每一个顶点出发，让第2个顶点作为中间节点，检测是否有关系。

M(k): 在M(k-1)基础上，从每一个顶点出发，让第k个顶点作为中间节点，检测是否有关系。

M(n): 在M(n - 1)基础上，从每一个顶点出发，让第n个顶点作为中间节点，检测是否有关系。

最终生成一个传递闭包，检测哪些顶点有循环调用就显而易见了。

源代码在此。

参考博客

计数排序的应用

2013-08-18

Algorithm

比较排序是我们常见的排序方法，如Insertion Sort, Merge Sort, Quick Sort, Heap Sort都有O(n*lgn)的下界，而如何让一个排序能在最短的线性时间O(n)内排序呢？就要求助于Counting Sort计数排序，该算法的基本思想是对数组中出现的数字进行计数，通过计数计算出每一个数字的排位，并按排位给出结果。计数排序明显的在时间上优于快排，以空间换时间，这个排序思想很像在编程珠玑的开篇中提到的按位排序，计数排序还有个好处是稳定的。

计数排序的应用主要是基数排序(Radix Sort),但是我试过排序一百万个数字，基数排序的时间虽然是O(n),但可能是常系数的因子太大，执行时间并不比快排理想，只能算是为了学习嘛，试验一下了。

虽然计数排序看着很快，万物都有利有弊，计数排序有一个前提，需要知道输入数据的分布，即最大值和最小值，如果不知道的话，还是快排最好。而基数排序则更适用于输入的数据位数都相同。

对于计数排序，其代码如下：[more…]
[java]
public void sort() {
count = new int[k + 1];
results = new int[data.length];
int i;
for (i = 0; i < count.length; i++) {
count[i] = 0;
}
// 对数组进行计数
for (i = 0; i < data.length; i++) {
count[data[i]]++;
}
// 计算每一个数字的排名
for (i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 按排名输出到结果数组中
for (i = data.length - 1; i >= 0; i–) {
results[count[data[i]] - 1] = data[i];
count[data[i]]–;
}
}
[/java]

计数排序的应用一

算法导论思考题8-3-a

给定一个整数数组，其中不同的整数中包含的数字个数可能不同，但该数组中，所有整数中的总的数字数为n。说明如何在O(n)的时间内对该数组排序。

分析：该数组的每个数字的位数不相同，直接用radix sort不好，需要做一些改进。其方法是用counting sort，按整数的位数给整数排序，再对相同位数的一段整数用基数排序，算法时间O(n)。

Source Code

计数排序的应用二

算法导论思考题8-3-b

给定一个字符串数组，其中不同的串包含的字符数可能不同，但所有的串中总的字符个数为n。说明如何在O(n)的时间内对该数组进行排序

分析：该问题的难度出现在字符串上，字符串的排序不像数字，位数多的比位数少的大，字符串的排序需要按字典顺序来。这个算法的基本思想是先对所有的字符串按首字母进行Counting Sort, 然后再递归地对相同首字母的字符串的第二个字符进行Counting Sort，以此类推，递归排序第三，第四…个字符。

算法的边界问题容易出错，debug花了我两个小时，不过能编出来实属不易。

Source Code