本文主要是从应用角度出发,分别阐述操作系统接口,计算机语言,文件系统等背后的一些知识,规范,原理,设计思想,应用法门,让初学者编码有一个整体的,全局的认识,有一个物理的视角,找到自己的起点。

计算机语言与编译器

计算机语言就是一套人机交互的协议,好比我们学了英语,就可以同“支持”英语的人交流,来达到我们的一些目的。计算机语言的本质也是一样的,程序员通过某语言来调配它的资源,完成目标任务。无论是什么语言,语法方面都大同小异,无非就是变量定义,表达式加几个循环而已--它的理论源头就是大名鼎鼎的图灵完备的编程语言。图灵从理论上论证了,只要符合图灵完备规则,就可以满足所有的自动化计算的需要。

因此,各种语言的语法都大同小异,那么,为什么我们还需要那么多的语言呢?
这就回到了“什么是计算机语言的本质“这个问题了,语言的核心到底是什么呢? 很显然不是语法,而是它编程思想和资源(功能)。 每种语言都是为了解决某些问题而存在,都会提供一套语法和平台资源--包括标准库和第三方库。

汇编语言主要是为了方便记忆,对机器指令上做了一个替换,没有汇编语言,我们还需要一边查着芯片手册,一边手敲着  "6F 01 20" 之类的代码。由于它没有提供内存管理和系统结构化的手段,本质上还是机器指令级别的编程。使用汇编语言,我们还得规划内存,挑选寄存器,完成堆栈操作,因此,汇编只适合代码量少的系统。如很小的单片机或者系统的引导代码。高级语言则不同,编译器帮忙搞掂了内存布局,进栈出栈等这些烦琐的事情,直接面向应用。

C语言提供了面向模块的结构化思想,通过模块化机制,我们可以分工合作,构建起应用。学习C语言,就是要了解它的模块化思想,学会如何利用数据结构和函数指针封装模块,提供统一对外接口。另外,还得了解它的库,这个决定了我们能获得多大的资源支持。C的基本库对系统调用进行了封装, 提供了一些跟操作系统相关的函数(文件操作,进程管理,内存相关,socket等),它没有提供常用的数据结构和算法(比如:链表的构建和排序,二叉树),需要自己处理。 在应用层面,它则提供了字符和字符串处理,数学函数(sin,cos,tan,...),日期和时间等等,可见C语言的标准库提供的都是底层的函数,当然了也有一些上层的GUI框架利用C语言提供接口的,他们在C的基础上提供大量的扩展,一步步地架构了自己的系统。

C++虽然是C的扩展,但它是全新的语言,提供的是面向对象的架构思想。只不是兼容C语言规范,它可以利用C语言的所有资源。它利用模板来提供标准库(STL)封装了常用的数据结构和算法。 官方又提供的 Boost模板库,拥有了更丰富更强大的功能。 利用STL/Boost和基础C库,都足以开发一些底层软件。 C和C++的基础库都没有提供图形,多媒体,GUI框架,用户需要使用第三方的资源,如:SDL, opengl,Qt等。

像JAVA这类带虚拟机的语言最厉害的地方,除了跨平台性,就是它强大的类库。不但封装了常用的数据结构和算法,还集成了GUI框架,图形库,多媒体处理,也有很强的web处理能力。

python则提出不要重复造"轮子",因为它提供了大量可用的轮子,从基础的数据结构到大型的应用模块,应有尽有。几句代码就可以完成一个 http服务器。 而且,python把变量定义这个环节都省了,直接面对要解决的问题,效率极高,特别适合教学,科研,做算法分析和原型验证,工具软件。 你想想,现在你突然有了一个算法构想,马上想验证一下,使用的python的话,你直接就可以写算法代码了,想当于把算法的伪码拿过来直接就用了。

用C语言的话,你得先定义各种数据结构,变量,再编译,排错,真的是很会很急人的,如果涉及到字符串的处理,心早就拔凉拔凉了。
软件编程就是利用语言来调配各种资源来实现目标。学习一门新语言,除了学习语法,更多的关注点还是它提供的编程思想和它的平台资源。你得了解目标语言提供的各种资源,了解它的适用场景,它是为解决什么问题而存在。最好的学习方法是看一些经典的源码,如:mplayer的C语言代码,很好地诠释了什么是模块化设计,真的令人叹为观止,会发现原来自己根本就不会写代码。

学汇编的比C语言厉害些吗?
经常会听到这样的争论,有一次地铁上,我在用C++编码,旁边一个”哥们“问我学习C++是不是赚钱些,我惟苦笑不已。语言本身没有高下之分,会用这个语言来完成任务才算厉害,最厉害的就是做出产品,像 freebsd, linux 这种划时代的产品,才是真的厉害。对程序员而已,厉害的是你的编程思想和算法能力,行业的专业知识。语言这种东西,只是是信手拈来,实现你的想法而已。

