如何编写高质量的程序

学习任何编程语言都会有一个基本的过程，开始的时候学习基本的语法，然后学习各种库，框架，开始做各种项目。在做项目的过程中，随着代码量的增加，我们会渐渐感到失去对程序的掌控能力，bug开始增加，牵一发而动全身，顾此失彼。这充分说明了编写高质量程序的重要性，这里的“高质量”主要指程序的正确性，可读性，可维护性。

什么是高质量的程序

正确性

程序正确性的重要程度无需多言，尤其在一些特殊领域，例如芯片制造业，航天业，武器制造业，对程序正确性往往有着极其严格的要求，因为一旦程序出错，代价往往是巨大的。在这些领域，需要使用形式化方法(formal methods)来自动验证程序的正确性，也就是说你需要证明程序的正确性，而不仅仅保证程序在大多数情况下是正确的。在其它领域，对正确性没有这么高要求，形式化方法也不适用，但是我们还是需要使用其它手段，例如测试，code review等等来保证软件的正确性。

可读性

可读性可以帮助程序作者理清思路，思路清晰后，程序不容易出错。另外，其它程序员在维护你的代码时，更容易理解你的意思，方便修改bug，方便扩展。

不要浪费自己的时间，更不要浪费别人的时间。

可维护性

这里的可维护性主要指程序应对变化的能力。程序在完成基本功能后，可能会发生各种改变：用户需求变了，性能达不到要求需要重新实现算法，等等。一旦程序的一个点发生改变，其它点如果也需要同时手动改变，那么程序会变的不可控制，出bug的机会会增加。想像一下，我们的程序是一个盒子，在添加新功能时，如果只需要把新模块插到一个地方，新模块就可以被系统使用，这样的程序可维护性是很高的。但是如果添加新功能时，需要把原来的程序盒子拆开，其它模块也需要相应修改，才能加入新模块，这样的程序可维护性就很差。

Read More ...

为什么我们需要数据结构

---

最近在学习各种数据结构，于是就在想，为什么我们需要数据结构呢？ 为什么要设计这么多数据结构？数据结构到底解决了我们什么样的问题？

我们提到 数据结构 时，一般是指计算机科学中的一个概念， 但是从本质上讲，数据结构应该是指对数据的一种组织方式。既然如此，我们没必要非在计算机科学领域中讨论 概念本身，把它放在其它领域中，可能更能加强我们的理解。

就说图书管吧，假如你是一名很久很久以前的图书馆管理员，那时候根本没什么计算机。数据结构？那是什么？

你的任务就是看着图书馆里的一堆书。于是，有一天，图书馆来了一堆书，你把他们堆成一堆，放在馆里。 这时候，有人来借书了，他只能在那一堆书里乱翻，翻来翻去也找不到自己想要的书，因为那是一堆书， 有的书他检查了很多次，有的一次也没检查。

这时候这堆书是一个集合，不方便遍历。

时间长了，抱怨的人很多。

作为一个怕麻烦的管理员，你忍受不了别人的抱怨，于是，你把那 一堆书 变成了 一排书。

这下好了，来找书的人，只要从书架左边走到右边，按顺序找就好了。只要书在图书馆里，慢慢找总是可以找到。 但是，随着图书馆的书越来越多，这样找实在是太慢了，因为每次都要从第一本书找到最后一本书。

这时候这堆书是一个列表，方便遍历，但是不方便查找。

时间长了，抱怨的人很多。

作为一个怕麻烦的管理员，你忍受不了别人的抱怨，于是，你把那 一排书 变成了 很多类书。

那么，按什么分类呢？按书的大小么？颜色么？退一步讲，分类的依据是什么？

分类是为了加快读者查找书的速度，那么读者查找书的时候，是按什么查找呢？是按书名。所以，我们对书名分类。 按书名分类也有许多种，按书名读音么？按书名笔画吗？按书名字数么？我们很容易想到，按读音分类给读者的压力最小， 也就是查找前的开销最小。否则每次找书之前还要数一下笔画，读者一定又会抱怨。

这时候，我们按读音把书分类，书名第一个字是A的在A书架，是B的在B书架。这下读者查找书的速度大大加快了， 因为一下子就能排除那么多类书，而代价仅仅是想一下书名第一个字的读音。不过，我们马上又发现，有的书架上书实在太多了， 那有什么关系？这个问题我们解决过啊，只要再分类就好了，书名第一个字我们用过了，现在用第二个字。

读者终于大致可以满意了。

这时候这些书架构成了一个查找树，方便查找。

另外，我们注意到，其实对于管理员来说，他的负担是增加了的，比如新来了一本书，如果图书馆是一堆书， 只要把新书扔在那一堆里就好了，如果是一排书，要把新书放在这排书的最后，而如果是分好类的书架， 管理员就要先找到这本书的位置，再把新书放在那儿，而不能随便放。好在分类后，我们找新书位置不会花多久， 假如分好类后，读者查找书方便了，但是管理员要把新书放在合适的位置，需要花一年时间， 那这个分类的方法肯定不是一个好方法。

这告诉我们

维护数据结构很重要。

这时候，我们在不知不觉间居然

设计了一个数据结构

这时候，我们回到开始时的问题，为什么我们需要数据结构？对应上面的故事， 为什么我们要把一堆书变成多类书？简单地说，这样可以使找书的过程变快。 这正印证了维基百科词条中的那句话。

数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。

回头想想，从一堆书变成多类书的过程，其实就是数据的组织方式发生了变化。我们来抽象一下整个过程。

• 我们有一堆数据D。
• 数据上最常用的操作是O。
• 我们的目标是让O很快。
• 我们设计一个数据结构S来组织数据D。
• 数据结构S需要额外的信息EI来组织数据D。
• 数据结构S有性质P，性质P可以使操作O很快。
• 数据结构除了支持操作O外，还要支持两个最基本的操作，Add:添加数据，Del:删除数据。
• 数据结构要保持性质P，所以Add,Del需要额外操作EO来保持P。

那么，关键的地方就在于:

根据操作O，找到性质P，设计数据结构S，使S有性质P，同时使额外信息EI，额外操作EO尽量小。

所以，无论是设计数据结构还是学习数据结构，都要弄清楚，

• 数据结构的关键性质是什么
• 为什么关键性质可以加快操作
• 额外信息与额外操作大小如何

下面我们探讨一些基本数据结构的特点

数组：数组的关键性质在于元素位置可以通过简单计算马上得到，这个关键性质为随机访问提供了很大的 便利。如果数据大小需要动态扩展，那么使用数组是不方便的，因为动态扩展难以维护数组的关键性质。

数组之所以拥有“元素位置可以通过简单计算得到”这个性质，在于数组在内存中是一片连续的区域，这样 知道数组第一个元素位置，知道每个元素大小，通过一次加法，一次乘法，就可以知道第N个元素的位置。 如果数组需要动态扩展，如果这片连续区域相邻的地方有可用内存，那么额外操作是分配这块区域给数组， 如果相邻位置没有可用内存，需要另找一片足够大的连续区域，作为新数组的位置，同时还要把已有数据 复制过去。

Read More ...