|
|
（一）
终于还是要写这种文章了。期末考试将至，写大程序没时间，写小程序没动力，只要演变成写文章了。之前的两篇字符串处理写完了仍然不过瘾，打算继续写关于递归下降法和LALR的事。后来想想还是暂时写写关于如何学习编程的好，毕竟这个问题对大家来说更加有益。
本篇将是一个系列，重点讲述在外力很少的情况下如何自学编程，以及需要注意的一些地方。
一般来说，一些所谓的『高手』或者老师会告诉人们算法是非常非常重要，以至于会不会算法就是你会不会编程的唯一标准。不过事实上并非如此。掌握算法固然是好，只是大部分程序并不需要高深的算法，而且招人的时候仅仅要求会算法的公司也是很少的（而且很难进）。我并不是学院派的人，所以虽然我本人也推崇学习算法，但并不推崇一开始就学习算法。
刚开始学编程的人总是不知道自己应该从哪里入手。实际上这是一个相当重要的问题。在我看来，学好编程有若干条件：
- 兴趣
- 数学/英语
- 财力
首先谈一谈兴趣。那些为了生计而寻找捷径学习编程的人并不在本篇的考虑范围之内，这些人我通常是不管的。兴趣是非常重要的一个条件，但是兴趣也是可以培养的。对编程的浓厚兴趣可以让自己自发地寻找各种各样的书籍，发现自己知识结构上的弱点，跟同行有效地进行交流等等。那些没有兴趣的人遇到了一个问题只会上论坛或者QQ群上要代码（而且多数脾气暴躁）。
数学和英语在一开始并没有什么影响，但是在你学有所成之后，开始接触复杂的内容的时候，数学能力就开始起作用了。很多计算机论文都是使用数学语言写的，对数学没有热情或者不够敏感的人将会很难跨过这个门槛学习一些书本上没有的东西。英语同样也是重要的，因为并不是所有的文章或书籍都会翻译成中文，或者及时翻译成中文。
财力并不是重点，不过至少在养活自己的同时要有闲散资金来不停地支付网络费用、书籍、电脑、外围设备等必须物品。
至于知识结构方面我个人的见解可能跟流行的观点有所出入。目前人们总是把知识结构比喻为一个金字塔，最下面是基础，上面一层一层更加深入而且更加专业的知识，最上是领域知识。老师们会说要学好基础，首先学好语言和算法，然后慢慢往上走。我自己并不这么认为。个人认为『从左到右』的学习方法是更加有效而且不会错过什么东西的，只是不能速成。
从左到右是什么意思呢？想象一个金字塔，最左边仍然是最底层的【基础】，再往左就涉及到更多的【基础】以及更多的上层内容了。这样一步一步下去就会有【基础】--【上层】--【基础】--【上层】这样的不断循环。这么做的好处是成果快，能够培养起兴趣和成就感，而且基础随着应用的需要慢慢积累，等到学有所成的时候，基础也覆盖完了，上层的东西也看得差不多了，就可以超越金字塔自己翱翔了。
好了，那么如何培养兴趣呢？
人总是对有趣的东西比较感兴趣的，而且这种东西如果不难入门的话，那么接受起来更加容易，跟容易培养成就感，也就更有兴趣了。根据实际情况，个人推荐刚开始接触的时候应该学习C#，理由如下：
- C#的书籍非常多，语言内核简单易懂，类库丰富。
- C#制作界面简单
- C#屏蔽了有关操作系统和底层的大部分事情，可以让学习的人专注于自己感兴趣的内容。
如果不是特别着急的话，一开始就对着C/C++的数组啊指针啊什么乱七八糟的东西我觉得没什么必要，反正将来自然就知道了。我在这里推荐C#的另一个重要原因是Microsoft Visual Studio .NET的C#编辑器有一个无敌美好的提示列表（按了一个“.”之后弹出来的），这对于初学者来说是相当好的一个工具。
一开始学习C#的时候应该首先掌握基本的少量语法，也就是说掌握条件语句、分支语句、函数声明以及数组，外加少量库的运用以及计算上的知识。然后开始学习制作界面，最后学GDI+。
学习GDI+是有很多好处的。不过在学习之前应该找本相关的书来看。GDI+有一些比较高级的功能如半透明效果和画刷等等，容易组合出一些非常漂亮的图形来。学会GDI+的基本操作之后，就可以慢慢接触一些图形滤镜、分形、三维的内容了。使用平面工具绘制简单的三维图形是一件非常有意思的事情，而且非常锻炼数学能力，所得到的效果也是『令人震撼』的。
随后应该学习字符串处理。典型的字符串处理有分析INI文件、对一个四则运算式子进行操作等等的内容。虽然C#处理器字符串出来比C++稍微蹩脚一点，不过在这个时候忽略这个问题是相当有用的，至少不用陷入无穷的指针漩涡里面去。
等图形和字符串都少有涉猎之后，就可以开始开发有趣的程序了。譬如用C#些动画、开发画函数图的工具、自己设计一种高度简化的HTML然后进行渲染制作自己的帮助程序、或者开发简单的图像处理软件之类。稍微聪明一点的人，如果每天都有机会写很多代码的话，大概半年到一年就可以走到这里了。
为什么我会选择图形和字符串两种东西呢？为了培养兴趣，首先要有成就感。图形跟字符串都是跟操作系统本身没关系的东西，而且操作起来也没什么注意事项，因此入门比较简单。如果渐渐深入的话会激发起学习数据结构、算法、甚至是数学英语的热情。如果可以使用这条主线贯穿整个编程的初级阶段的话，得到的将会是扎实的基础以及灵活的头脑。
好了，今天就先说到这里。下次再写续篇。在此解答一下大家有可能提出来的疑问。
· 数据库和网络都很热门，要不要学呢？
-- 这两门技术掌握了也是很好的一件事情，而且作为入门的话也未尝不可。只是如果一开始就往数据库和网络的路走的话，将来可能会错过一些学习操作系统底层以及复杂的算法的机会，因为这两种东西不会让你有学习大部分有深度的知识的动力。
· 算法为什么不一开始学习呢？
-- 学会了算法，但是没有有趣问题给你解决的话，那学来干什么？而且学习算法的最终目的是让自己拥有设计算法的能力，很多人都忽略了这一点。
· 学会了GDI+和字符串之后能不能找工作呢？
-- 不能。做人切勿急躁，学编程没有个三五年还是不要把自己看得太厉害的好。
· 接下来应该学习什么样的东西呢？
-- 请看下一篇文章
（二）
接着上一篇文章继续往下讲。如果按照上一篇文章走下去的话，现在估计做了有些小软件了吧。字符串和图形都容易做大，而且对于潜意识上喜欢数学的最有希望的程序员们也是有吸引力的。但是这两种东西却不容易做好。等到程序到了一定规模的时候，维护和效率这两大问题就会凸显出来。心急吃不了热豆腐，为了解决维护和效率这两个经常会出现的问题，我们需要学习算法和架构。这两种东西是可以同时学的，但是一篇文章说不了多少东西，那么就从算法开始吧。
程序员是需要开阔眼界的，光C#一门也是不行的，毕竟程序运行在各种平台上，有各种各样的语言。譬如Win32上的native C/C++、Delphi等，.NET上的C#和VB.NET，还有自成体系的Java，然后就是运行在mainframe上的COBOL，剩下的还有各种各样的函数式语言、脚本语言等等。熟悉了C#的人从Delphi入手不会很困难，从C/C++入手也可以了。这两门原本是本地语言的语言在编写程序的时候需要我们注意多一些的东西，典型的就是内存管理。这还是需要多加练习的，在这里就不多说了。
说到算法，在这里首先向大家推荐《算法导论》第二版。一年前我去买的时候，发现了中文版，但是中文版那个时候仍然有一些章节没有翻译。不知道现在怎么样了。英语好的同志们可以去买英文版。
算法与数据结构是经常出现在一起的。每一种算法总会有在各种不同数据结构上的实现，用于处理不同的问题。在不同的语言上面，各种各样针对实际问题的数据结构也有一些巧妙的做法和通用的做法。我们可以用STL，可以用System.Collections.Generic，也可以自己写。这根据实际情况而定。我们并不是不能做的比STL好，只是STL已经相当好了，满足了大多数人的需要。在特定的情况下，面对非常特殊的问题，有时候我们就要自己实现数据结构。使用上一篇文章说的办法来联系的话，到了这个时候已经写了不少代码了，用了不少并不复杂的数学知识了，锻炼了理论与实际相联系的基础。有了这些基础，我们学习算法和数据结构会比较简单。
常用的数据结构有链表、列表、堆栈、队列、二叉树、平衡树、堆、哈希表和图等，除此之外还有各种各样的变形，但是万变不离其宗。围绕着这些数据结构还有各种各样的算法。典型的有排序算法、搜索算法、寻路算法、网络流等等。还有一些属于策略的算法，譬如贪心算法、动态规划等等。属于策略的算法经常用于制造新的算法，要慢慢体会，勤加思考才行。至于这些数据结构和算法的实际内容我并不打算在这篇文章讲。《算法导论》用了半本书来说这些问题，还是看书的好，文章不够详细。
至于我们如何选择算法呢？就如同我刚才强调的一样，我们需要联系理论与实际的经验，我们要用数学的眼光来看待我们需要解决的问题。如果我们找到了一种简洁的表示来描述我们的问题的话，我们同时也找到了解决问题需要的数据结构的雏形。当然这个数学并不是指数学分析这些，我觉得更接近于抽象代数。扯远了啊，一般来说我们并不需要钻研这些学科，我们只需要有感觉就好了。培养感觉的一个捷径就是学习数学。当然不学习也可以，经验也能知道我们做事情，只不过走的路要长一些。至于读者希不希望学习数学就自己决定吧，没有普适的道路。找到了数据结构的雏形之后，剩下的就是寻找算法了。有一些算法可以在书里面找到（譬如ACM很喜欢考的题目），有一些算法可以在论文中找到（譬如专门为了对付一些复杂问题而制造出来的不具有通用性的算法），剩下的就要靠我们自己去推导了。
那么，我们如何学习算法呢？我们是为了解决实际问题才学习算法的，是为了为将来自己遇到问题的时候有个指导方向才学习算法的，我们并不是为了学习算法而学习算法。我见过两种不同的学习算法的人。第一种是直觉阅读算法并学习，以后碰到问题再寻找。另一种则是仅仅将算法稍微了解一下然后就放开，以后遇到问题的时候再翻开相应的算法来学习。两种方法适应于两种不同的人，并没有什么大的优劣之分。于是我们根据自己的兴趣或者需要，终于必须掌握一种算法了。那么这个时候我们可以找资料来看，就跟阅读文章一样消化里面的知识，然后就写一些小程序来试验试验（或者叫做原型，那些做软件工程的人都喜欢这么说）。这种小程序属于抛弃型原型，写完即扔的，目的是为了让自己在了解了算法的内容之后，检验一下自己是否已经真的明白了执行这个算法所需要的所有细节问题。等到觉得自己已经能控制这个算法的时候，我想也就差不多了吧。
有些人可能会觉得算法很复杂，因为书里面的算法都是非常复杂的。但是算法的目的是为了快，因此有一些好的算法跟数据结构结合的时候可能会变得相当简单，但是并不是很容易想到。在这里我举几个简单的例子。
喜欢做图形的朋友们，大概都喜欢做游戏吧，嘿嘿。我们小时候在做那种简单的2D游戏的时候，总是要计算一大堆人之间是否相互接触，或者很多人放出的魔法是否跟敌人碰撞到。如果我们的地图上有100个人，每个人放了两招，两两检验是否碰撞（以便判断是否应该实施攻击）的话就需要检查20000次。这显然是不行的。那么我们可以使用分而治之的原理来做。我们可以把地图切成很多个区域，区域包含着人和魔法。每当人和魔法的移动越过区域的边界的时候，人和魔法就把自己从前一个区域断开，链接到新的区域里面去。这个时候区域就保存了两个链表，一个是人，另一个是魔法。好了，如何检查魔法和人互相碰撞呢？只需要检查同一个区域里面的就行了。如果这100人都在25个区域里面，平均每个区域有4个人8个魔法，那么两两检验的话只需要检查4×8×25=800次，相对于前面的暴力算法节省了96%的时间。当然这只是理想状态。
在这里举另一个例子。我们都觉得C#、VB和Java很神奇吧，东西new了都不用delete，多舒服。假设我们现在要实现这种功能的话，我们需要维护所有已经new了的内存空间，并执行一种搜索算法来判断哪一些内存空间是再也不可能被访问的然后标记，最后删掉所有被标记的空间。于是我们需要一个内存管理器，用来申请、标记和释放。如何做比较合适呢？
我们的内存管理器需要根据设置的长度返回一段句柄来代表内存空间，然后需要可以通过句柄来访问内存，最后标记并一起删除这些句柄。为什么要句柄呢？因为如果直接返回指针的话，语言执行久了会产生很多内存碎片，而且new和delete也不够快。现在，我们需要以下几个数据结构：
- 一个记录所有被new了而且delete过的句柄的列表，用于迅速获得没有正在被使用的句柄。
- 一个记录了所有正在使用的句柄的列表，记录指针以及长度。这张表是一个数组，句柄是索引。
1. new的时候，我们查询第一张表拿出一个空闲的句柄。如果列表为空的话那么将第二个表变大（这个时候所有句柄都被使用）并且将第一个空闲的（也就是原来的表接下去的第一个新空间）句柄所对应的记录标记使用。然后我们分配的总是最末尾的地方。
2. delete的时候，我们查询所有标记了使用句柄，看看是否有被mark，有的话就标记为不使用并将句柄放置入第一张表。
3. mark的时候，我们查询这个句柄所对应的记录，然后mark。
4. collect的时候，这是一个操作，将所有内存碎片清除。我们只需要顺序遍历第二章表，将有用的内容挪动到前面一大块无用的空间里面，复制一下数据然后修改一下起始指针即可。
图示一下：
空闲句柄：1 2
句柄记录：<0,0..9><1,NULL><2,NULL><3,40..43>
内存空间：[第0-9个字节占用][10-39不占用][40-43被占用][此处为末尾]
好了，我们需要申请一个内存空间，我们拿到了句柄4，需要10个字节。
空闲句柄：1 2
句柄记录：<0,0..9><1,NULL><2,NULL><3,40..43><4,44..53>
内存空间：[第0-9个字节占用][10-39不占用][40-43被占用][44-53被占用][此处为末尾]
现在我们标记3并删除：
空闲句柄：1 2 3
句柄记录：<0,0..9><1,NULL><2,NULL><3,NULL><4,10..19>
内存空间：[第0-9个字节占用][10-19占用，从句柄4挪过来的][此处为末尾]
分析一下时间复杂度吧，这里分析的是绝大部分情况，根据数据结构的实际实现偶尔会有少许偏差。
new为O(1)，因为从空闲句柄获得内容为O(1)，分配末尾内存为O(1)，找到记录并标记为O(1)
mark为O(1)，因为找到记录并标记为O(1)
delete为O(1)，因为只需要标记
collect为O(n)，因为遍历句柄记录O(n)，挪动内容，就算最多也就挪动整段内存空间，也是O(n)
从句并获得内存地址也是O(1)
我们仅仅需要在内存不够的情况下才动用win32的api分配一块新的大内存，这样来看的话在大部分情况下我们的内存管理器的分配比操作系统做得还快，这也是为什么C#作为托管语言并没有明显慢下来的一个原因。当然还有一些其他原因，譬如.NET虚拟机会把一些托管代码临时编译成本地代码等等。
至于第三个例子，就看这里吧，为了做一个大作业而弄出来的利用动态规划是显得简单寻路算法。
说到这里本篇也快结束了。举着两个例子只为了说明以下问题：
- 算法往往跟执行效率有很大关系
- 好的数据结构才能发挥算法应有的威力
- 要根据实际情况来选择，甚至自己思考算法
- 算法并不都是复杂的
其实，对于数据结构和算法不熟悉或者根本没听说过的话，也并不是就不能写出一些稍微有点规模的程序，只是写出来的程序可能会很乱。算法在一个程序员的发展道路上看还是最好学一学。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
