这个世界是我们的

九月 25, 2010
Life

土豆是我的兄弟,我们一起长大,一起上小学,上初中,高中,说的搞笑一点,是穿着同一条内裤长大的

土豆很有天赋,很小的时候就会拿着粉笔满屋子的画画而且画的有模有样,可惜爸妈都是农民,身边又没几个知识分子,土豆遇不上伯乐。书法也很好,小学 就已经拿过全国奖,不过没人栽培,现在也就马马虎虎了。还看过很多书,他曾经断断续续地拿过家里一千多块钱,然后全用来买书了,当然,他还不知到一千块钱 是很大一笔数目。他让我看得最多的是卡耐集的文集比如人性的弱点等等,可惜我识字不多,看的少。这些书,对土豆的成长有过很大的影响

土豆原本是农村里睡大街的小屁孩,后来考上了镇上的一所三流小学,四年级的时候又去到了镇上最好的中心小学,小学毕业后,考上了市里最烂的职高,三年后又考上了市里最棒的高中,大学,当然是比较烂了。这是他的人生曲线,土豆的故事太多了

土豆对数学出奇的感兴趣,我曾经翻看过他的手稿本,厚厚的一沓,泛黄的膜皮,渗水的笔迹,记录了土豆小学六年来对各种数学问题的思考与研究,比如,圆心在同一条直线上的连续圆,半径有什么关系

土豆初中的时候还曾经挂名到另外一个学校参加全国赛,拿了将了,后来就不得而知了。

土豆喜欢看书,不喜欢交朋友,性格不算孤僻但是喜欢独来独往,土豆的外号很多,比如化骨龙,因为他很瘦,又比如轻工水上飘,因为土豆不喜欢把时间浪 费在走路上,所以每次吃饭的时候跑得特别快,尤其人多的时候怎么跑都撞不到人,就得了这个称号。我也给他起过花名,因为他笑起来跟女人一个模样,不过他很 少笑,更多的时候,静静的一个人做自己的事

我曾经问过他咱们班上的人,谁谁谁啦,可惜很少有他答得出来的,他对他们很少印象,土豆甚至自己老师的名字都不知道。不过数学老师他是知道的,那个 时候土豆有过很长一段时间的辉煌历史,他对数学,知道的远比别人的多,他老是觉得老师讲的慢,磨磨蹭蹭的,就自己找书看,土豆第一次参加校内竞赛的时候, 考的有很大一部分都是超纲的题目,倒是对土豆来说没什么难度,结果他考了全校第一名,第二名是同班的,差了4分,大红纸贴出来的时候,大家一下子就爆炸开 了,因为第三名已经缩了二十多分了,也是因为这个事情,我和土豆认识了第一个朋友,阿飞,此后一路考试直至毕业,都是土豆第一,然后阿飞跟着第二,不过阿 飞英语要比土豆好。后来高中之后土豆去了高州中学,阿飞跳到了茂名一中,此后就更少有了联系

别人看来,土豆很成熟,懂得很多道理,待人处事方式很不一样,所以土豆虽然没什么朋友,但是很多同学喜欢悄悄地跟他聊心事,哪怕自己失恋了。有一件 事,对土豆的影响很大,这么说来,要追溯到小学的时候了,土豆经常受到班里某几个同学的欺负,而且有一个还跟着土豆一起上了初中。土豆后来跟我回忆说,因 为一件小事,本来不是土豆的错,但是土豆主动给那个人写了一封信,详细地写了很多事情并表示真诚的道歉,我问土豆,你有没有想过他看到这封信会觉得你更好 欺负,土豆说不知到,书上学到的,想尝试一下。很快那个人有了回信,静悄悄地放在了土豆的铅笔盒里,信里同样讲了很多事情,说,没想过你会给我写信,我想 他一定很感动,为了不是自己的过失却站出来向别人道歉,这是一种谦卑。土豆说,原谅别人,就是善待自己

土豆很有理想,虽然他不知到他的理想是什么,不过也正是因为这样,所以他才努力的让自己成长,有朝一日,可以看到外面的世界。我相信每个半夜起来沿着单车棚上厕所的人都忘不了那段奋斗史,一群在路灯下挑灯夜读,卧辛尝胆学子们,是土豆,民开,祖森他们,当然,还有我

土豆还曾经有过几个很好的朋友,就是所谓的四人帮,土豆,金海,健强,还有文家周,认识文家周是入学第一天晚上的时候,宿舍很热闹,家周和土豆是邻 床,两个人都不出声,土豆在听心灵地图,家周放着别安的歌,然后很奇异的一幕发生了,家周伸直两条腿,使劲往上蹬,手脚像个婴儿一样,土豆肯定觉得家周很 二B,两人相互对视了一眼,就这样认识了

之后,土豆和我上了高州中学,民开去了二中,祖森在一中,还有玮琪,在四中,其余的人,从此断了联系

土豆高一的时候曾经疯狂的迷恋过黑客技术,经常上课不听课就是经常抱着一本黑客X档案或者黑客手册之类的书籍在看,我记得他好像收过一个学弟,叫陈威,这件事说起来有点搞笑

土豆觉得自己水平还行,然后搞了一个团队,叫什么极度深寒二进制网络安全联盟,名字其实是从邪恶八进制那里来的,正好阿威那时候也正在看这类书,两 人一拍即合就成了拍当,土豆觉得光有团队不行,还得有团规,团章,当然了,肯定要收团费的嘛。于是土豆就跑去杂货市买了各种材料,连印章都叫人刻好了,前 前后后花了几百块钱。弄妥了就去找阿威,跟阿威说了入团的事,要了照片,还说,要收5元的团费,其实土豆本来不想收这个钱,只是觉得不收的话觉得阿威可能 怀疑自己是骗子,就象征性地要了5块钱,还跟阿威说,还有几个其他团队的成员,以后让你认识认识,其实谁也没有,土豆有意把团队搞的神秘一点而已,毕竟那 个时候能成为一名黑客是多么牛B哄哄的事情,后来每每我一想起这件事就觉得特别逗笑