编译器就是语言的某一个具体实现,厂家不同,产品不同,像经典的 TC 和 VC。 编译器最基础的功能就是把所支持的源语言,编译成操作系统支持的可执行文件格式。如果,它再提供一个GUI界面,增加了源码编辑,断点调试,GUI框架,那么,它就成了一个开发平台,比如经典的VC。 目前,我们使用的集成开发环境都是融合了编辑,编译,项目管理,资源编辑,GUI控件布局,代码生成等一系列工具。

对于初学者还是建议大家自己使用GCC来作编译器, GDB来调试, 自己写Makefile来定义编译规则,再找一个源码编辑工具像Emacs或者Eclipse之类,这样大家可以很清晰地知道自己在干什么,需要做什么。再使用集成开发工具的时候,知道该怎么去处理各种问题,不然一直稀里糊涂地不不知道一个'Run'点下去,到底发生了什么,一出问题就傻眼。

如果需要重量级GUI框架的,可以考虑Qt平台,初学者也不要使用Qt Creator,可以自己使用Qt的工具来做预处理,如:

           

可以定义相应的规则,把它放到Makefile里面,这样就可以使用make来进行管理。

 

数据结构和算法

话说学好了数据结构和算法,就基本解决了编程问题。可是当我们拖拉几个控件,写几个事件,就可以完成工作的时候,不禁会有点疑惑,说好的数据结构和算法呢。--其实,它无处不在,在应用框架里,在中间件里,在API里面,在 Kernel里。 C++的STL和JAVA都把一些常用的数据结构封装成了“集合”对象。
数据结构就是对客观对象的抽象,算法则是如何来组织和调用这些数据。在kernel里面,我们耳熟能详的概念都是一个个具体的数据结构如:进程,内存页面等等。下面是linux的进程数据结构'struct task_struct'部分片断,可以看到对进程的描述信息(属性)都定义在该结构里面了。

这个就是我们通过ps命令看到的进程信息描述,其实在linux kernel都是按照线程来管理的,所以,task_struct 也是线程的描述。 linux 源码里面就是大量的这种数据结构定义,以及把它们链接起来进行管理的各类链表,二分查找树。

 

下面简单说下数据结构和算法在STL里面的应用。

STL作为C++的标准库,它封装了常用的数据结构和算法。
<vector> 的数据结构本质上是动态数组,当空间不够的时候,它重新分配空间,并拷贝旧元素到的数组。

  • “读”的时间复杂度是常量--可以随机访问。
  • “插入” 需要额外进行数据拷贝,时间复杂度是 O(n)--n是pos到end元素数量,这部分数据需要拷贝。
  • “push_back”的操作时间经平摊后是常量级别,vector在插入元素时,往往会额外多分配一点空间,以免每次插入元素都进行“重分配”和“拷贝”的操作。  使用vector最好可以显示地给它分配空间,以提高性能。

<list> 是一个链表,“读”和“ 插入”的时间复杂度是O(n)--n是元素的位置, “插入”数据操作的时间消耗是常量级的。

虽然<vector>的'插入'时间复杂度也是O(n),但是,<list>不需要拷贝后面的元素,只需要移动到相应的位置,它的'插入'性能更好,而<vector> 提供随机访问能力,适合通过'数组下标'直接访问场合。  

有没有像<vector>那样提供随机访问能力,但是又能提供<list>那样的插入性能的数据结构呢?  
有,那就是<deque>,它相当于是<vector>和<list>的一个结合,相当于<list>来连接固定大小的<vector>。

 

(图片来源于 stackoverflow.com)

  • “读”的时间复杂度是常量--可以随机访问。
  •  “插入”的时间复杂度是O(n)--n是元素的位置

那是不是可以使用<deque>来代替<vector>和<list>呢? 当然不可以:

  • <deque>的内存浪费会比较严重,那怕只有一个元素也会分配一整个数据块。
  • <deque>的随机访问效率还是不如<vector>高。
  • <deque>在某个chunk的插入也还面临着拷贝末端数据的问题,因此,严格意义上说,它的插入性能还是不如<list>。

<set>和<map> 通常用一棵红黑二叉树来做为数据结构的实现,根据关键字来排序,“查找”,“插入”和”“删除”的时间开销都是 O(lg(n)),它里面的记录是有序排列的,我们根据关键字把它导出来就是一个有序列表,它们的综合性能比较好。

如果需要更快速的访问能力,可以考虑使用带hash结构的<unordered_set>和<unordered_map> “查找”,“插入”和”“删除”的平均开销是“常量级”的,性能很好,但是它里面的数据是“无序”的。

 

用户评论:
发表评论: (限500字)

注册 忘记密码 登录