土豆成绩倒退得特别厉害,期末考试的时候全科9门加起来都不够400分,我想很大一部分是因为这个原因。我找到土豆,跟他说,你现在看到的,真的是你想要的吗。我说你不应该把时间浪费在这里,如果你真的喜欢,就应该到更高的层次去深造,起码也等上了大学再说。我们触膝盖长谈,谈理想,谈了很长时间,最后土豆接受我的意见,把心思放回到学习上,争取考上好的大学。

土豆又开始过上了三点一线的生活,似乎比以前更安静,更忙了,土豆还是那样记不起班里同学的名字,甚至不常说话,只是在思考自己的问题,土豆学习很 有自己的一套方法,不像其他的同学,他做很少的习题一样可以有效果。相比盲目的去熟练那些公式,土豆更喜欢发现这些自然规律之间的内在关系,土豆更多的时 候是在想和总结。有一次土豆想的深了,想不出来,就去问老师,老师很惊讶,说思路没有问题,不过是微积分的问题,你们还没有学

慢慢地,土豆成绩回到了班上中上水平,高三的时候,已经稳定在班里全十名内,考个自己想要的学校已经不是什么问题了

不过,这个世界有时真会捉弄人,土豆的人生,一如有规律的跌宕起伏不断,我想,那年高考,如果不是因为那一场意外,土豆的人生也不会发生那么大的转变,也许今天,他也可以像很多人一样游走在ACM等赛场里大显身手甚至成为实验室的宠儿。

这一切,似乎与土豆无缘。高考结束后,土豆没有留下任何联系方式,连毕业照都没有拍,自己一个人背起包裹离开了,一走就是两年,杳无音信

再次见到土豆,是我已经快结束大二学业的时候,人在迷茫的时候是不是应该回到原点好好探讨一下,他说很庆幸终于找到自己的理想了,谈话间我还得知他恋爱了,我问他嫂子哪的,他说河南的,我笑着跟他说,那也好,两个人一起奋斗总比一个人更有力量

土豆此后陆陆续续来找过几次我,我察觉得出土豆的上进,他的好强,我有时笑他是平民科学家,土豆说,人离开了实验室,会不会就真的什么也做不出来,我说那当然不是,对土豆来说,所谓科学,是一种信仰,是学术自由

最近土豆一次过来,我们在学校的体育馆大汗淋漓地跑了几圈球场,吃完饭,我送了送土豆,回来的路上自己一个人静静的踹步在这个大学的校园里,上大学这么多年,很少有现在这样的心境了,想想我们过去的二十年,不禁感概万千

土豆来了短信,说:这个世界不止是有你们,我也可以改变世界

是的,只要不放弃,这个世界就是我们的

文本压缩的思考

十二月 7, 2009
Programming practices

最近断断续续花了很多时间在研究文本压缩领域,没有说是数据而是文本,是因为文本在特定的场合和环境可以有更大的改进和性能提升,比如基于 ASCII码和Unicode的就可以设计得截然不同,仅用一种方案来对不同的场景产生应用,是要付出一定的代价的比如性能。而且,不同的语言又会有不一 样的表现形式,这对垂直式的压缩技术来说是一种新的挑战。

因为业务需要,我希望可以实现一种更快的压缩算法,尤其是在解码方面要有不俗的速度表现。

我尝试过对哈夫曼编码进行一些细节上的改进,但是效果不太明显,哈夫曼编码的特点就是即使极限情况下也是能够保证绝对的压缩,当然能压缩多少倒是不 一定。编码过程比较块,难点就是对于这种比特流的存储方式,解码时必须单个比特地亦步进行,耗时特别长,是我不能接受的。研究算法远不是纸上谈兵那么简 单,不是随便在纸上画一棵二叉树就能解决问题领悟到信息论的奥秘。离开实际的应用研究不存在太大的意义,所以我们要清楚面临的需求以及对算法作出何种改进

 

lz77算法比传统的范式哈夫曼可能花费的时间更长一些,毕竟哈夫曼编码只需执行一次遍历就可以统计出编码模型而lz77则需要花费更多的时间在建 立字典和回溯检索上面。不过,lz77最大的特色就是解码特别的快,与其他编码相比解码速度完全不在一个数量级上面。lz77及其变种大部分的实现都是等 长编码,是建立在字节级别上的,不是比特流,本质上速度就有很大的优势。更重要的是,lz77每解码一个字符只需向前查看一次滑动缓冲区,总的时间复杂度 是Θ(n),线性

Gzip就是lz77很成功的一个例子,不过,网上说的那点也太简单了简直不值一谈,Gzip精妙的地方在于对算法做了很多有利的改进,我猜的,因为不管我怎么设计,以及优化,总是赶不上gzip的速度,事实证明,gzip真的很优秀

在滑动窗口也就是字典的设计上,我没有使用哈稀表而是用了一个二维数组来对任意字符进行索引,一方面我懒得搞那么复杂,而且二维数组似乎更加直观因为我主要基于单字。数组保存了对在滑动窗口里出现的所有字符的索引,而且采用了插入排序来改善查询的性能

到目前为止,整个实现最值得探讨的问题,在于滑动窗口的大小以及设计能够匹配的最大的长度,是关乎压缩效果最重要的一方面

从语言的角度来看,中文又不同于英文,英文里最常见的字符如 the,of,to,and 等在极短的滑动窗口里也可以有很好的匹配效果,但是中文就不一样了,还要取决于不同字符集的实现,滑动窗口要更大一些。这里就回出现一个性能项瓶的问题, 窗口规模与匹配的最大长度是成线性比例关系的,如果滑动窗口设计的太大,即使能匹配到好的长度,程序也要花费太多的时间在Match上面,而且大量的数据 可以表明,不是所有的字符串都能够找到最优匹配的,很多情况是,在小的窗口模式下,比如31或者63,能匹配成功的平均长度是1到2位左右,也就是说,2 个比特就足以完成保存匹配长度的工作,默认我设置了3bit,是因为我发现3bit的长度和31的窗口更有压缩上的优势

最终的测试结果是,相比较gzip的实现,压缩大约80M的文本语料库,平均时间为 1.413s,解压为 0.248s,压缩率是48.5%,而gzip的测试结果是,平均时间为 0.998s,解压为 0.131s,压缩率达到25%

我一直很好奇gzip是怎么做到的,如果我用多线程的话效果是不是会好一点。

目前所知,硬件层来说使用磁盘阵列可以提高io的效率,对压缩也是有好处的。

块排序压缩的数学原理

十一月 14, 2009
Programming practices

也叫 BWT 转换,严格来说不属于一个压缩算法,是压缩领域的辅助技术,BWT 的目的仅仅是将信息转换得更加适合压缩而已。BWT 巧妙的地方在于,只要精心设计,除了增加少额的计算量外,没有任何其他的开销。因为他的输出仅仅是将原有字符的排列顺序作了特定的安排

为了描述方便,举个简单点的例子,比如,即将处理的序列是 S = abraca ,S 的长度 N = 6,将 S 向右旋转一位,S 的末尾移动到 S 的首部,形成一个新的序列 S’ ,再将 S’ 向右移动一位再次产生新的序列 S”,重复这个步骤,直到得到一个 N*N 的矩阵 M,对 M 按字典排序,得到 M’ ,取矩阵 M’ 的最后一列作为输出,如下:

注意上面红色的 # 号,是一个辅助转换的结束符号,目的是为了标记原序列 S 属于 M’ 中的第几行,这个很重要,如果不使用结束标记符,就必须另外维护一个索引值,排序结果也会不一样,但是最终还原的字符序列是相同的。

逆转的过程更有意思,也非常简单,我们知道输出的序列 L=#rcaaba,L是表示矩阵 M’ 的最后一个序列,同理,F 是第一个,逆转的过程是从 L 恢复到整个 M’ 的过程,#号所在的 Row 就是原字符序列 S,因为 M’ 经过字典排序,自然 F 也是有序的

定理:对于包含 N 个字符的任意序列 S,按照 BWT 规则产生矩阵 M,对 M’ 进行字典排序得到 M’,假设 F 是 M’ 的第一列字符,L 是 M’ 的最后一列字符,若 F 是有序的,则 L 是唯一的。

从转换的过程我们知道,对于矩阵 M’ ,每行,每列所包含的元素都是相同的,也就是说,不考虑字典序,F 与 L 中的所有字符都存在一一对应的关系 T,在这里 L=#rcaaba ,所以 F=aaabcr#,则 T={6,5,4,0,1,3,2}

T 的计算过程有个需要注意的地方,L 与 F 中不是每个字符都是唯一的,也许有 N 个字符 value 相同,但是其实 index 不一样,L 中相同字符的索引顺序在 F 中也是完全相同的,也就是说,对 a,L=#rcaaba,F=aaabcr#,T 不可能是 {6,5,4,1,0,3,2},我们可以证明一下,为什么会这样。假设 ai 是 L 中所有字符 a 产生的一个序列,i=1,2,3,4……,i 表示 L 中出现该字符的序列,比如 a1 是 L 中第一个出现的字符 a,a2 是 L 中出现的第二个字符 a,以此类推,同理,对 F 中所有字符 a 产生的序列为 a’i,i=1,2,3,4……。能够证明,a’i 就是 ai

假设 pi 是序列 S 中紧接着 ai 后面的字符,对与 M’ 中任意一个最后字符为 ai 的行 r,则 r 的首位一定是 pi,不失一般性,取 L 中的 a1 a2,所在的行分别是 m n,而 m n 行的首位是 p1 p2,因为 index(a1) < index (a2) ,明显 index (p1) < index (p2) ,对于 F 中的 a’i,因为 a’i 的值是相同的,按照字典序,实际上排列的是 pi 而不是 ai,亦即 a’ipi=aipi,所以 a’i=ai,证毕。

有了关系 T,从 F 中得出原字符序列就变得相当容易了。S[N-1-i] = L[Ti[I]]  i=0,1,2,……,N-1 ,其中 I 就是结束符 # 在 L 中的次序,T0[x] = x ,  T(i+1)[x] = T[Ti[x]],本例中 I 是 0,所以有 S[N-1-0] = L[T0[I]] = L[I] = L[0] = F[6] = #,S[N-1-1] =  L[T1[I]] = L[T[0]] = L[6] = F[2] = a,最后 S0 = a,整个序列就出来了。

Michael Burrows 和 David Wheeler 确实很聪明,独辟蹊径完全从另外一个角度来思考压缩的过程,对算法设计的思考有很大的帮助,要学会如何寻找突破口。有没有想过,多阶 BWT 变换又会是什么情况?

参考文献:

^ Burrows M and Wheeler D (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation

Crash

十一月 12, 2009
Life

这是一部多元探究人类的心里与情绪反映的细腻之作。

故事透过地方检察官一家,经营商店的波斯商人,墨西哥锁匠,两个劫车混混,一个菜鸟警官与中年韩籍夫妇……

等等这样的角色,在短短36个小时间

经由间接,直接,甚至是不经意的互动,呈现出人们在不同时间与场景之中的情绪反映,以及这些情绪反映的联动关系对人们的命运、态度与观点所产生的影响 ……

“ ……

你知道,在很多城市里,你和别人擦肩而过,或者偶尔别人撞撞你。可是在洛杉矶没有人会碰到你的身体,我们总是躲在钢筋和玻璃的后面。或许是我们太怀念那种触感,以致需要通过剧烈碰撞才来体会得到…”

正是这部电影所要传达给我们思考的主题

香农熵与大脑学习

三月 6, 2009
Life

信息是个抽象的概念,我们常说信息很多或者很少,但是很难说清出信息到底有多少,比如一篇800字的文章有多少信息量。

直到 1948 年,信息论之父 C. E. Shannon 在其发表的论文  A Mathematical Theory of Communication 中第一次将热力学的熵引入到信息论,并用数学语言阐明了概率与信息冗余度的关系。

在通信领域,大家知道,通信链路传输的是比特流,通信的双方均会事先遵守某种人为约定,比如,00 表示“我”,01 表示“爱”,10 表示“老”,11 表示“婆”,所以如果 A 给 B 发送 00011011,B 就会知道 A 说了一句话:“我爱老婆”

Shannon 指出,任何信息都存在冗余,冗余大小与信息中每个符号(数字、字母或单词)的出现概率或者说不确定性有关。什么是冗余,冗余就是多余重复的东西,比如,通 信的 A 端给 B 连续发了 1000 次 00011011 比特序列,那么就有 999 次是多余的,实质上 A 只需给 B 传输一次,然后告诉 B 要重复多少遍就行。

举个例子,系统 S 内存在多个事件 S = {E1,…,En},每个事件可能出现的概率为 P = {p1, …, pn},则每个事件本身(信息本体)的量为: Ie = − log2pi(对数以2为底,单位是比特(bit))

如英语有26个字母,假如每个字母在文章中出现次数平均的话,每个字母的信息量为:

而汉字常用的有2500个,假如每个汉字在文章中出现次数平均的话,每个汉字的信息量为:

这就是 Shannon 的理论信息极限,相比使用 utf-8 字符集来传输,每个英文字符可节省的极限信息量是 8 – 4.7 = 3.3bit,而汉字则是 24 – 11.3 = 12.7 bit(注:在 utf-8 字符集里,用 8 bit来表示一位英文字符,用 24bit 来表示一个汉字) 。

-------------------------------------------------------------------------------------

OK,如果你能明白我上面说的,那就可以想得到,事实上信息处理的过程和大脑学习是多么的相似,人脑包括两个功能体,一个负责存储信息,一个负责处理信 息。今天我只想讨论大脑如何接受新知识的过程,假设信息的本体是“知识点”,这就有,人脑的学习过程其实就是不断存储新知识点的过程。

但是不同的大脑,对新知识接受的方式不同,等同与上面提到的通信约定,在计算机程序里相当于你取决于何种信息处理的算法。不同的算法,处理结果是不 一样的,比如说,你不一定要约定 00 表示“我”,你可以这样假定,0 表示“我”,100 表示“爱”,101表示“老”,然后 110 表示“婆”,传输的比特流就成了 0100101110,相对于第一种约定,多开销了 2 个比特

所谓信息处理的算法,在映射到大脑学习的过程里,是一个人接受新知识的能力,也就是说,你的能力越强,学习同样的东西,经过各自大脑的处理但是你的结果要比其他人更接近信息本体的极限,也就是说,你需要存储的量,要比他人少得多。

这里说的能力有两个意思:记忆力,以及能够揭示知识之间的关系

人的记忆力是不存在差别的,这点要切忌,记忆的本质只是知识重现的过程。想让你的知识变得更加牢固,就要不断重现它,一个单词读一遍和读1千遍的效 果截然不同,更重要的是,对一个知识点的不断重现,大脑就会将它放到越容易找到的地方。(因为有人想到这一点,所以发明了MTF转换)

而能否揭示知识之间的关系以及将这种关系揭示到何种程度,是衡量人与人之间能力差异化程度的重要标准,比如,算术编码就是一个很好的例子。此外,还 需注意的是,关系越复杂,人脑需要消耗的脑容量就越大,甚至有时超过于信息本体本身,这一点,我自己也不是很清除。不过有一点可以肯定的是,你挖掘的越 多,你的头脑就越灵活。

所以说,能力在很多时候是远要比知识更重要

格式化字符串

十月 23, 2008
Programming practices

这是在 mozilla open source 代码里发现的一个问题,目前还不确信是不是个BUG

c99引入了uintptr_t,uintmax_t 这样的标准数据类型,我们知道 printf() 函数对于常见的数据类型都有一个对应的 length modifier 用于格式化输出,int 的是 d,ptrdiff_t 的是 t,但是对于非标准的 pid_t,uintmax_t 等就没有对应的 length modifier 了。在c89的世界里,解决这种问题的常规化方案是强制类型转换到尽可能大的整数类型,比如这个 pid_t,POSIX 只要求它是一个 signed integer type,所以转化成 long 就OK了:

C++代码
  1. pid_t pid;
  2. printf("%ldn", (long )pid);

不过,c99新引了另一种方式,就是使用宏来替代 length modifier,例如 uint32_t,uintmax_t 可以使用 PRIu32 和 PRIuMAX,这些宏可以在 <inttypes.h> 中看到其定义(在 glibc 源代码中对应 sysdeps/generic/inttypes.h)。有兴趣的可以直接去看一下源代码,其实就是对已有的 format conversion 进行的宏封装。显然,第二种方式更优雅,但最近发现了一种更加优秀的方式,虽然看起来绕了一些弯路

C++代码
  1. /* Make sure BUFSIZE is large enough. */
  2. #define UMAX2S_BUFSIZE 21
  3. static char *
  4. umax2s(uintmax_t x, char *s)
  5. {
  6.     unsigned i;
  7.     /* LINTED */
  8.     assert(sizeof(uintmax_t) <= 8);
  9.     i = UMAX2S_BUFSIZE - 1;
  10.     s[i] = '�'';
  11.     do {
  12.         i--;
  13.         s[i] = "0123456789"[x % 10];
  14.         x /= (uintmax_t)10LL;
  15.     } while (x > 0);
  16.     return (&s[i]);
  17. }

这里以 uintmax_t 为例,逐个逐个的将整数的末尾转换成字符保存在缓冲区里,然后全体右移,小测一下,以数字 2334532234523为例,可以看到程序是怎么处理末位字符的

不过要注意 uintmax_t 是无符号整形,如果要处理有符号的,要剖离符号位使之变成绝对值来处理,这里只是提一下,其他自由发挥即可。另外,mozilla 里也是使用了一样的方法。

We don’t want to depend on vsnprintf() for production builds, since that can cause unnecessary bloat for static binaries.  umax2s() provides minimal integer printing functionality, so that malloc_printf() use can be limited to MALLOC_STATS code.

C++代码
  1. /* LINTED */
  2.  assert(sizeof(uintmax_t) <= 8);
  3.  i = UMAX2S_BUFSIZE - 1;
  4.  s[i] = '�'';
  5.  do {
  6.      i--;
  7.      s[i] = "0123456789"[(int)x % 10];
  8.      x /= (uintmax_t)10LL;
  9.  } while (x > 0);

我之所以觉得有问题是上面的第8行代码,mozilla 将 x 强制转换成了 int 型,因为 uintmax_t 类型要比 int 型所能表达的范围要大,如果 uintmax_t 值大于 int 所表示的范围而且相对 int 的最高位恰好是 1,强制转换后就是负数,负数对10取余,结果会是什么呢?大概是个BUG吧

深入浅出c指针

八月 13, 2008
Programming practices

指 针(pointer)是对“数据对象或函数”的一种引用,它记录了一个“对象或函数”的“内存地址和类型”。通俗地说,指针是一个变量,为了区分普通的变 量(普通的变量内存空间存储的是数值,而指针存储的却是计算机内存空间的某个地址),网络上很多资料对这个概念的叫法不一,有时叫指针,有时叫指针变量, 实质上都是同一个东西,指针本身就是一个变量,指针变量从语法的角度上看算不算重复累赘?

指针有很多用处,灵活性极强,比如,在C里,如果需要处理大量的数据的话,使用指向数据的指针比直接处理数据本身更经济和高效,又比如,你不需要移动内存中的数据就能对大量的记录进行排序,此外,利用指针,还能实现各种甚至非常复杂动态数据结构等等

声明指针

通常来说,指针的指向一般有几种:非数组对象,数组对象,函数,我们后面会更进一步地讨论“指向数组和函数”的指针,现在首先来看看,如何声明一个“指向非数组对象”的指针,语法描述如下:

C++代码
  1. type   *   [类型的限定符]   名称   [=初始值]

在 声明中,type   *  不同于 type,type 表示需要声明的是一个普通变量,而 type   * 声明的是一个指针,该指针指向 type类型的对象 ;[]表示参数具有可选性,比如 [=初始值] 表示在声明对象的同时初始值是可有可无的;类型的限定符,一般有const,volatile,restrict 等,关于指针类型的限定符,可以自行参考,这里不做详细描述;名称被声明为一个指针对象,其数据类型为 type   * ;

举个例子,声明一个指针p和变量k:   int   *p; 在上面这个声明里,我们可以得出很多有用的信息:

  1. p是指针,而不是 *p
  2. int  * 是指针的类型,而 int 是指针所指向的类型,int  * 的意思是说,我所指向的对象的数据类型必须为 int (当类型不一样时,某些编译器可能会进行隐式转换)
  3. 指针p 是一个变量,在32位机里,有4字节长的内存空间

在讲解指针的之前,我们先来解释一下有关指针的几个重要而且容易混乱的概念:

  1. 指 针:指针是一种非常特殊的变量,特殊的地方在于,一方面指针的内存空间并非用来保存有效数据,而是存储着另外一个对象或者函数的内存地址;另外一方面,不 管指针所指向的对象类型是什么,指针作为变量,自身的内存空间大小是一样的,换句话说,char  * 型和 int  *型的指针所占用的空间大小相同,在32位的计算机上,通常是4个字节长,刚好32位
  2. 指针的类型:既然指针也是变量,自然有自己的数据 类型,不同的是,普通变量的类型描述是 type  ,而指针的类型描述是 type  * ,指针的类型只有一个作用,它给计算机指出了自己所指向的必须是什么类型的对象,事实上,如果你强行将int  *类型的指针指向一个 char 类型的对象,那么编译器会发生隐式类型转换
  3. 指针所指向的类型:如果这个指针是指向对象的,那么指针所指向的类型就是该对象的类型;如果这个指针是指向一个函数的,那么这个指针所指向的类型就是该函数的返回值类型
  4. *  :要区别 * 的两种用法,在表达式里,*  是间接运算符,比如,对于指针 p ,那么*p的运算结果就是指针 p 所指向的对象的值(计算机是这样计算的,遇到 *p 指令时,p是指针,然后读取变量 p 的值,把这个值作为一个内存地址,寻址到这个值所在的内存区域,再读取出这个区域所存储的数据 β,那么 β 就是指针 p 所指向的对象的值);而在指针声明里,*  并不是运算符,而是声明符的一部分,它给计算机指出:我要声明的是指针而不是普通变量
  5. & :取址运算符,意思就是说,可以取得一个对象的内存地址,但是也有值得注意的地方,比如:假定变量 k 的数据类型是 char ,那么 &k 的结果产生一个 char  * 类型的指针,该指针自身的内存区域保存了变量 k 的空间地址

另外,即使指针保存的是另外一个对象在内存中的地址,但是也不可否认指针本身也是内存中的一个对象,因为它也是一个变量。站在对象的角度来看指针,那么其他的指针就可以指向该对象,这里就涉及到指针的复杂类型问题。解决这些疑问之前,先来看看下面的东西:

C++代码
  1. int**  a; //就是声明一个二级整型指针
  2. int*  *a; //就是声明一个整型指针,而这个指针本身也是一个指针,也就是二级指针
  3. int **a; //那就是声明一个整型变量,这个变量是一个二级指针变量

实际上这种解释并不正确,声明的描述也不规范。首先,我不清楚多级指针这个说法;其次,上面三种声明的描述其效果都是一样,但只有 int  **a  的写法才符合标准的;还有,说这话的人没真正的理解指针,因为指针本身就是一个 int 型变量。在C的规范里,我们说这类型指针 P 是复杂的,要声明一个复杂的指针,语法描述应该是:

C++代码
  1. type   *…*   [类型的限定符]   对象名   [=初始值]

*  描述符的多少取决于指针指向的复杂程度,假设你这样声明一个指针  int  ***p ;      这个声明这样解释:

  1. 声明了一个对象,这个对象是 p 而不是 *p 或者 **p ,p是指针!
  2. p 的类型是 int  ** ,int  ** 的意思是说,该指针最终所指向的对象一定是 int 类型的,当然,** 的意思,暗示了多重指引

还要说一下指向数组的指针的问题,在许多C程序里,指针通常指向一个数组对象,或者作为元素存储到数组里面。“指向数组的指针”通常被简称为数组指针,而“有指针类型元素的数组”则被成为指针数组,要声明指向数组类型的指针,必须使用括号,语法描述是:

C++代码
  1. type   (*…*   [类型的限定符]   对象名)[n]   [=初始值]

下面举个简单的例子来说明一下:

C++代码
  1. int  (* arrPtr)[10] = NULL ;

上面的声明描述可以这样解释:

  1. 声明一个指针 arrPtr 指向一个数组对象
  2. arrPtr 的指针类型是 int   (* )[10],它表示 arrPtr 必须是一个指向“拥有10个 int 元素的数组”

指向函数的指针比较复杂,后面我会专门讨论到这个问题,这里讲一下有个需要注意的地方,那就是 [类型的限定符] 的位置问题,无论是声明指向非数组对象的指针还是指向数组对象的指针,类型限定符处于不同位置,声明的效果是不一样的:

type   *   [类型的限定符]   名称   [=初始值]      (or)       type   [类型的限定符]   *   名称   [=初始值]

对于限定符 const,const 是一个常量关键字:

C++代码
  1. int  * const  Ptr;   //关键字 const 出现在 * 右边,表示要声明的是一个指针常量
  2. int  const  * Ptr;   //关键字 const 出现在 * 左边,表示要声明的是一个常量指针

要注意指针常量和常量指针的区别:指针常量,指针自身就是一个常量,表示指针自身不可变,但其指向的地址的内容是可以被修改的;常量指针,就是指向常量的指针,表示指针所指向的对象的值是不可修改的,但指针自身可变。

同样,对于指向数组的指针,下面的描述也是不一样,理解同上:

type   (*…*   [类型的限定符]   对象名)[n]   [=初始值]    和    type    [类型的限定符]     (*…*    对象名)[n]   [=初始值]

前者声明了数组指针常量,指针自身是不可被修改的,正因为如此,还多说一句,在声明一个指针常量的时候一定要进行初始化。后者声明了常量数组指针, 该指针指 向了一个数组名,不过,在C语言里,数组名本身就是一个指针,该指针指向了这个数组内存区域的首地址,按照语法描述的意思就是说,这个数组名就是一个常 量,但是计算机在给一个数组分配完内存的时候就是不变了的啊,这么说,这个语法描述就没什么意义了。


指针的初始化

具有自动生存周期的指针(被声明为 static ),是没有定义值的,除非声明的同时提供显式的初始化器(initializer),另外,如果既没有被声明为 static 又没有对其进行赋初值的,系统默认把空指针当作其初始化值,一个指针的初始化有以下几种方式:

一、使用空指针常量,比如,标准函数 fopen() 如果无法在指定的模式下打开某文件,将返回一个空指针常量 NULL

 

C++代码
  1. /* … */
  2. FILE *fp = fopen(“test.txt”,”r”)
  3. if(fp==NULL){
  4.     //Wrong ! Can’t open the file
  5. }

二、指向相同类型的指针,或者指向较少类型限定符的相同类型指针,要注意的是,如果指针不具有自动生存周期,必须使用常量表达式来初始化,比如“取址运算”的结果或者数组、函数的名称

 

 

C++代码
  1. #include <stdio.h>
  2. /* … */
  3. int s[10],*p;
  4. p=s;

三、一个 void 指针(被初始化的指针不能是函数指针)

 

另外注意,在对指针进行赋值操作时,如果表达式两边指针的类型不一致时,要注意编译器是否会进行一些隐式的操作,或者将一个指针显式地转换成另一个指针的类型,具体的细节和范例大家可以参考《C in a Nutsbell》 里的第四章:类型转换,有很详尽的描述

还有就是,给数组指针赋值或者初始化时,一定要注意数组指针的类型,这个很容易混乱,作为一个出色的程序员,你不应该忽略这些东西,下面是一个不规范写法的例程:

C++代码
  1. int main()
  2. {
  3.     int a[5];
  4.     int  const (* p)[10]=&a;
  5.     return 0;
  6. }

 


指针的运算

这 一节我们着重讨论指针相关的一些操作。常用的操作有:存储、读取和修改“指针所指向的”对象或函数,还有就是指针本身的运算,比如指针的自加自减运算等 等,也可以比较指针或者使用指针来遍历内存区域。上面我们提到过关乎指针运算很重要的两个符号,间接运算符 * 与取址运算符 & ,在这里有个需要注意的地方,乘法运算符 * 虽然和间接运算符 * 符号一样,但是性质是不一样的,前者是二元运算符,后者是一元运算符,也就是说,间接运算符只需要一个操作数。

假定 ptr 是一个指针,那么 *ptr 就是 ptr 所指向的对象或者函数,在指针的定义里我们得知,指针的类型决定所指向对象的类型,比方说,当用 int 指针存取一个特定位置时,读取或写入的也必须是 int 类型的对象,在下面的例子中,ptr 指向变量 x ,因此表达式 *ptr 等同于 x 本身

 

C++代码
  1. double x,y,*ptr;   //声明两个double变量,和一个指向double型对象的指针ptr
  2. ptr=&x;            //对x进行取址运算,&x产生一个指针,该指针指向一个double型的对象,也就是说,该指针的类型是 double * ,与 ptr 类型相同
  3. *ptr=7.8;          //因为 ptr 是指向 x 的指针,所以 *ptr 等同于 x ,对 *ptr 进行赋值操作也就是给 x 赋值
  4. y=*ptr+0.5;        //将 x 的值加上0.5再赋值给 y

对于复杂类型的指针,如指针 p,要注意给 p、*p、**p、***p 等赋值的意义是不一样的,示例:

 

 

C++代码
  1. Ptr = &k      //指针Ptr自身作为变量保存k的内存地址
  2. *Ptr = &k     //将k保存到指针Ptr所指向的对象的内存区域里
  3. **Ptr = &k    //计算机先找到Ptr指针指向的对象,将这个对象保存的数据作为内存地址继续找到下一个指向,然后写入k的首地址到这块内存区域里
  4. /* …… */

以此类推,在运算表达式里,* 的作用是在寻找指向的对象

 

除 了使用赋值操作让一个指针指向某对象或数组,也可以使用数学运算来修改指针,比如,对一个指针执行整数加法和减法操作;两个指针相减;比较两个指针 等等,通常这些相关运算的对象是数组指针。当两个指针想减时,这两个指针就必须具有相同的基本类型,但是类型限定符则不需要一样,因为类型限定符的作用是 指针本身,它就像一个监视器,必须保持指针具有什么样的性质,而不关乎你进行什么样的动作。

为了演示这些运算是怎么使用的,我们来看看下面的例子,其中两个指针 P1 和 P2 都指向数组 a 内的元素:

  1. 如果 P1 指向数组元素 a[i] ,并且 n 是一个整数,那么表达式 P2=P1+n 的结果就是:P2 指向了数组元素 a[i+n],也就是 *P2 等同于 a[i+n]
  2. 如果 temp = P2 – P1 ,那么 temp 的值就是两个指针之间数组元素的个数,temp 的类型是 ptrdiff_t,ptrdiff_t 是有符号整型 (int),在 stddef.h 头文件中有定义,用来记录两个指针的差距
  3. 在使用数组的时候,例:a[n],计算机通常会把 n 作为数组 a 内的一个索引,因此如果 P2 所指向的元素比 P1 所指向的元素具有更大的索引值,那么我们就说 P1<P2 的结果为 true,否则为 false

对 于第一种很好解释,数组名不同于变量名,在C里,数组的名称本身就是一个指针,它指向了数组的第一个元素,如果你非常熟悉汇编或计算机内的存储结构,那么 这点就不难理解了,我们可以把数组的下标计数法对换成指针的算术,定义数组 a[100] 和一个指向数组 a 内元素的指针 P1 ;

  1. a 是数组名,a + i 表达式的结果产生了一个指向 a[i] 的指针,而 *(a+i) 则是 a[i] 本身
  2. P1 – a  表达式的结果是 P1 所指向的元素的索引值

对 于指针与 int 型变量的相加减,编译器是这样处理的:假定 Ptr 是一个指向 char 型数组的指针,Ptr + n 的意思是,将指针 Ptr 向高地址移动 n*sizeof(char) ,在32位PC里,char 变量是1字节,也就是 8bits 的长度,如果 n 是3 ,那 n*sizeof(char)  就是 3*8=24(bits),相当于 n 个 char 型对象的长度,实际上也就是说,如果指针指向 Ptr 了一个数组对象,那么 Ptr 每次加 1 就相当于指针 Ptr 指向了数组的下一个元素。

现在你明白了吧,也许你会问,如果将一个 int *型的指针指向了 char 型的数组,类型不一样,按照上面的说法,指针加1岂不是不能指向到数组的下一个元素了吗?不是这样的,因为这种情况是不可能存在的,将一个 type  * 型的指针指向一个非 type 类型的数组,编译器会自动隐式地进行类型转换,这并是一种好的编程习惯,所以,应该尽量避免这种情况,否则,就显式地强制类型转换

为了助于大家的理解,我写了一个用指针来进行选择排序的算法

 

C++代码
  1. void selection_sort(int a[],int n){
  2.     int *last,*p,*minPtr;
  3.     last=a+(n-1)
  4.     if(n<=1)
  5.         return(-1);
  6.     for(;a<last;++a){
  7.         minPtr=a;
  8.         for(p=a+1;p<=last;++p)
  9.             if(*p<*minPtr)
  10.                 minPtr=p;
  11.         swap(a,minPtr);
  12.     }
  13. }

通常我们使用索引 i 来获取对应元素的数组,如 a[i] 或者 *(a+i) ,因为计算机会将数组的首地址 a 加上 i*sizeof(element type) 的值,这就增加了计算的重复工作量,而在上面的 selection_soft 算法里使指针自身进行递增的,无需索引就可以直接指向所需元素

 


关于指针的运算还有更为复杂的一种形式,那就是在二维数组里,以 int  a[3][5] ;  为例,首先来讲解一下二维数组的存储结构以及它和指针之间的关系,给二维数组分配内存的时候,首先将一块区域分成 3 大块,再将每一大块分成 5 小块,如果是三维数组,那就再将每一小块分成更小的块,以此类推

在一维数组里我们知道数组名本身就是一个指针,指向数组的第一个元素,但是,在二维数组里,并非如此,一旦声明一个二维数组 int  a[n][m] ;   我们就可以得到许多有用的信息:

  1. 集合 A = { a[x][y] | x∈[0,n-1] , y∈[0,m-1] } 中的每一个元素都是一个 int 型变量
  2. 集合 B = { a[x] | x∈[0,n-1]  } 中的每一个元素都是一个指针,指针的类型是 int  *,所指向对象的类型是 int
  3. 数组名 a 也是一个指针,指针的类型是 int  (* )[m],所指向对象的类型是 int  [m]

第 一条不解释,第二条很好理解,因为二维数组还有另一层含义,那就是它本身也是一个存储了n个指针(每个指针指向一个一维数组)的一维数组,比如你看上 图,a[0] 可以看作是由 a[0][0] , a[0][1] ,a[0][2] ,a[0][3] ,a[0][4] 所组成的一维数组的数组名, a[1] 也可以看作是由 a[1][0] , a[1][1] ,a[1][2] ,a[1][3] ,a[1][4] 所组成的一维数组的数组名,这么说来 a[0] 和 a[1] 又是指针,指向了各自数组的第一个元素,所指向的元素的数据类型是 int,所以 a[0] , a[1] 指针的类型是 int  * 。同样的道理,a 可以是指针数组的数组名,a 是指针,不同的是,数组元素并不是指针 a[0] , a[1] , a[2],而是 a[0]‘ , a[1]‘ , a[2]‘,a[0] , a[1] , a[2] 指向的是一个数组,但 a[0]‘ , a[1]‘ , a[2]‘ 指向的却是与数组a[0] , 数组a[1] , 数组a[2] 占有相同大小空间的内存区域,所以指针 a 的指针类型是 int (* )[5],这一点一定要区分。

如果你明白我上面所说的,下面的一些演示例子会帮助你加深理解:

 

C++代码
  1. int matrix[3][10];   //定义一个二维数组matrix
  2. int (* arrPtr)[3];      //定义一个指向int (* )[10]型指针的指针
  3. arrPtr = matrix;      //让 arrPtr 指向matrix的第一大块内存区域
  4. (* arrPtr)[0]=5;      //给matrix[0][0]赋值
  5. arrPtr[2][9]=6;       //给最后一个元素赋值
  6. ++arrPtr;                  //将 arrPtr 指向matrix的下一大块内存区域
  7. (* arrPtr)[0]=7       //给matrix[1][0]赋值

 


指向函数的指针

与“指向数组”指针的声明一样,函数指针的声明也需要括号。下面的范例展示如何声明“指向函数”的指针:

 

C++代码
  1. int  (* funcPtr) (int , int)

此声明定义了一个函数指针,被指向的函数需要两个 int 参数和一个 int 型返回值,注意一定要将 * 与标识符括起来,如果没有括号,int  *(funcPtr) (int , int); 的声明就是函数的原型,而不是指针的定义了。还有就是,函数名称会被编译器隐式地转换成函数指针,因此,下面的语句会将标准函数 pow 的地址赋值给 funcPtr ,然后利用指针调用此函数:

 

 

C++代码
  1. double result;
  2. funcPtr = pow;
  3. ……
  4. result = (*funcPtr)(2.2,4.3);  //调用funcPtr 所指向的函数
  5. result = funcPtr(2.2,4.3);     //效果与上面是一样的

 

毕业细语

六月 15, 2008
Life

高考结束,没有毕业典礼,同学们都陆陆续续回家了。有很多人还会回来,但也有不少人,将很少回来,甚至也许再也不会回来。或许,很难再见到他们了。
整个学校也安静下来了,难得的宁静。
教室里顿时变得空空荡荡。往日的人、书,如今都离开了。往日熟悉的笑脸也都离开了。这里,肯定还会热闹起来,但已经不再是我那60个昔日同窗了。望着仅剩的桌子和凳子,感觉心里很失落。就这样结束了?桌子和凳子,黑板和粉笔,你们的静默,是否也是在失落与感伤?
或许因为安排的事情太多没有时间,或许因为我自己不知道从何开口,所以,毕业了,也没有和同学们正式说过离别感言、赠言什么的。是否有些不够完整?
只顾着给他们写毕业留言,居然忘了把我的毕业纪念册也给他们,请他们写留言给我。真是不该!
毕业,说明我们长大了,学到了不少东西。这是好事!应该高兴!
但愿,在三年里,作为他们人生中的过客,能落幕他们心里依稀的回忆。
祝愿,他们在未来的日子里,继续健康成长,道路越走越宽,创造美好的未来!