周弈帆的博客
0%

Posted on In ,

本文转载自我的知乎回答如何评价北京理工大学第十五届“连山科技”程序设计大赛？

最近时间开始多了起来，我准备多写点东西。

如何评价北京理工大学第十五届“连山科技”程序设计大赛？

光阴似箭，从大一我第一次参加新生赛，到昨天最后一次参加校赛，已经过了三年了。最开始的时候，还能见到14级的强神、庆神，现在20级的新生都已经在比赛中大放光彩了，真是让人感觉时光荏苒；不过，年年比赛都能看到易大师、龙神、牟神、沈帝等人的身影，又仿佛一切都没变过，我的时间永远定格在大一的暑假集训。做为一个退役选手，本次比赛的意义对我的意义已经不在于过了多少题，更多的是一些比赛之外的东西。

按照老规矩，我还是会完全站在个人视角，先对比赛的出题质量、服务质量进行评论，再以时间顺序从网络赛到正赛谈个人经历和感想。个人感想可能有点多，可以直接跳到最后面看总结。

评价

由于这次命题组人数较多，且有龙神等出题经验丰富的前辈，整体试题质量极高。从题型覆盖看，模拟、签到（排序）、dp、博弈、字符串、图论、计算几何、构造……应有尽有；从难度分布来看，正赛6题快银，8题快金，冠军队更是以唯一10题队的身份稳稳占据榜首，题目区分度十分明显。具体到每道题上，不少题目出得十分精彩，其中最令人印象深刻的是网络赛G题构造，讨论完普遍情况，特判完所有特殊情况后，一发畅快淋漓的AC令人意犹未尽。

但是，题目的质量仍有提升空间。从题面上看，亮皇出的热身赛J题中文语法混乱、逻辑不清，参赛者不得不凭借自己的脑补能力把题意理解清楚。正赛最后一题M题对于d的解释不够清楚。正赛又是网络流，又是高斯消元，又是后缀自动机，需要使用模板的地方略多。

服务质量仅讨论中关村正赛。打印服务一开始不能正常工作，且奇慢无比，严重阻塞了三线程的运行。编译环境恶劣，只有不带c++11的devc稍微好用，codeblocks一开始没编译器，后来编译器不能在32位系统上运行。比赛完回到良乡后，滚榜都快结束了，冷餐就剩了一点“给中关村选手准备的食物”。好的地方不是没有，志愿者和裁判组倒是十分积极努力地在提升选手的参赛体验。虽然很多问题是客观问题，再怎么样也不能改变，但该喷还是得喷。

网络选拔赛

我一直很想再参加一次团队算法竞赛，但比赛报名前夕才发现没队友。幸好喵神把我拉进了她们队里，三个退役选手组了个队。现在的我，回想起那个因找到队伍而欣喜的下午，绝对想不到之后我竟然会成为一个工具人。报名开始后，喵神不肯做队长，要我去报名时，我就感到不对劲。之后，各种繁琐的流程接踵而至。又是填报名信息，又是接邮件记密码，之后还要领衣服，比赛完了还要填获奖信息。热身赛我一个人去检查环境，比赛完我一个人回去领奖。虽然如此，比赛的时候大家还是在愉快地讨论，参赛体验还是不错的。

网络赛的时候，为了创造更好的参赛体验，不让学弟们感到太多的压力，我们选择不发挥全力，在实力上有所保留（实际上是，队友不在校内，编程环境不太好，代码只能让我提交）。最终我们过了9题，既向大家展现了实力，又把宝贵的前几名让给了学弟们，可谓是用心良苦。

比赛开始前一小时，我去cf随便写了几题。当我熟练地在5秒内敲完for(int i =0; i < n; i++)时，我感到一切都回来了。手速、算法知识、编程技巧，我完完全全地找回了它们。我自信地迎接着网络赛的到来。

比赛一开始，一股熟悉的想抢一血的冲动涌上心头。我本能地点开I题，浏览题目之后，发现事情不对，立马换题。抱着想抢一血的功利心，我不想花费一分一秒在看榜上。很快，我准备写F题。

F题很明显是个排序签到题，写惯了正经代码的我，从这样一道算法少、流程繁琐的题开写是十分妥当的。可惜意识尚在，熟练度尽失。我仔仔细细地读了遍题，工工整整地定义了类和两个排序函数，main函数里用简短优美的代码完成了整个算法流程。我颤颤巍巍地把代码上传，确认再三后才点击了提交。焦躁地按了几下F5刷新后，屏幕上出现了一行绿色的CORRECT。看到代码通过后，我体会到久违而熟悉的成就感。此时比赛已过去21分钟，不仅F题一血没了，其他水题也被陆陆续续地通过了。但我的斗志丝毫没有衰退，带着首次过题的成就感BUFF，心态良好地开始跟榜做题。

我看L题过题人数最多，就开始写L题。L题是个超级签到题，用第一个月学C语言的知识就能轻松做出。

A题一看就是个“模拟”题。久经战阵的我，发现了题目和数据的不一致性，并且知道样例才是正确的。我用一个比较繁琐的方法才把图片导入进代码：先读入样例文件，把空格和符号转化成01串，再把01串粘贴进代码。我及其稳健地一次通过A题。

B题过的人也不少，但乍看之下不是什么简单的题：和普通背包问题类似，你要保证不超出背包容量的前提下选择物品，获得最大价值。只是每次选择的物品不大于上次物品的重量。但仔细观察数据范围可以发现，物品数、重量全都不超过100。我一边写代码，一边以极强的基本功在心里推出转移函数，顺利过了B题。

J题全是用中文写的，但读起来和天书一样，在跟榜做题的原则下，我不得不开了这题。题目给了一行数，每个数字表示一个物品；又给了一个每种物品的数量要求。你要从这行数中选一个连续区间，使得选的物品满足物品数量要求，求最小区间长。数的规模是1e6。我看答案是单调的，先考虑了二分答案，再想到用尺取判断答案。后来发现不用二分直接尺取就可以过了。不过出题人比较善良，加了二分也没有t。J题也被轻松通过。

这个时候，我的队友加入了战场。湛学姐读完了D题E题，以极强的思考能力迅速理论AC了这两道题。于是，我选择去实现E题。

E题是计算几何题，给出平面上若干点，保证不存在三点共线。要求找到一对点，使得过这两点的直线能恰好平分剩余的点，或者说明这样的点对不存在。由于要求正好平分，奇数个点的情况就之前pass了。对于偶数个点，以某个点为原点进行极角排序，找到排序后最中间的点。原点和中间点就是答案。极角排序的原点可以选择最左下角的点，但比赛的时候我先找了下凸包，再选了凸包上一点。由于我对自己的板子很不熟悉，WA了两发。但是，此刻我知道我不能再浪了。为了契合我们的队名，我发出了“从现在开始，不会再WA”的宣言。

喵神负责写D题，似乎看出了只需计算素因子贡献就行了，一次性顺利过题。

湛学姐又读完了C题，快速给出了做法。我用两分钟时间看完并理解了转述的题意和解法，用二十分钟稳健地AC这题。题目给了一个元素不重复的数组，在保持元素不重复的前提下，可以进行一种操作，操作每次可以把数组里的一个数转换成另一个数。现在给出数组的初始状态和操作若干次之后的状态，问最早需要操作几次及具体方案。一个数在被转换之前，需要保证转换之后的数不在当前的数组中出现。因此，如果数组初始状态和最终状态中不同位置出现相同数字，可以对把这两个位置连一条有向边，表示对两个位置操作的先后性。最终得到的图如果没有环，可以直接按着有向边的顺序进行操作；如果出现环，就把某个位置先修改成一个tmp值，把环拆掉，再进行操作。

剩下的题目中最有希望的是G题。G题过题人数较多，且是构造题，想到就能过。题目要求用两种形状的积木拼出一个给定长宽的矩形，问方案是否存在，若存在要输出具体方案。积木的形状是

1
2
***      **
 *       *

经讨论，2X3，2X5~2Xn都能构造出来。4X4特判。3X5无法构造。仅需讨论5X5能否构造即可构造出剩余比较大的矩形。湛学姐以极强的洞察力和丰富的想象力，构造出了5X5的方案。我负责把代码写出来。由于这题要求输出方案，代码极其繁琐。我凭借着多年积累的结构化编程经验，把每个操作模块化实现，先后实现了声明新积木、画积木、转积木、反转矩形、画矩形等函数。整个程序变量名、函数名清楚易懂，代码逻辑清晰，堪称代码中的典范，入选世界10大优美ACM代码也不令人奇怪。最终2发AC，第一发WA在了2X2上。

后来学姐们发现I题是个原题，以前打多校赛的时候写过，本来准备粘一份代码。但喵神坚持着网络选拔赛过题影响正赛RP的封建迷信，拒绝了这种做法。我也秉承着给学弟们保留信心的做法，没有过题。网络赛就这样结束了。很久没有这么爽快地过题，我感到神清气爽。

正赛

刚才，有个朋友，和我说：“帆神，写个答案吧。”

我说：“怎么回事？”他给我发了一个知乎链接，我一看，噢，原来是佐天，有一个竞赛，叫“连山科技”，算法竞赛。我和两个学姐，退役选手，一个研一，一个研二，参加了比赛。

比赛前，我说：“加入你们，让你们丢了最佳女队，不好意思。”塔们说：“没事，你可以carry。”我说：“我carry不了，但我们可以抢一血。按传统的比赛情况来看呢，我是抢一血的。去年校赛，前年新生赛，我的队伍都拿到了全场一血，啊。（笑）”

塔们也很服气，说可以试试。比赛一开始，喵神啪地一下就撕开试题册，很快啊。然后就是，一个找题，一个写题，一个交题。代码提交了，手放到提交键上没有点。这时间，按照传统的比赛情况来看，如果这个键点下去，一血就是我们队的了。塔知道这个代码一定能过，但塔又去检查了一遍代码，塔知道这个代码能提交通过的，啊。但提交一看呢，噢，一血没了，额，大概几分钟前没了，老年人，手速慢了。

但没关系啊。我手里还有题的啊。我老规矩，开局看了I题。发现不对，又去看了G题。G题很明显是个签到题，sg函数，搞个二维的，随便写一写就过了啊。我啪、啪，敲了几下键盘，额这个题目就写好了，很快啊。交上去一看，RE！

喵神说，塔有H题可以写，要我去打印代码。我说：“可以。”我大意了啊，不知道，这个打印机呢，坏了。这个三线程工作，给阻塞了。但我也不傻啊，又去看L题，说：”题目简单，我可以写。“

当时急着过题，我又大意了啊。交了L题，WA了。我一改代码，咋样例又不对呢。湛学姐和我讲了遍题意，噢，原来是题读错了。我说：”对不起对不起，我题读错了，我是乱写的。“喵神又把我踢下去了。

湛学姐急了，塔一直在读题，额，大概有4，5道题，都已经理论AC了。塔说：”I题是个签到题。”塔和我讲了讲题意，一个排序，再随便搞一搞，就好了。噢，原来我上当了。我说：“你来写I题。”总算啊，81分钟，过了第二道，签到题。

之后，我又说：“L题我可以改。”写完了，感觉很正确，交上去，又WA了。喵神看了看，发现有一个排序，有一个小问题，写反了。塔指点了一下，就稍微指点了一下啊，我改完，题就过了。两个小时，我才写了一题。为了表示谦让，我是全队最后一个过题的人啊。

这时间，那个打印机啊，搞好了。G题代码，给送了过来。我一看，噢，一个数组下标，本来是a-b，给写成了b-a。数组下标成了负数，这不RE才奇怪呢。一改完，题就过了。本来开场20分钟就过了，现在两小时20分钟才过，整整120分钟，啊。我们呢，刻意的呢，想多让学弟们，让塔们一些罚时。

喵神又去写H题去了。湛学姐又理论AC了一题，就是那个J题，枚举一下，套个高斯消元就过了啊。我用我的人脑评测机啊，测了测塔的算法，感觉确实没问题。D题、M题，早就会写了，我说：“你来写。”塔说：“我不写。这是码农题。传统码农题是讲代码量的，一题二百行。”我说：”那我来写。”这时候，我们等于呢，已经过了7题。喵神H一过，那就算过了8题了，啊。

喵神呢，交了两发H，然后发现题读错了。我说：”停停。没关系啊，我也读错了题。但现在，要以大局为重，让我写D和M。“我上去，一个手起键落，以迅雷不及掩耳之势，花了一个小时，才把，就把D和M写完了啊。我练过三、四年算法竞赛啊，训练有素。三小时的时间里，我们AC了6题。

喵神说H题过不了。我问，怎么回事，算法问题还是写法问题。塔说，算法和湛学姐讨论了，没有问题。一个DAG，点有点权，边有次数限制。从1点到n点，可以走无限趟，求最大价值。塔说，贪心，每趟取最大价值，不用写网络流。二十分钟就有人过了题啊。我一下没找出反例，说打印代码看看。

这时候啊，一个裁判，龙神，走了过来。他说，出题人，牟神，让喵神去写字符串。挑衅我们啊。我们哪有不理他的道理啊。既然这H题算法没问题，我说那我来看H题代码，你们去写E题字符串吧。塔们说，可以。

我拿过H题代码一看，没毛病啊。正着看，反着看，代码都倒背如流了，也没发现什么大问题啊。我用人脑编译器，诶，编译了一下，二进制代码都生成了，跑了样例，流程没问题，结果没问题。我啥也干不了了。

只听那边啊，谈论得，风生水起，什么后缀自动机、fail边，后来又是multiset，很复杂啊。我后缀自动机，都全忘，不能说全忘，都策略性地存储到了大脑深处了啊。没办法，很烦，帮不上忙。

最后半小时，没事干，我又看起了H题。突然，我想出了一组反例，嚯，算法假了。网络流带回边的，这样贪心表示不了操作撤销啊。最后也来不及想了，就也没过题了。

赛后一看，E题做法没错，F题也是会写，但没写。不算H题，理论上我们过了8题。四舍五入，其实就是一等奖队伍啊。最后，发现我们只有三等奖。其实，减去G题打印机导致的罚时，还是有二等奖的。但是出于对后辈的考虑啊，刻意没拿这个二等奖。

后来去问出题人，塔们说I题本来是A题，怕大家不敢看A和A调换了一下。塔们说是乱换的，塔们可不是乱换的啊。仔细反思，这次比赛，没有抢到更多的钱，原因有三点。一，签到题I题被替换了；二，打印机坏了；三，出题人挑衅参赛选手。这些出题人、裁判员，不讲武德，来，骗，来，偷袭，我们三个，加起来六十多岁的，老选手。这好么？这不好。我劝，这些出题人，耗子尾汁，好好反思，以后不要在题目顺序搞聪明，小聪明啊。

比赛结果，重要吗？不重要。重要的是你学会了什么，你得到了什么。比赛，要以和为贵，要讲娱乐，要讲友谊，不要搞，内卷化。谢谢朋友们！

总结

这次比赛，貌似是我生涯中结果最差的一次比赛。但是，这是非常有趣，令人难忘的一次比赛。不去追求名次，而是享受比赛本身，享受交流、合作、共同自闭，这是之前我从来没有做到的。很荣幸能参加这次比赛，能最后一次体会到算法竞赛合作的乐趣。

赛后仔细看了看榜，排名前列的好几个队都是大一队。正如其他人所说的，后生可畏，北理进Final有望了。但除此之外，我还有一些其他的期待：北理ACM集训队的寒假集训和暑假集训做的非常棒，通过大一一年的学习，有志于竞赛的同学能学到很多东西。但是，之后就没有什么正式的培养学生的流程了，很多情况下只能靠学生的自律来进行训练。ACM固然是强调个人能力的竞赛，个人能力是取得好成绩的前提条件。但是，个人的某些竞赛经验、思考方式是可以传承的，也有许多有潜力却没经验的人需要更好的指导才能成长。祝愿现役选手、未来即将加入集训队的同学们取得好的成绩。也希望你们在保证了自己的比赛成绩后，能把自己收获的东西传承下去，让北理的ACM水平一直提升。

最后打个广告，欢迎关注我的博客。我即将在一个月后对我的ACM经历进行回忆和整理，会发到博客和知乎。希望大家保持关注。

我对这篇文章的评论

文章以幽默的语气，生动形象地描写了老年选手在比赛时候的手足无措，同时其中透露出的欢快之情体现了选手享受比赛本身的放松心态，旨在让读者以一种全新的视角来看待算法竞赛。

Posted on In ,

我已经半年多没有认真写博客，没有静静地分析、思考一个问题了。最近，几个“项目”（有明确结束条件的事情）已经结束， 我可以抽出一些时间，来反思一下生活中的事情。

过去这半年，我的整体表现和之前一样：没有产生什么突出的成果，也说不上毫无作为。一切都还算顺利地进行着。未来，准备出国的材料，再申请一所符合我水平的学校，一切也估计会正常进行下去。这半年我也有许多做的不好的地方，或许以后时间多了我会抽时间来专门反思一下。

回到今天的主题。大四开学后，我周围的学习（努力）氛围发生了翻天覆地的变化。步入大学的最后一年后，所有同学都忙了起来，为未来拼搏着。我的室友要考研，他们都早出晚归，去教室自习；隔壁宿舍有找工作的同学，三天两头出去面试；和我一样出国的同学，为推荐信等材料烦恼焦虑着。我虽然一开始就目标十分明确，且不会因周围的环境而改变自己的行动，但我依然被周围的环境震撼了：命运的分岔口就在前方，所有人都很忙啊！

大学本科有一个共识：大四的成绩是没有用的。无论是保送研究生，还是出国，都只计算前三年的成绩。对于还有着其他目标要达成的同学来说，大四的课程就是一个累赘。我自然也不例外。我深刻地感受到，大四的课程严重占用了我准备出国的时间，尤其我们大四的第一门课还是一个要三周完成的大项目。

这个时候，我产生了一种看起来很矛盾的想法：如果说准备出国，或者考研、找工作等事情是我们的主要目标的话，那么认真花时间学习大四的课程，不就是在浪费时间吗？这和平时打游戏，不去认真上课，不是本质上相同吗？

这话乍看之下确实很有道理。当然，这句话默认了一个前提：大四的课对你未来的目标几乎毫无帮助。有过上大学经历的人大概都会同意这句话，因为绝大多数的大学课程，在它的分数失去了功利的作用后，就变得毫无价值了。和自己的人生目标相比，上课竟然变成了和玩游戏本质一样的浪费时间的事情，真是十分讽刺。

我虽然产生了这种想法，但我隐隐感觉有一些不对劲，我本能地认为这种想法是错误的。我把这种想法概括成了一个问题：做无益目标的事情是在浪费时间吗？经过一定时间的思考，我认为这种说法完全是错误的。

人们习惯于单一目标

从小学开始，我们就被灌输了一个概念：学习成绩是最重要的。在高考之前，我们所做的一切事情就是取得好的学习成绩，考上一所好大学。上大学后，大家的目标会稍有变化。有些人专心刷绩点，争取保研名额；有些人一边保持着绩点，一边想办法接触国外的教授，为出国准备优秀的材料。再过一段时间后，有些人会开始准备复习考研的各个科目，还有些人会看面经，准备工作面试。大部分人，哪怕是本身对人生不够有主见的人，都能在环境的影响下找到一个短期内值得奋斗的目标。人们基本上都在为单一目标奋斗着。

有些观点说，人们习惯于单一目标，是我们从小的应试教育造成的。但我看未必，因为人本身就习惯于单一目标。竞技项目中，无论是传统的体育竞技，还是智力竞技，都只要完成在本项目上提升自己，战胜对手这一目标即可。在面对单一目标的时候，我们能很明确地知道哪些事情是有益的，哪些事情是无益的。s在刷绩点的时候，玩游戏就是无意义的；在当职业电竞选手时，不玩游戏反而是不对的。可以说，追求单一目标本身就是简单的。只要有一定来自内心或外界的动力，明确了每件事是否有益，全力去做有益的事情即可。人们选择去实现单一目标，本质上是选择了一种简单的做事方式。

另一方面，单一目标意味着评价标准唯一。在单一目标上取得优秀成果的人，往往能收获到很多世俗上的利益，这鼓励着其他人也追求着单一目标的优秀。高考分数高，意味着你能上一个好大学，“改变命运”；绩点高，推荐信强，有学术成果，你能去世界一流大学研究，“成为学术大牛，改变世界”；在竞技项目上成为顶尖选手，你能收获荣誉、收获粉丝的崇拜、收获名利。

可以说，人们习惯于单一目标，人们往往为单一目标而奋斗。确实，许多人因为单一目标的成功而成了受人羡慕的人，这鼓励着其他人继续为单一目标而奋斗。

更多目标与更远的目标

其实说了这么久，我一直没有解释单目标是什么。或者说，从对立面来看，什么不是单目标的态度。事实上，我自己也习惯了单目标的思维，单目标成为了一种普遍、唯一存在的事情。解释什么是单目标，其实意味着思考单目标的对立面是什么，这本身就是一件很有挑战的事情。

从单目标，很容易想到多目标。除了我们当前正在做的事情以外，还有许多重要的事情。沉浸于心流之中（玩游戏）、与他人进行一次有趣的谈话（吹牛）、欣赏作品（看动画），这些事情都能令我们很开心，却又常常与我们的当前目标无关。你能说这些事不重要吗？我们当前主要目标之外的其他一些事情，同样很重要。

此外，我们眼中无比重要的单一目标，往往只不过是我们人生中的一个岔路口。回头望去，很多当时我们觉得天都要塌的要紧的事，其实根本不重要；很多我们当时的无心之举，往往深刻了影响了我们的一生。小时候，一不小心丢了东西，一不小心考砸了，可能觉得自己要被骂死了，事后之后成为有趣的谈资；以前无心接触的爱好，可能一直推动着我们前进，最后成为终身的职业。那么未来何尝不是如此呢？未来的目标与现在的目标有多少关系呢？你保研成功了，又意味着什么呢？你进入了世界一流学校，又意味着什么呢？你选择了自己心仪的专业，或者选择了天坑专业，又意味着什么呢？你高考复读了一年，或本科毕业gap一年，又意味着什么呢？你成绩不好，无奈选择考研又意味着什么呢？你的一时的成功或者一时的失败，真的就是一辈子的成功和一辈子的失败吗？现在的事情，对以后的工作、升职、赚钱、成家、糊口、育儿，有多大的影响呢？即使你赚了大钱，有着无数可以挥霍的财产，你接下来又该做些什么呢？未来有无限的可能，更有无数要考虑的目标。现在的单一目标，很难说对未来的目标有多少影响，甚至大部分情况下毫无影响。

再进一步思考，上文中提到的更多目标，比如在娱乐中收获的快乐，这些重要的事情该如何概括呢？我认为，这些事情其实就是人生意义的本质。人生是为了什么呢？不就是为了获得满足感，享受开心的时刻。能够直接通过生活中的一些小事，收获快乐，实现人生的意义，何乐而不为呢？我认为单一目标外的更多目标，是能直接实现的人生终极目标。而上文提到的更远的目标，实际上也有一个尽头。工作、赚钱，最终可能是实现自我的价值，或者是实现自我对社会的价值。所谓更远的目标，实际上是比较困难，需要间接实现的人生终极目标。这两者本质上都是我们要实现的终极目标，只是表现的形式、难易不同。

简单的满足感、自我价值的实现，这两者的本质相同，性质却不太一样，得分开讨论。做无益单一目标的事，显然不是在浪费时间。除了单一目标外，我们要考虑如何实现这两种目标。当然，这两方面的话题拓展下去又可以谈出更多东西，我今天只稍微谈一些比较浅显的看法。

实现简单的满足

实际上，大家都会自然地追求这种简单的满足。学累了玩一盘游戏，周末和他人聚个会。不过，在各种错误的宣传下，有些人会认为这些放松是不对的。因此，在实现简单的满足这件事上，主要是要让自己摆正态度，让自己明白放松是非常正确的，不应有任何负罪感。在有了正确的认识后，再去考虑发现生活中能令自己开心的事情，多去享受那些快乐的瞬间。

这里跑一点题，稍微谈一下游戏的事情。我之前把大四时花时间学习课程，和平时花时间打游戏对比，其实已经表明了我不认为做无益目标的事是没意义的——我向来是支持玩游戏的。玩正确的游戏本身能带来很多精神上的享受，这本来是一件中性的事情。有些沉迷打游戏的人，只是为了逃避生活中的事情，选择了一件能快速大量获得享受的事情而已。能在合适的时候里玩合适的游戏，一定是有益于生活的。就获得满足的角度上来看，玩游戏和出去运动、和别人聚会等事情没有本质的区别。一定要对放松的事情有正确的认识。

能获取简单满足的事情可就多了，每类事都可以都可以花很多文字来分析。但稍微分一下类的话，可以分成直接的感官刺激，比如吃美食，去游乐园；个人精神的享受，比如玩游戏、看视频；社交的享受，比如聚会、聊天。

准备更远的目标

实现眼前的单一目标，很多时候是必须的事情。但是，我们不能忘记未来有更多的目标，不能忽视现在一些对未来有益的事情。有些做法看似不是当前目标的最优解，甚至对当前目标的完成有负面影响，但对我们的长远发展有利。比如准备语言考试，去报只学解题技巧，和自己稳扎稳打地准备。虽然后者效率更低，但显然更能提升自身的语言水平。尽量追求全局的最大价值，就是我最喜欢讲的“大局观”。显然，人不是机器，生活也不是一个可以用公式表达出来的有最优值的函数。我们永远做不到最优，却可以找到一些更优的原则。

提升自我对世界的认识，这在任何情况下都是最重要的，因为自我对世界的认识决定了你做一切事的方法和态度。自我对世界的认识就是如何看待自己及自己与周围事物的关系，比如：我在这个世界上的地位是怎么样的？我想成为怎样的人？我该怎么样提升自己？我这篇文章所说的内容也包含在内：如何看待当前最优目标与其他事情的关系。在提升对世界的认识上，一个非常有用的经验是：越是去思考，并去改变自己的看法，越能对世界有更正确的认识——所谓更正确，指在做事的时候更加顺利，毕竟对世界的规律了解得越多，越能利用这些规律。

提升自己的核心竞争力。这点要和学生时代唯分数论的观点比较起来看。分数大致上能反映一个人的综合能力，却无法反映一个人的技能水平。但在社会上，想要活下去，或者更好的活下去，必须得有比别人更突出的地方。无论当前的主要目标是什么，都不要忘记自己的优势是什么，如何提升自己优势，让自己的优势别人发掘，或者主动利用优势创造价值。

最后再重新提一次，由于我人生经验尚浅，很多内容了解的不够多，在人生其他目标的了解不足，无法展开来讲。其实本篇文章主要是因为我发现了一种普遍存在的“学生思维”，我自己也没能脱离这种思维后，想专门针对大四面对主要目标的矛盾时应该怎么做写一篇议论性的文章。

大学本科的学习即将结束，我感觉我将面对更多的事情，经历更多的挑战与机会。不论如何，我认为自己在某些方面非常强。在反复确认了自己认为重要的事情是什么后，我有信心去实现我看重的人生目标。

Posted on In ,

和上一篇博文一样，这篇博文也是一个项目回顾与总结。

这个项目是我NLP的第二个大作业。在这个大作业中，老师要求做一个能完成某个功能（而不是做句法分析等预处理工作）的NLP程序。选题时可以从老师给定的题目中选，也可以自己找一个题目。当时我时间并不是很充足（感觉这学期我就没有在时间充裕的情况下写过项目），准备尽快把项目做完，因此决定从老师给的题目里挑一个来实现。一开始我挑了垃圾评论检测，因为老师明确指出，只要实现一篇论文的内容就行了。我去搜了那篇论文，却发现论文的数据集不是公开的，想获取数据集需要发邮件去申请，十分麻烦。我只好在剩下的题目中再找一个题目出来。排除掉了一些看上去不是那么实用的题目后，我选择了”汉语自动纠错系统“这个题目。在论文中，这个问题被称作”中文拼写检查(Chinese Spelling Check)”。

我很快搜索到了一篇非常好的综述博客[4]。根据博客中的介绍，我去读了几篇论文。比较幸运的是，这些论文中的算法对我来说非常简单，我很快就理解了算法的细节。比较了各种方法的实现难度并参考了综述博客对各种方法的比较结果后，我选择了[3]中的方法。一般来说，拼写检查问题可以分成两个部分：先对句子进行分词，再根据分词结果进行拼写检查。[3]的方法可以同时完成这个两个步骤，处理起来比较方便。

我很快实现了分词算法，并且按照评估标准评价了我的程序的表现。我本以为这个项目就这样结束了，但我对我程序极差的表现产生了一丝怀疑。我更仔细地阅读了一下论文，发现论文除了提出分词算法外，还提出了一种利用数据统计文字错误概率的方法。文章利用了谷歌1T的数据库来训练。我难以获取这个数据库，哪怕获取了电脑也存不下，哪怕存得下训练时间我也接受不了。考虑到这是大作业，老师不会只按结果给分，而更看重程序的原理、工作量。我于是决定用其他数据来代替论文中的1T数据，用论文中同样的方法来统计文字出错概率。

找数据又花费了我很多工夫。我需要一个包含文字错误的语料，标注可有可无。我找来找去，总算在Github上一个比较出名的中文语料库中找到了一个台湾论坛聊天语料。虽然数据量不够，但勉强可以在这个语料库上执行文章中的训练算法了。

在统计文字出错概率之前，需要先用一个分词语料库训练出一个语言模型。我用的是比较常用的北大人民日报语料。但是，所有的中文拼写检查都是基于繁体字的，这就出现了一个问题：语言模型仅用了简体语料，无法处理繁体字。我决定把人民日报语料转换成繁体。一开始我用word转换，一按简繁转换按钮程序就卡死了。我又去网上随便下了一个简繁转换程序。这个程序的转换速度倒是很快，但我发现转换结果有一些问题：一个简体字可能对应多个繁体字，比如简体”后“字有”(皇)后“，”後(面)“这两个对应的繁体字，而转换程序只能进行一对一的转换。最后我在Github上找了一个运用了NLP技术的简繁体转换程序，总算得到了一个能用的繁体语料库了。

至此，我总算解决了所有的问题，准备好了编程所需的所有资源。剩下的编程、写实验报告的工作就没什么值得讲的了。

这次项目对我来说意义很大。倒不是说我在这个项目中学到了多少NLP知识，或者说留下了一段比较有趣的工作过程。我在这次项目中，最大的收获是初步掌握了检索文献并了解一个领域前沿知识的能力。我第一次了解了什么是综述，虽然这篇综述放在博客上，并不是按照标准的论文格式写的。我第一次读懂论文并实现了论文的算法。我之前一直觉得论文都很高深，涉及的方法非常复杂。多亏这几篇论文算法相对来说比较简单，给了我读论文的自信。在这个项目之后，我还碰到了很多需要自主学习领域前沿知识的项目。得益于这次项目的经验，我能够快速搜索到一篇好的综述文章并开展学习，高效率地完成对相关领域前沿知识的了解。

以下项目介绍绝大多数内容摘自实验报告。

中文拼写检查器（基于图网格，C++实现）

Github链接

https://github.com/SingleZombie/Simple-Chinese-Spelling-Checker

任务定义

  1. 找出一个句子中出错字的位置。

  2. 把出错的字修改成正确的字。

实现思路

实现思路和参考论文[3]大致相同。

对一个句子同时进行分词和纠错。假设每个字都可能出错。列出每个字的混淆字，这样对于整个句子来说，就形成了一个图格。分词和纠错等于在图格上找一条权值最大的路径。在这个图格中，每个字都看成一个节点。如果相邻的几个字可能构成一个词（无论这些字是否来自混淆集），就把这个词当成一个节点。两个节点的之间的权值就是转移的概率。

节点间的概率来自两个部分，一部分是语言模型概率（判断分词是否正确），一部分是字会出错的概率（判断修改的是否正确）。

对于语言模型，使用大作业一的二元语言模型，即基于人民日报语料库构建的模型。每次可以查询前后两个词一起出现的概率。

对于字会出错的概率，使用互联网文本来训练模型。对文本的每句话进行分词（分词采用大作业一的算法），之后考虑任意连续的两个或三个词，试图用混淆集的字替换其中的一个字（混淆集来自汉语的同音字、近音字），看看这两个或三个词能否合并成一个词。如果能，则把改之前和改之后的字符串作为一个pair储存。这些pair表示候选错误串。

统计所有pair的情况。把每个pair的出错字符串的前面一个词看成一个向量（向量的维度是上一个字符串，向量该维度的值是上一个字符串出现次数）。同时，用同样方法统计pair的正确字符串的前一个向量，这个向量可以从语言模型中获得。对两个向量求cos值，该值可以表示两个向量的相似程度。若这个cos值大于一个人工设置的阈值，则认为错误串和正确串上文相同，这个串确实出错了。之后，把串中出错的字找到，统计一个字出错变成另一个字的个数。

有了一个字出错成另一个字的个数，就可以统计一个字出错成另一个字的概率。一个字符串出错变成另一个字符串的概率，就是每个字出错成对应字概率的乘积。

节点的转移权值由以上两部分概率相乘得到。

由于图格构成一个DAG，且已经拓扑排序好，可以用DP找最大权值的路。寻找每一个可能的词以构成节点时，在词典的字典树上查找以减少时间开销。找到最大权值的路后倒序得到每一个节点，出错纠错结果。

程序设计与实现

数据预处理

由于测试集是繁体，词典用的分词语料、汉语词典被转换成了繁体。

混淆集文本预处理模块如下所示：

由于原始数据是json型的，数据先被提取出来，保存到txt文件里。（这一步程序里没有，只保留了最后的txt文件）

之后main函数调用outputConfusionPair进行候选串的获取。选取候选串的主要算法函数存在ConfusionTrainer.cpp文件中。其算法先对句子进行分词，再每次找相邻的两个、三个词，尝试从完整的混淆集（来自于汉语的同音、近音字）替换每个字，看这两个、三个词能否构成一个词典里的词。其具体算法和后面的替换算法类似，都是在词典的字典树上查找。最终这一步会输出三元组（上一个词，可能出错的词，正确的词）。

之后main函数调用calPotentialConfusionPair，LanguageModel统计上一步得到的三元组，根据出现次数计算输出出混淆对概率信息，这个信息文件里包含每一个混淆对的cos值，混淆对的出现次数。cos值是把对可能错误的词的上一个词的出现次数乘上语言模型中正确的词也是这个上一个词的出现次数再相加，最后除以正确的词上一个词的总个数，除以可能错误词上一个词的总个数。和向量求cos值方法相同。

最后confusionSet根据cos值和混淆对出现次数筛选掉一些不合法的混淆对（实现时cos值>=0.2，出现次数>=2），之后对合法的混淆对统计是哪个字出错了，最后得到一个字错误成另一个字的次数。根据一个字错成另一个字的个数，可以得到一个字错成另一个字的概率，具体公式是：

ch是正确字符，ch'是某一个被混淆的字符。S(ch)指字符ch的混淆集。由于样本数据较小，这里用了加1的数据平滑。

由于最后一步预处理很快，这一步的结果没有写进文件，在程序执行的时候才会处理。

程序执行

最终可执行程序的结构如下：

词典读入分词语料库，得到二元语法模型，同时所有词构成一个字典树。混淆集读入每个字所有可能的混淆字，以及每个混淆字的概率。语言模型综合二者的信息。算法模块提供了所有核心算法。主程序对整个程序的过程进行控制。

程序开始运行后，会先读入分词语料库，以及一个成语库，二者会插入进语言模型的词典。词典在内部建一棵字典树以维护所有词语，并统计相邻两个词出现概率。之后主程序会读入一个有概率的混淆集。最后调用Language Mode再调用NLPAlgorithm文件中的算法对测试集进行纠错并评价结果。

CSCAlgorithm.cpp包含本程序主要的纠错算法。主要函数的算法流程图如下：

分词函数先定义了节点二维数组vertice[i][j],从字符串的每个位置开始进行DFS。DFS在递归过程中，会尝试替换每一个字符，并且在词典的字典树上移动。如果字典树上没这条路径，即当前节点号crtTrieIndex==0，就可以对DFS进行剪枝。通过DFS可以生成图网格中所有可能的词节点，并且得到每一节点的最大概率。通过最后一个节点可以反向遍历出结果字符串。

具体节点概率（准确来说是权值）计算公式如下：

word指当前词，preword是上一词。$P_{LM}$是语言模型的概率，直接调用二元语法模型的函数就可以计算。$P_{err}$为出错概率，其公式为：

公式就是把出错词中每一个出错字的出错概率累乘。其中：

根据这个字是否出错，这个概率分两部分来计算。其中perr是一个超参数，表示某个字出错的概率。如果这个字确实是错的字，就去之前的错误模型里寻找概率。程序中这个值是CHARACTER_ERROR_P = 0.0003

程序结果

使用SIGHAN Bake-off 2013作为测试集。其中subtask1用于错误查找，subtask2用于错误纠正。根据测试集论文的描述，评价标准有以下几项：

错误查找：

  • FAR（错误识别率）：没有笔误却被识别为有笔误的句子数/没有笔误的句子总数

  • DA（识别精准率）：正确识别是否有笔误的句子数（不管有没有笔误）/句子总数

  • DP（识别准确率）：识别有笔误的句子中正确的个数/识别有笔误的句子总数

  • DR（识别找回率）：识别有笔误的句子中正确的个数/有笔误的句子总数

  • DF1（识别F1值）：2 * DP * DR/ (DP + DR)

  • ELA（错误位置精准率）：位置识别正确的句子（不管有没有笔误）/句子总数

  • ELP（错误位置准确率）：正确识别出笔误所在位置的句子/识别有笔误的句子总数

  • ELR（错误位置召回率）：正确识别出笔误所在位置的句子/有笔误的句子总数

  • ELF1（错误位置准确率）：2 * ELP * ELR / (ELP+ELR)

错误纠正：

  • LA位置精确率：识别出笔误位置的句子／总的句子

  • CA修改精确率：修改正确的句子／句子总数

  • CP修改准确率：修改正确的句子／修改过的句子

我的结果：

FAR:16.5714% DA:70.0000% DP:50.0000% DR:38.6667% DF1:43.6090%

ELA:63.7000% ELP:22.8448% ELR:17.6667% ELF1:19.9248%

LA:16.3000% CA:15.2000% CP:37.1638%

使用的公共资源

语言模型

北大人民日报语料库

新华成语词典：https://github.com/pwxcoo/chinese-xinhua

混淆集

原始混淆集：SIGHAN2013 ConfusionSet

训练用互联网语料：https://github.com/zake7749/Gossiping-Chinese-Corpus

工具

简体繁体转换程序：https://github.com/hankcs/HanLP

测试集

SIGHAN2013 finalTest

程序实用说明

输入文件的格式必须是Unicode BE。

txt文件描述：

ChatData.txt 混淆集训练用的互联网原始文本

ChatDataConfusionSet.txt 互联网文本中提取的候选混淆对

ConfusionInfo.txt 候选混淆对筛选出的词对cos值和出现次数

FinalTest.txt SIGHAN测试集subtask2

FinalTest_Result.txt 程序跑出来的subtask2结果

FinalTest_Truth.txt subtask2正确答案

FinalTest_SubTask1.txt SIGHAN 测试集 subtask1

FinalTest_SubTask1_result.txt 程序跑出来的subtask1结果

FinalTest_SubTask1_Truth.txt subtask1正确答案

IdiomDictionary.txt 成语词典

SimilarPronunciation.txt SIGHAN原始混淆集

SimilarShape.txt SIGHAN原始混淆集

TrainDataCht.txt 北大分词语料

参考文献

[1]. Shih-Hung Wu, Chao-Lin Liu, and Lung-Hao Lee (2013). Chinese Spelling Check Evaluation at SIGHAN Bake-off 2013. Proceedings of the 7th SIGHAN Workshop on Chinese Language Processing (SIGHAN’13), Nagoya, Japan, 14 October, 2013, pp. 35-42.

[2]. Chao-Lin Liu, Min-Hua Lai, Kan-Wen Tien, Yi-Hsuan Chuang, Shih-Hung Wu, and Chia-Ying Lee. Visually and Phonologically similar characters in incorrect Chinese Words: analyses, Identification, and Applications. ACM Transactions on Asian Language Information Processing, 10(2), 10:1-39.

[3]. Hsieh Y M, Bai M H, Huang S L, et al. Correcting Chinese spelling errors with word lattice decoding[J]. ACM Transactions on Asian and Low-Resource Language Information Processing (TALLIP), 2015, 14(4): 18.

[4]. hqc888688.中文输入纠错任务整理[EB/OL].https://blog.csdn.net/hqc888688/article/details/74858126,2017-07-09.

Posted on In ,

由于套暑研要准备一个简单的简历，我打算总结一下之前做的一些项目，发博客并上传Github。虽然我能明确地知道，做这些事情对看我简历的人来说毫无影响，但写博客记录自己人生是我自己想做的一件事。

做之前这些项目的时候我都没有去写博客，当时我还没有想好博客该怎么用。以后应该不会出现这些情况了。只要是有一些规模的项目，我都会把从技能学习到编程实现的整个过程发到博客上。

写这个项目是因为我图形学的导师在写一本图形学教程书，其中有一些习题要附上源代码。他让我帮忙实现真实感渲染章节的习题，顺便学习一下这一章的内容。

由于是项目总结，内容会十分简略。

CPU光线追踪C++OpenGL实现

Github地址

https://github.com/SingleZombie/Ray-Tracing-OpenGL

编译项目需要包含一些额外的文件，具体的要求见Github里的readme。

任务定义

实现一个使用光线追踪技术渲染的场景：一个带反射的球放在黑白相间的棋盘格地面上。

知识背景

光线追踪的思想比较简单：以摄像机为端点，向屏幕上每一个像素的处发射一条光线。光线接触到第一个物体后，既会接收物体自身的颜色，还会进行反射和折射，产生更多的光线。这些后续的反射、折射以及物体本身的颜色都会对最开始的这条光线产生贡献。这条光线的强度就能转化成产生光线的像素的颜色值。

从实现的角度来看，光线追踪就是一个递归的过程。为了计算一条光线的强度，还要计算它反射光和折射光的强度。

由于光每次都可以反射和折射，光线与物体的碰撞次数与递归层数成指数级增长，并且客观上光线的反射和折射是无穷无尽的，光线追踪算法需要一些停止递归的规则。递归层数过多、光没碰到物体都能让算法中止。不过即使有了一些限制规则，不经过优化的光线追踪算法运行得依然很慢。

设计

当时我写的伪代码如下：（不过是写完了程序再写的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// plane是一个平面结构，分量有平面上任意一点、平面法向量、材质
// ball是一个球体结构，分量有中心点、半径、材质
// scene是一个场景类，存储了平面、球等物体，存储了光照信息，可以进行光线追踪计算
// pixelPos表示屏幕上某个像素在世界坐标的位置
// ray是一个光线结构，表示从观察点射向pixelPos的一条光线
// color(i, j)表示屏幕坐标为(i, j)处的颜色
// CreatePlane(p, n)用平面上一点p和法向量n构造平面
// CreateSphere(p, r)用点p和半径r构造球体
// pixelToWorldPos(i, j)计算屏幕(i, j)处像素在世界坐标的位置
// Ray(p, d)用点p和方向向量d构造光线

plane = CreatePlane(vec3(0, 0, 0), vec3(0, 1, 0));
plane.setMaterial(checkMaterial);
ball = CreateSphere(vec3(0, 1, 0), 1);
ball.setMaterial(ballMaterial);
scene.add(plane);
scene.add(ball);

for i = 1:640
	for j = 1:480
		pixelPos = pixelToWorldPos(i, j);
		ray = Ray(viewPos, pixelPos – viewPos);
		color(i, j) = scene.traceRay(ray, 0);
	end
end

// traceRay(ray, recursionTime)接收参数当前光线ray,当前递归次数recursionTime,递归计算并返回光照强度light
// MAX_RECURSION_TIME为常量最大递归次数，递归超过次次数函数会停止执行
// intersectedPoint表示当前光线照射到的第一个物体的照射点
// intersectedEntity表示当前光线照射到的第一个物体
// normal表示照射点处物体的法向量
// material是一个材质结构，表示照射点处物体的材质，分量有着色比例kShade、反射光比例kReflect、折射光比例kRefract。
// light是表示当前点的光照强度
// reflectDir表示光线经照射点反射后光的方向
// refractDir表示光线经照射点折射后光的方向
// getIntersection(ray)是场景scene的函数，用于计算场景中光线与物体的交点以及照射到的物体
// shade(entity, fragPos, ray)接收参数物体、着色点、光线，利用Phong等局部着色模型计算出该点的光强

function traceRay(ray, recursionTime)
	if (recursionTime >= MAX_RECURSION_TIME) then
		return;
	end
	(intersectedPoint, intersectedEntity) = getIntersection(ray)
	if (intersectedEntity == NULL) then
		return;
end
	normal = intersectedEntity.calNormal(intersectedPoint);
	material = intersectedEntity.calMaterial(intersectedPoint);
	light = material.kShade * 
shade(intersectedEntity, intersectedPoint, ray);
	if (material.kReflect > 0) then
reflectDir = reflect(ray.direcion, normal);
		light += material.kReflect * 
traceRay(Ray(intersectedPoint, reflectDir), recursionTime + 1);
	end
	if (material.kRefract > 0) then
		if (intersectedEntity.rayEnterEntity(ray)) then
			refractDir = 
refract(ray.direction, -normal, material.index, airIndex);
else 
			refractDir = 
refract(ray.direction, normal, airIndex, material.index);
end
		light += material.kRefract * 
traceRay(Ray(intersectedPoint, refractDir), recursionTime + 1);
	end
	return light;
end

实现方法

从软件工程的角度来看，根据光线追踪的描述，很快可以得到编程所涉及的对象：射线（光线）、物体、光源、场景。物体、光源属于场景，每帧从视点向所有像素发出光线与物体判断相交，计算颜色时要用到光源、物体参数。再具体来说，光源包含颜色等参数，物体包含自身的几何信息及材质信息。有了类和类间关系，代码结构很容易写出来。

从算法实现的角度来看，只要理解了光线追踪算法，看懂了上面的伪代码，很容易写出对应的代码。

由于光线追踪算法的像素值完全来自射线和物体的交，物体可以以解析式的形式定义。比如球只需要定义一个中心点位置，一个半径。在判断射线和物体的交时，求解一个射线的参数方程即可。

结果

Posted on In ,

SLICAP图像分割C++实现

代码仓库

https://github.com/SingleZombie/SLICAP-image-segmentation-cpp

需求分析

输入一幅图像，输入图像中每个像素的分类。比如产生以下的效果：

Requirement

由于我的软件工程天赋过于高超，加上用户、产品经理、程序员都是我自己，因此分析阶段的功能建模部分就略过了。

技能学习

算法原理

见上一篇博客

概要设计

学完算法，准备开始写程序后，我的脑中立刻就浮现了以下的程序结构图：

design1

和以往一样，主函数分成预处理、执行操作、输出处理三个模块。执行操作可以分成生成超像素和利用超像素进行图像分割，在用超像素模块分割模块中会利用到AP聚类算法。

这次程序的两个主要模块非常清晰：用SLIC生成超像素的模块和用AP聚类的模块。两个模块独立性高，且具有先后关系。应该逐模块进行开发，每个模块开发完成后进行单元测试，确认模块工作正常后再进行后续的开发。同时，由于项目时间十分紧张，我还需要采用敏捷开发，不浪费一分一秒在无谓的写文档上。

详细设计

虽然划分模块用的是结构化设计的思想，但我还是喜欢设计类并进行面向对象编程。

超像素生成模块

时间紧张，不画UML图了，直接用文字表达思想，之后直接写代码。

首先要有一个SuperPixels类。该类用于在超像素生成和超像素图像分割模块间传递信息。该类存了一个图像矩阵、一个存储每个像素所述超像素类的数组、一个存储每个超像素信息（平均颜色向量）的数组。外部操作有根据图像矩阵创建新对象。由于算法对数据操作较多，该类可以被看成一个“结构”，标记数组、超像素信息是透明的。超像素信息用SuperPixel结构表示，该结构就是一个五维量（颜色和坐标）加一个像素数。

SuperPixelsGenerator提供生成超像素的算法，与一个SuperPixels关联，被处理模块调用。该类要存储一个图像矩阵，超像素期望的个数superPixelCount, 颜色距离参数colorDisM，最大迭代次数maxIterTime，计算一个期望距离expectedDis。我按算法流程顺序来设计每一个部分。设计时参考了这篇博客。

首先我需要一个RGB和LAB互相转换的函数，供SuperPixelsGenerator调用。这个函数应该单独写在一个模块中。上面那篇博客的作者还写了一篇RGB转LAB的博客。但由于自己实现比较复杂，我打算直接用OpenCV自带的方法转换。

std::vector SuperPixelsGenerator::computeGradient()，计算图像每一点的梯度。

void SuperPixelsGenerator::initSuperPixelsCenter()调用computeGradient()来计算初始的超像素中心。

void SuperPixelsGenerator::updateEachPixel()更新每个像素的标记（类别）。

void SuperPixelsGenerator::updateSuperPixelsCenter()更新超像素中心为平均值。

void SuperPixelsGenerator::enforceConnectivity()对最终的标记进行强制连续性的处理。

超像素聚类模块

我先完成AP算法模块的设计，再完成调用AP算法模块的设计。

AP算法应该可以对任何形式的数据进行。因此，AP算法应该写成一个模板函数。

AP算法接收一个数据间相似二元关系的矩阵，输出一个标记表，表示每一个数据的数据中心是哪个数据。唯一一个可调参数是更新率$\lambda$。我本来想写一个和STL风格类似的模板函数，结果发现我忘记了怎么声明一个参数的指针或迭代器参数。再进一步思考，不管什么类型的数据，都可以用一个整数索引来表示，相似度可以直接存在一个数组里。那么我就不需要使用模板函数了。最终，函数声明写成了这样：

1
std::vector<int> apClustering(const std::vector<int>& similarity, unsigned dataCount,double lambda = 0.5)

再思考一下程序设计细节。对于每对数据，要计算除某点之外的某值的最大值，这个可以通过记录每对点某值的最大值和次大值实现（打ACM做树形dp的时候实现了好多遍了）。另外，每对数据间还需要一个除了某两点以外的累计值，这个直接存一个累计值，用的时候减掉那两个不要的值就可以了。

这个算法直接写在一个函数里没什么问题。要让代码模块性更好的话，可以把$r,a$矩阵的更新分别写一个函数。

超像素聚类算法单独写一个类。该类初始化时接收算法权值参数。调用该类的clustering函数可以对一个超像素集合进行聚类，直接返回AP聚类的标记数组。该函数调用一个函数计算相似度，在调用AP算法返回结果。

1
2
3
SuperPixelClusteringAlgorithm::SuperPixelClusteringAlgorithm(int wl = 3, int wa = 10, int wb = 10);
std::vector<int> SuperPixelClusteringAlgorithm::clustering(const SuperPixel&);
std::vector<int> SuperPixelClusteringAlgorithm::getSimilarity(const SuperPixel&);

程序设计及性能优化

由于时间紧、算法对数据操作量复杂而软件流程复杂性低，本次程序我写得十分“暴力”，很多地方都没有进行模块化、封装。

超像素生成模块

我用四个半小时的实际工作时间完成了看似正确的超像素生成模块。在三种参数下的生成结果如下：（鼠标放到图片上可以看到参数信息）

K = 500 m = 10 iter = 2

K = 500 m = 5 iter = 2

K = 500 m = 10 iter = 4

但是，程序的性能非常差。明明我已经有意识地降低时间和空间使用程度，但程序依然要20多秒才能完成4次迭代的生成算法（生成上面的第三幅图）。

凭借着上次软件工程项目的经验，我使用VS的性能分析工具来改进程序，结果如下：

opt1-1

大部分时间都是画在迭代函数上。令我惊讶的是，几乎所有时间都浪费在了这个计算五维量距离的函数上。

仔细看了一遍网上实现代码和论文中的算法，发现我对算法的理解错了！每次是搜索超像素中心附近的$2S\times2S$个像素，不是对每个像素进行搜索。我立马修改了上一篇博客和代码。

这下算法的结果也正常了，性能也正常了。程序1.7秒可以完成4次迭代、500个超像素、图片大小510X385的超像素生成算法。哪怕不经过任何优化，这个性能也能满足一般的要求。调试的时候不会浪费太多时间，做为作业提交也十分足够。有机会的话，我还是会优化一下代码。

在算法正确的基础上，我又做了3次实验：

K = 500 m = 10 iter = 4

K = 500 m = 5 iter = 4

K = 500 m = 10 iter = 10

目前开发调试外加吹牛的时间共计五个半小时。

超像素聚类模块

这个模块实现起来并不复杂，但我还是浪费了很多时间在调试上。

一开始，我发现我没有正确理解AP算法，没有对相似度矩阵对角线上的值进行特殊处理。我把对角线的值设为平均值后，还是发现聚类算法只会把每一块的数据中心划成自己。由于图片不好调试，我构造了6个点相似度矩阵进行算法调试，其中每三个点有一个很明确的数据中心。算法迟迟得不到正确结果。我浪费了大量时间在代码比对上。突然，我一气之下修改了AP算法的循环停止条件，让它迭代进行100次，结果竟然正常了。我发现在AP算法迭代的过程中，每个点的数据中心可能会固定一段时间，但实际上两个矩阵的值还没有收敛。我把循环停止条件改成了数据中心连续5次迭代都不变才解决AP算法的收敛问题。可是，我把数据从6个点换成了原图像，算法还是进行失败。我又偶然间把计算相似度矩阵对角线的公式去掉了SLICAP论文中提到的比例系数，算法竟然正常工作了。不知道是不是我没有认真看那篇论文，我觉得那篇论文太坑人了，加上比例系数后算法完全工作不了，我还以为是自己写错了。

和设计的一样SuperPixelClusteringAlgorithm类只负责相似度计算和算法调用，AP算法的细节在APClustering中。

程序设计真的没什么可以说的。假设有$N$个数据，迭代$I$次，那么AP算法时间复杂度是$O(IN^2)$，空间复杂度$O(N^2)$。稍微优化一下求最大值和求和的过程就能把看似$O(N^3)$的单次迭代变成$O(N^2)$。

图片显示模块

我打算显示3幅图片：超像素分割结果、超像素聚类结果、图片分割处理结果。

理论上需要一个模块来专门处理输出图片的处理。由于时间不够，我也很懒，只把超像素聚类结果生成函数放到了单独的文件里。超像素分割结果图像放到了超像素类里，图像分割处理结果直接放到了main函数里。这样写程序是非常不好的，我会在之后的版本中修改。

命令行参数模块

理论上，所有的参数都是可以调整的，而且程序可以在不关闭的情况下保存之前的参数设定，循环处理图片。做为一个完整的软件来说，应该提供这些丰富的功能。但我暂时没有写，我写的东西暂时只能算一个程序。

最终结果

（我也忘了当时参数是什么了，但这绝对是程序生成出来的）

p1 tag

p1 result

p2 tag

p2 result

感想

我觉得自己很帅。在一天之内不仅实现了图像分割程序的功能，而且凭借着强大的心理抗挫折能力，没有被烦人的BUG击溃，最终站到了胜利的高点。当我回首过去，看着一条条充满荆棘的路，看着我踩的一个个坑，我感到一丝心酸；但当我俯视大地，看着程序能够产生较好的图像分割结果时，我又感到苦尽甘来，心旷神怡。

更新记录

20.2.1

  • 上传博客

Posted on In ,

本文先对论文“SLIC Superpixels Compared to State-of-the-Art Superpixel Methods”做一个论文阅读报告，再稍微介绍一下其他论文，介绍算法原理。下一篇文章会按之前小作业的格式写技能学习、编程过程、代码结构介绍、实验结果分析与感想。

SLIC论文阅读报告

在搜索引擎中可以找到很多分析此论文的中文博客。比如这篇博客分析了代码实现原理。论文中的代码实现网页我怎么都打不开，只能从这篇博客里来获取代码实现的细节。另一篇博客分析了论文代码实现上的性能缺陷。直接看一些中文博客的分析就能对论文的方法理解个大概，再看论文的时候就会比较顺利。

内容梗概

本文对当时的5种超像素方法进行了比较，并提出了一种simple linear iterative clustering (SLIC)(简单线性迭代聚类)的生成超像素的算法。

superpixel

超像素就是一些像素的集合。超像素的边缘要和图像中物体边缘大致符合。一般获取超像素是其他数字图像处理的预处理工作。图像分割就可以先进行超像素预处理，把每个超像素当成原来算法中的像素来处理，减少数据规模。

算法流程

算法整体上接受一个参数$k$，表示期望的超像素的个数。算法输出$k$个超像素中心以及每个像素属于哪个超像素。

每个像素被看成一个五维量$(l,a,b,x,y)$，前三维是LAB颜色空间信息，后两维是像素位置信息。算法均匀地初始化$k$个超像素中心，并计算超像素间距$S=\sqrt{N/k}$（$N$是像素个数）。之后遍历所有像素中心，找到每个像素周围$2S\times2S$范围内在一种距离度量下”最近“的超像素中心。每个像素”分类“完成后，把一类像素的五维平均值当成新的超像素中心，并以计算本轮分类方式和上一轮的残差。算法不断重复上述过程直到残差收敛至0。

以上只是一个算法的大致描述，算法的具体细节如下：

距离度量方式

如果单纯地把两个像素的距离定义成五维量的距离，就会出现一个问题：像素距离给整体距离的影响是不确定的。如果要求的$k$值较小，每个像素离超像素中心的距离较大，那么像素距离就会给整体的距离带来更大的影响。为了让像素距离和颜色距离对距离的影响权重更为平衡，文章提出了如下的距离度量方式：

其中$i,j$表示两个进行距离比较的像素，$N_c,N_s$是用于标准化颜色距离和像素距离的量。

文章取 $N_s = S=\sqrt{N/k} $，$N_c$直接定义为一个常数$m$。文章建议$m$取$[1,40]$。现在距离定义成了如下形式：

实际实现时出于方便，距离用以下公式计算：

另外，当图片的形式发生变化时，公式可以很方便地修改。如果图片是灰度图，那么颜色度量只需要考虑灰度之间的差就行了；如果不是图片而是三维体素，那么只需要把空间距离加上$z$分量。

保证超像素连续性

由于像素分类的时候除了位置的相似性外，还考虑了颜色的相似性，这样会出现一些问题：一个靠左的像素，可能属于右边像素中心；一个靠右的像素，可能属于左边像素中心。这样的话同类的像素可能被另一类的像素切成了两块，在图像上并不连续。

为了强制同一类超像素连通，算法在迭代结束后又对超像素进行了处理。算法从上到下，从左到右尝试搜索未标记的像素。对正在搜索的像素，把其四邻域中与它属于同一个旧超像素的像素加入搜索队列，并标记其和当前搜索像素属于同一个新超像素。当前这片新超像素搜索结束后，若新超像素总数少于期望超像素大小的一半，则把当前超像素的标记改成上一个新超像素的标记。上一个新超像素是当前新超像素搜索起点四邻域中的一个新超像素。

初始超像素中心优化

初始的超像素中心如果处于梯度比较大的点的话，可能会影响算法之后的表现。

该算法实现时，计算每个初步选择的超像素中心的$3\times3$邻域的梯度，把梯度最小的像素作为最终的初始超像素中心。

梯度的计算是$x,y$方向上梯度之和。$x$方向梯度是左右两个像素颜色向量的差平方和，$y$方向梯度是上下两个像素颜色向量的差平方和。

默认参数

由于残差收敛很快，算法默认迭代10次。这样残差可以不用计算了。

颜色距离参数$m$固定为10。

基于超像素的图像分割

仅获得了图像的超像素还不够，还需要一些其他的方法来做图像分割。我又去找了一些基于超像素的图像分割论文。

我浏览了以下论文：

[1] Li Z, Wu X M, Chang S F. Segmentation using superpixels: A bipartite graph partitioning approach[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2012: 789-796.

[2] Zhou B. Image segmentation using SLIC superpixels and affinity propagation clustering[J]. Int. J. Sci. Res, 2015, 4(4): 1525-1529.

[1]论文本身质量较高，且没有使用深度学习的方法。论文提出了一种基于超像素和二分图分割的图像分割方法，需要输入类别数$k$，输出图像分割结果。我一开始看到了标题中的二分图，以为图像分割会被转换成一个可以用我十分熟悉的二分图算法解决的问题。但是文章莫名其妙地把问题变成了一个我很陌生的二分图分割的问题。我既没有从文章不清晰的叙述中理解问题转换的原理，也不愿去学一个看起来比较复杂的二分图分割算法。所以最后放弃了实现这篇论文的方法。

在Google上搜索”superpixel based segemenataion”或”image segmentation using superpixel”，都能搜出这个网站。该网站的作者实现了一个基于超像素的图像分割算法，其算法来自论文[2]。论文[2]非常直接地把SLIC和AP聚类两个算法拼接起来，得到了一种基于超像素和聚类的图像分割算法，该算法不用指定类别数。正好，我觉得超像素这个预处理已经对图像分割帮助很大了，只需要一个简单的超像素分类算法即可。我最终决定学习论文[2]的方法。

学论文[2]不应该去看那篇论文，而应该去看AP聚类算法的论文Clustering by Passing Messages Between Data Points。这种聚类算法比较有名气，搜索引擎上可以找到不少分析此算法的中文内容。

AP算法需要提供数据间的相似度这一二元关系矩阵，输出每个数据点属于的数据中心。AP算法的思想我没有理解，但其流程十分简单：算法构建了两个关系矩阵$r，a$，用以描述某个点适合作为另一个但数据中心的程度。算法用两个公式来更新这两个关系矩阵直至矩阵收敛。特别地，为了防止数值上的问题，算法引入了一个更新系数$\lambda$，每次保留$\lambda$倍的上一轮值，加上$(1 - \lambda)$倍更新值。这个比例系数在数值算法中非常常见，有点像梯度下降中的学习率。

如果我把AP算法理解了，会写一篇博客来详细介绍这一算法。

把AP算法运用在图像分割中，只需要定义图像任意两个超像素间的相似度就行了。论文[2]的主要贡献也就是定义相似度。论文[2]比较了3种相似度定义方式，最终选择了效果最好，也最简单的一种定义方式：相似度定义为负带权颜色向量差平方和，即：

其中$s(i,j)$表示超像素$i,j$间相似度，$L,a,b$是超像素平均LAB颜色空间颜色向量分量。

论文中超像素数$K=600$，超像素颜色距离参数$m=20$，颜色权值$w_l=3,w_a=10,w_b=10$。理论上这些参数都是可以调的，甚至相似度的定义参数也是可以调的。

Posted on In ,

我总算找到了博客的正确用法：给自己增加做事情的动力。

寒假回家后，我整个人变得很懒，这个学期最后一门课程的大作业也迟迟没有做完。恰好我发现，自从我把博客链接放到了社交媒体上后，有同学看了我的博客。让别人看到自己“作品”的感觉还是很好的。我打算用写博客的方式来更好地完成作业。

本文按照作业的要求，分为论文概要、代码模块分析、实验结果（使用自己的数据）三个部分。当然，由于我在博客里写东西比较随意，我提交的作业报告肯定会在这篇博客的基础上有所修改。

论文概要

问题定义

本文解决的是一个非常经典的问题：如何恢复一张被模糊和添加噪声的图片。即假设模糊矩阵是$K$,原图像是$u$，噪声是$N$,模糊图像是$g$。那么$g = Ku+N$。现在我们只知道$g$，如何得到$u$。

更具体地，本文介绍的是盲去模糊，即不知道模糊卷积核的情况下，应该如何恢复模糊图像。我上次写的第二个小作业解决的是类似的去模糊问题，但那次问题是一个非盲去模糊，即卷积核已知。

文章贡献

求未知模糊卷积核的问题可以被转换成一个优化问题，即求解某一个损失函数的最小值。文章主要的贡献是提出了一种在损失函数中添加正则化的方法，并且围绕这种方法提供了一套完整的去模糊算法。

方法思想

求解模糊卷积核的优化问题有很多的局部最优解。为了获取一个更好的解，需要加入一些正则化项。正则化项似乎可以用在所有的优化问题里，来避免一些局部最优解。但正则化项的原理我一直都不是很理解，感觉这就是一个被人工设置出来的东西，没有比较清晰的理论依据。把一个参数的正则化项加入优化的损失函数，其直观意义就是让参数不能过大。

在去模糊问题中优化问题中，一般使用的是复原图像的高频图像（后面会详细介绍这个是什么东西）的第一范式（每个分量的和）做为正则化项，加入到需要最小化的损失函数中。该文章发现，噪声增加能让第一范式项也增加，但是模糊却能减少第一范式项。如果单纯地把这一项放进优化目标里，可能得不到好的去模糊效果。文章发现，如果把第一范式和第二范式（每个分量平方和的平方根）的比值做为正则化项的话，无论是模糊增加还是噪声增加，都会让这一项增加。那么，最小化这一项，就能达到同时减少模糊和噪声的效果了。

简而言之，这种新的正则化项较以往的方法，能更好地同时减少噪声和模糊。

算法流程

整体上来看，算法分两步：第一步使用新的优化函数估计出模糊卷积核，这样盲去模糊问题就变成了一个非盲去模糊问题；第二步使用以往的非盲去模糊方法得到去模糊结果。

模糊卷积核估计

卷积核估计是在图像的高频图像进行的。所谓高频图像，就是对图像求x方向的一阶导数和y方向的一阶导数得到的图像。用$y$来表示模糊图像的高频图像，$x$表示修复图像的高频图像，那么优化目标可以写成：

其中$k$是模糊卷积核，$\lambda,\phi$用来调节对应两项的权重。

解决这一优化问题的方法是对两个优化参数$x,k$进行轮流优化。即优化$x$时，假设$k$是一个常量；反之亦然。

更新$x$

此时，优化目标被简化成以下形式：

但这个函数依然是一个没有极点，比较难优化的一个函数。文章中发现，如果第二范式的值固定，即求解

$min_{x} \lambda||Kx-y||_2^2+{||x||_1}$这样一个优化目标的最小值的话，是有一个比较快的iterative shrinkage-thresholding algorithm(ISTA)算法的。

因此，更新$x$又可以分成两层：先在固定第二范式的分母的情况下，使用ISTA更新几次$x$；之后重新计算第二范式，这个大的过程又重复进行几次。

更新$k$

此时，优化目标被简化成以下形式：

这个问题也有现成的算法可以解决。文中用的是无约束的iterative re-weighted least squares (IRLS)算法。

文章中也指出，在实际运用的算法的时候，每次计算出卷积核后要把其中值较小的数直接设为0，以更好应对噪声。

多级卷积核更新优化

由于实际情况中，模糊卷积核可能很大。为了保证卷积核在较大时也能得到一个比较好的解，文章中使用了一种优化方法。该方法从粗到精地计算卷积核，即先假设卷积核很小，使用之前提到的算法计算出卷积核后，再把卷积核细分变大。

在实现时，文章把最开始的卷积核设为3X3，每次以$\sqrt{2}$ 的比例扩大卷积核。对每一层卷积核的更新，$x$和$k$都进行200次交替更新。新一层卷积核使用上一层卷积核的双线性插值得到。

图像恢复

图像恢复用的是Fast image deconvolution using hyper-laplacian priors这篇论文的非盲去模糊方法。该方法大致思想是最小化复原图像做模糊卷积的结果图像和退化图像之间的均方误差。由于非盲去模糊的非适定性较小，不需要再用这篇文章开始提到的第一范数和第二范数的比值做为正则化项。

方法拓展

之前的描述都假设模糊操作是通过一个卷积核来完成的。如果图像因为旋转而扭曲，也可以用类似的方法，只需要修改优化目标中的卷积那一项就行了，大致思想不变。

实验结果与评估

文章首先对Understanding and evaluating blind deconvolution algorithms中提出的4幅用8个大小不同的模糊卷积核得到的32个模糊图片进行去模糊操作，并且用这篇文章中提出的方式来评估去模糊的效果。具体来说，评估的方法是比较还原结果图像与真实图像的均方误差与以已知卷积核还原图像与真实图像的均方误差的比值。这个比值肯定是大于1的，反映的是模糊卷积核复原的效果。文章统计了错误比值的分布（图片错误比值为1、2、3…所占所有图片的百分比）。

文章把新提出的算法与之前的某两个算法进行了比较。

同时，文章还使用了一些现实中的模糊图片实例来进行去模糊。文章还对一些经过旋转扭曲的图像进行复原。这些复原的结果没有经过数据上的评估，但经肉眼观察，这些图像复原的效果还是很好的。

代码模块分析

整体层次

代码的模块调用层次如下：

  • test_blind_deconv_params(执行算法的函数版本)
  • test_blind_deconv（执行算法的脚本版本）
    • ms_blind_deconv（多级盲去模糊，主函数）
      • ss_blind_deconv（单级估计卷积核、原图像）
        • pcg_kernel_irls_conv（IRLS算法）
          • pcg_kernel_core_irls_conv（IRLS算法中计算一个公式中的值的函数）
      • fast_deconv_bregman（非盲去模糊算法）
        • solve_image_bregman（解决非盲去模糊中的优化问题的算法）
      • center_kernel_separate（把卷积核位置调整为居中）

算法接口test_blind_deconv

test_blind_deconv提供了一个对示例图片去模糊的脚本，而test_blind_deconv_params提供了一个接收文件名、模糊卷积核大小的去模糊函数。这两个文件里的内容相同。

算法接口仅仅调用了主去模糊函数ms_blind_deconv，并且默认了一些可调的参数（文件名或模糊图像矩阵，$\lambda$等参数，优化算法循环次数、非盲去模糊的参数等）。

多级盲去模糊主函数ms_blind_deconv

该函数接收文件名和参数结构，返回原图像、模糊图像、模糊卷积核、参数结构。

该函数描述整个算法的主要流程，在调用具体优化算法前对输入图像进行了繁琐的预处理，并最后把去模糊结果显示出来。

和论文中的描述算法流程一样，该函数先对数据预处理，再分级估计卷积核，每一级里先循环更新$x$，再调用IRLS算法更新$k$，求得最终估计模糊卷积核后使用非盲去模糊算法计算复原图像。

预处理部分大致干了以下事情：

  • 从文件或参数中读取图像矩阵
  • 更改图片的大小
  • gamma校正
  • RGB转灰度图
  • 计算各级卷积核大小

在每一级估计卷积核前，函数还获取初始化卷积核、图像（从上一级插值得来）、计算高频图像。

之后函数调用单级卷积核估计函数ss_blind_deconv。每次卷积核被计算出来后使用center_kernel_separate函数居中卷积核。

最后一级的卷积核被估计出来后，这个卷积核会被存下来。该卷积核用于调用非盲去模糊算法fast_deconv_bregman，最终可以得到去模糊的图像。

单级估计卷积核、原图像ss_blind_deconv

该函数接受模糊图像、初始化复原图像、初始化卷积核、优化函数参数、循环次数，输出复原图像核估计卷积核。

该函数先初始化变量，之后按照论文中的方法，在固定第二范式项的情况下使用ISTA来更新几次$x$，之后更新第二范式项。更新$x$后调用IRLS算法更新$k$。

pcg_kernel_irls_conv函数是IRLS算法。算法中又调用了pcg_kernel_core_irls_conv来计算公式中的一个值。

非盲去模糊算法fast_deconv_bregman

该算法在Fast image deconvolution using hyper-laplacian priors中被提出。算法把最小化损失函数中的可变参数加入x方向的高频图像和y方向的高频图像，在每一轮迭代中使用solve_image_bregman来计算可变参数的更新值。

实验结果

现有数据

使用自带的fishes.jpg

p1

p2

新数据

我使用第二次小作业的模糊图像作为输入，用test_blind_deconv_params("I_n.jpg",9)命令来执行算法。

p3

p4

p5

实际的模糊卷积核是一个高斯模糊卷积核。估计的卷积核与真实的卷积核十分接近。

Posted on In ,

我还剩软件工程这门课要考。这门课没留下真题，直接复习很难定下具体的目标。于是我决定还是用写复习笔记来复习，让复习的目的性更强，同时激发斗志，收获成就感。

软件工程这门课的性质十分特殊。这是一门几乎不涉及理论，却涉及工具的使用、大量的经验与人为设定的规则的一门课。讲得清楚一些，就是这门课几乎没有什么干货，应该更多地考察实践能力，而不是用靠着一张瞎记瞎理解就能回答的卷子来考察。但没办法，我纵使有着极为丰富的项目经验教训与软件工程方法实践心得，平时学这门课的时候也还算认真，考前还是不得不去做一下复习。

吐槽完了，来谈一下具体的复习策略。课本无效内容较多，每一章的有效内容量分布不均，最气人的是复习大纲和课本还对应不起来。没办法，我只能自己把这门课讲的内容分个类，针对每个类的内容集中复习。

从实际的编程方法来看，这门课讲了结构化编程和面向对象编程两种编程方式。这两种编程方式有着不一样的分析和设计方法、工具。因此，我会各用一篇文章来复习这两部分的方法和工具。此外，还有不少内容和具体的编程方法无关，比如软件测试、软件维护，这些内容我会用一篇文章来复习。还有一些比较细致的，略有理论性的东西，比如耦合的分类等内容，我单独用一篇文章来写这些理论知识。最后我对照复习大纲，扫干净剩下的知识点。

软件工程复习1：结构化编程

需求分析

结构化需求分析的核心的数据。围绕着数据，要建立三种模型：数据建模、功能建模、行为建模。三种模型有各自的建模工具，三种模型中涉及的概念会被统一写在数据字典中以方便查看。

数据建模

数据建模描述的是数据的静态信息。准确来说，是一个数据可以进一步被分解成哪些属性，以及一个数据和另一个数据的关系中出现的新属性。

数据建模使用的E-R图。矩形是实体，圆圈是实体的属性，菱形是实体间的关系。有关系的实体要写上是几对几关系。

E-R图在上学期学数据库的时候学了，我就不多加复习了。只要看了E-R图的一个例子，就能很快搞懂这个图的意义与使用方法。

功能建模

理论上来说，有了静态模型，剩下的应该是动态模型。我对剩下两种模型的理解是：功能模型是对数据整体处理方式的建模，行为建模是对数据局部具体处理方式的建模。

所有程序全部可以看成是一个输入转换成输出的过程。输入输出不仅是传统的数据，输入可能是鼠标的一次点击、键盘的一次输入；输出可能是屏幕窗口的一个变化。功能建模就是描述输入数据是怎么一步一步变成输出数据的。

数据流图（DFD）是常用的（考试考察的）功能建模工具。DFD按照自顶向下的思想，用多层图来逐步分解数据加工过程。顶层图只有一个数据加工过程，之后的1、2层图会把上一层的数据加工过程细分。

每一层中，圆圈表示数据加工；矩形表示外部的实体，也就是和数据交互的对象；封了半边口的矩形是数据库；箭头是数据流向，箭头上要有数据流名。

DFD有以下要求：

  • 父图和子图要平衡。具体来说，父图和子图的输入输出要一致。子图可以把父图的输入分解。
  • 数据变换部分要按次序编号

这种图看了一遍例子就能理解图的意思，但要自己画一画才能掌握画的方法。正常来说DFD至少要分解到第二层，但考试要求我们只画一层。为了复习，我来做一道例题。

</br>

例：银行活期现金存取款柜台业务软件系统。存款时，储户将存款金额及存折，交给银行柜台操作员；取款时，储户则直接将取款数额告知操作员，并递交存折。具体存取款过程如下：

(1) 存款处理

  • 清点现金，确认存款金额；
  • 输入帐号、存款金额；
  • 根据存款金额记录分户账及总账，并登记存折及打印凭条。

（2）取款处理

  • 输入帐号，取款金额；
  • 储户输入密码，系统核对密码并查询余额；
  • 若余额充足，根据取款金额记录分户账及总账，并由票据打印机打印登折数据和凭条数据。

</br>

要求：画出系统顶层和一层数据流图 。

老师给的参考答案：

DFD1

我第一遍的答案：

DFD2-1

DFD2-2

看了答案后修改的答案：

DFD2-3

先声明一下，这道题我们之前上课做了一遍，我不是第一次做。

首先先看一下顶层图，顶层图其实就是这个系统包含的范围，以及系统涉及的实体。把存折给操作员等行为并不是在软件中，因此不能放进软件系统里；打印机是一个独立的系统，不算在这个软件里面。所以最终顶层图画成了那个样子。我对顶层图答案没什么异议。

重点在一层图上。我这次第一遍画的时候，看到需求很明确地把软件的需求分成了存款和取款两个部分，所以我直接就分了两个数据变换模块，没有去管存取款的实现细节。讲道理，一层图不需要画那么细，这样画一样理论上就可以了。

但我看了答案之后，加入了一个信息记录模块。因为把修改分户账和总账在存款和取款中都出现了，单独拿出来也说得过去。

但是答案剩下的部分我就不能赞同了。首先是业务确认模块。需求只提到存款要确认，但没有提到取款要确认。虽然按常识来说存取款都是要确认操作的，但是这里需求没有给出，就不应该加进来。既然取款不需要确认，那么就不能写一个公共的业务确认模块。再来是查询余额模块。查询余额显然是属于取款的，这个应该属于实现细节，在一层图就写出来还早了一点。

老师上课的时候也跟我们说，由于只要求画一层图，这张图细节部分写得多了一些。按理来说，参考答案做的并不是很好。我觉得我第二遍的答案更好一些。甚至在实际实现的时候，我觉得第一遍的答案就够了，细节就应该在之后的图里显示出来。哪怕存取款有重合的部分，也可以在实现的时候进行模块复用。

我觉得这道题的最大启示不是一层图该如何分解，而是顶层图如何划分软件系统的边界的。我上课第一次画的时候就把递存折写进系统，而且没有画打印机，这些都是很明显的错误。当然我不知道考试的题会怎么出，应该把题目涉及的实体和数据变换模块找出来，把每一个重要的词都画进系统里应该就问题不大。

行为建模

前面也提到了，我觉得行为建模就是对更具体的数据变换过程进行建模。课本上介绍了两种建模方法：状态转换图（STD）和过程描述语言（PDL）或伪码语言（PL）。

状态转换图

正如其名，状态转换图描述了数据对象不同时刻的不同属性，以及在不同状态间的转换方式。

我先以个人经验讲一下状态转换图的必要性。我之前做游戏的时候，被一个逻辑搞得十分头疼：卡牌游戏中鼠标的控制逻辑。正常情况下，鼠标可以拖动卡牌，也可以放到敌人头上或者一个buff上查看具体信息。在拖一张卡的时候，卡移到我方头上或者对方头上就不能显示信息，而应该根据卡牌是否能对这个目标使用而高亮目标。拖手牌里的一张卡和拖场面上的一张卡的拖动状态还是不一样的。由于没有事先设计，这个逻辑写的我非常混乱。我一看到了状态转换图，就立刻知道了以后该怎么处理这种状态转换情况。课本上再栩栩如生的案例也不如一次个人的经历对我理解这个概念的帮助大。

状态转换图就类似自动机，是一个点和边构成的图。点是状态，边是转移条件。在STD中，黑点代表初态，带圈黑点表示终态，大圆角矩形框表示中间状态。中间状态要写上状态名、状态变量、状态此时的活动。

状态转移图我还没画过，虽然考试不一定会考怎么画，但我还是想练习一下。

我画的时候发现visio的状态图和课本上的不太一样，就不打算画了。

加工逻辑

加工逻辑就是描述流程或算法。工具就是我们非常熟悉的伪代码。

伪代码理论上没什么格式要求。我喜欢按C语言的风格写。当然有些人喜欢拿箭头表示赋值。

数据字典

数据字典就是对之前建模过程中的数据流、数据变换、数据做一个详细的定义，以方便沟通交流。

数据字典本身是一个概念性质的东西，其实现形式多种多样。课本上讲了三种定义数据字典的方法。

词条描述

非常死板非常麻烦的数据词典表示法，也许在实际运用中非常好用，因为它读起来的时候非常详细。但在学这门课的时候我是不愿这样写数据字典的。

直接拿一个例子来讲词条描述的表法吧：

1
2
3
4
5
6
数据元素名：词
类型：文字（char*)
长度：任意长度
取值范围：………………
相关数据元素：………………
相关数据结构：字符型（不能为空）

定义式

用一种类似上下文无关语言的方法来定义一种数据。还是直接上例子：

1
2
3
4
日期 = 年 ＋　月　＋日
年 = “1900”.."1999"
月 = "01".."12"
日 = "01".."31"

数据表

直接把数据库二维表当成数据字典。比如

编号 属性 英文名 备注
001 姓名 Name 无

结构化设计

设计分成概要设计和详细设计。这两个阶段的具体定义可能会在其他文章中讲。

在结构化设计中，概要设计就是根据数据流图设计出整体结构，详细设计则是在语句层面具体设计某一个算法、过程。概要设计用面向数据流的设计方法，详细设计会用到流程图、盒图、问题分析图（PAD）、判定树。

面向数据流的设计方法（画结构图）

面向数据流的设计方法就是根据需求分析时的数据流图，设计出程序的模块。和画DFD一样，这个过程也是自顶向下进行的。

结构图

这个过程用到的工具有层次图和结构图（SC）。但从课本上的介绍来看，结构图是层次图的一个拓展。也就是这两种图不是并列关系，而是递进关系。后续的分析也是基于结构图的。

层次图用方框表示模块，只是把模块一层一层地越分越细。结构图在层次图的基础行，要求在模块之间的线上加上数据流的描述

数据流图转结构图

数据流图经过很简单的转换就能变成结构图。课本介绍了两种转换方法。这两种方法输出的结构图的整体结构与大致算法大致相同，但分析数据流图的理解角度不同。

第一种方法是变换分析法。这种方法把整个程序看成输入处理、输出处理、变换控制三个大模块。在一层数据流图中，根据数据流与变换的形状关系，把变换分进这三种大模块里。每一个变换属于大模块里的一个小模块。

用这种方法画结构图要按以下步骤：首先，画一个主控模块（MC）、输入模块（MI）、输出模块（MO），变换控制模块（MT）。MC在最上面，MI、MT、MO分别画在下面，与MC连线。之后，再一层数据流图中画两条边界，把一层图分成三部分。最后，把数据流图“旋转”一下，把对应的数据流和变换模块都写到大模块下方。只要有了数据流图，划分了边界，就可以立刻把数据流图转换成结构图。看了书上的例子就能很快理解这个转换方法。

第二种方法是事物分析法。该方法是思想是找到一层数据流图中有多条路径的变换，把这个变换当成事务中心。所有的输入在经过预处理后经过事物中心进行变换，没有输出模块。

用这种方法画结构图有以下步骤：首先，在一层数据流图中找到事物中心，把事物中心的输入部分划分到一起。之后，画一个主控模块（MC）、输入模块（MI）、事物调度模块（该模块名就是选择的事务中心的变换名）。最后，用和变换分析法类似的方法把数据流图“旋转”一下，在大模块下补上小模块。

当然还有第三种方法，叫混合分析法，就是把两种方法综合一下，变换分析法的输出模块改成事物调度模块。

程序流程图

这是高中就学过的工具，用以描述程序设计的三种结构（顺序、分支、循环）。

圆矩形表示开始结束，方矩形表示是操作，菱形表示判断，箭头表示控制流方向。

盒图

盒图也是用来描述程序设计的。相比程序流程图，盒图没有随意的控制流，能够更好地划分数据的区域。

整个盒图画在一个方形中。具体形式看后面的示例。

问题分析图

问题分析图（PAD）也是用于程序设计的图。它也能规避控制流的任意性。

PAD从上到下是流程，从左到右是模块的细分。

例：

把代码转换成盒图和PAD。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
A;
B;
if (C1)
{
	while (C2)
	{
		if (C3)
		{
			D;
		}
		else
		{
			E;
		}
	}
}
else
{
	do
	{
		F;
		if (C4)
		{
			G;
		}
		else
		{
			H;
		}
	}
	while (C5);
}
if (C6)
{
	I;
}

（原题来自课本的一个流程图）

解：

NS

OAD

判定树

判定树用来表述复杂的条件判断。由于if语句本身符合树结构，用一棵树来表示判断语句是非常自然的。

判定树画起来很简单，左边是条件，每个条件都可以分叉成多个子情况里的条件。最右边是该分支下的结构。

判定表

判定表和判定树作用一样，也是设计复杂条件判断的工具。

判定表的行分成两部分，一部分是条件，另一部分是动作。判定表的每一列表示一个条件和动作的组合情况（条件用T、F表示，执行的动作打个勾）。

一些后续的事情

由于我没有管理好精力，我没有对后面几章做系统的复习。还好，考试没有考很多死板的内容，考的东西偏向理解，我几乎都能答得上来。有一点要特别提一下：考前说好数据流图只画一层，考试的时候要求画两层。

Posted on In ,

计算机组成原理考试结果

和写论文一样，讲完了方法以后，要展示一下实验的结果。我在运用了带有周弈帆特色的费曼学习法进行计算机组成原理的复习后，也要讲一下考试的结果，以佐证方法的高效性。

考试前天结束，现在考试的分数还没出。我先从我自己的感觉谈一下考试的结果和收获。考试分数结果等出了分再更新。

个人感觉结果

考试考察的知识点果然全是复习PPT里的。复习PPT里用红字标出的内容全部出了题目。很不幸，我没有把复习PPT涉及的细琐知识点都过一遍，填空有3题左右完全没听过，选择有1题完全没听过。但我对剩下的题目涉及的知识点非常熟悉，解起题来十分顺畅。说实话，在这门课里我学到的东西并不多。但我也不搞硬件。我认为我在这门科目上的学习成果符合我对自己的要求，也符合学校对学生们的要求。

从复习时间安排上来评价我这次考试。学校所有课程结束后，我剩下了3天时间复习。虽然第一天我没有调整好生物钟，昏昏沉沉地过去了。但在接下来的两天半里（考试是下午考），我快马加鞭，聚精会神地进行复习。把对每章知识点的熟悉程度提升回写那一章作业时的程度。最终，虽然有些小赶，时间略显窘迫，但我还是比较完整地复习了所有内容。我在时间安排上虽有失误，却亡羊补牢，为时未晚。

从复习方法上了评价我这次考试。我和以前一样，用的是费曼学习的思想，也就是用自己的话去描述知识，从而找到理解的漏洞。其实我之前概率论和计算理论也是用了这种方法，但效果不佳。概率论那次应该是我对知识本来就比较熟悉，不应该重新理解知识，而应该做题巩固知识的理解；计算理论那次我只写了一章，实在太累了没有接着写下去。我坚信不是方法有问题，而是我之前做得不够好，所以这次依然采用了这种复习法。恰好，计算机组成原理考试强调知识的基本理解而不强调知识的熟练应用，这种复习法完美契合了考试的要求。我也坚持了下来，把主要章节都做了一次复习。可以说这次考试方法选择得非常恰当。不过话说回来，我似乎也没有发明出第二种复习方法，好像“选择”一词并不恰当。但是，用这个词更帅一些。

从复习策略上里评价我这次考试。我既没有像无头苍蝇一样，拿着课本乱翻乱看；又没有像复读机一样，逐字逐句地去从干巴巴的课本中背下每一句话。我去学校网站上下载了考试复习的PPT，非常精准地命中了大部分的会考到的知识点。与此同时，对于我上课的时候理解过一遍的知识点，以及每次课后作业所涉及的知识点，我又认真地复习了一遍。可谓是双管齐下，两手都抓，两手都硬。最终，虽然算有遗策，但大局难改，考试的大部分题目对我来说就像小学数学一般简单。在有限的时间里完成复习，复习策略的正确选择是成功的关键。

虽然考试结果没出，虽然我可能惨遭打脸，但我依然敢于给自己下断言：我这门学科成绩85起步，封顶95。

如果最终成绩有所偏差，那么我也不亏。在学这门课的时候，我学到了课本内的知识，培养了课本外的学习能力。分数不能代表一切。你若是只看分数，你就输了。要看到分数之外的东西。

希望二月出成绩后，我能看到一个比较好的结果。

考试结果

最后我考了88分。没考到90分满绩还是有点遗憾的。

考试的结果证明这次的整体复习效果确实还可以，但是由于时间不足的原因，我没有仔细去看每一个知识点，这些细琐的知识点应该是我失分的地方。

我不希望以后再出现这种考试，所以我就不写我以后应该怎么怎么做了。

Posted on In ,

去百度查课后答案的时候，发现这本教材至少11年没有发生改动。虽然这本书涉及都是一些原理性的东西，和时代无关，这门课对我们来说也不过是一门学过就忘的课，但我还是觉得这种“万年不变”的教学态度有问题，需要加以改正。

计算机组成原理复习：第六章 中央处理器

本章主要在讲CPU（中央处理器）。本章先整体介绍了CPU的组成结构、性能参数等内容，之后稍微介绍了CPU的硬件实现，再具体介绍了CPU的整个控制工作原理。由于CPU执行指令的时候涉及一些微操作，本章接着又进一步介绍了微操作的有关内容。介绍完了CPU的基本工作原理后，本章又介绍了一个简单CPU应支持的操作。最后本章介绍了CPU相关的新技术。

CPU实际上包括运算器和控制器。运算器主要涉及的计算方法在之前章节已经介绍过。这一章实际的重点是控制器的实现。

考试重点应该是放在对CPU执行指令的过程和微操作的原理上。要理解CPU指令的执行过程，对于一个给定的操作，要能够写出CPU每一步在做什么。

和上一章一样，我只对比较重点的地方进行复习。

CPU的基本组成

其实CPU的组成主要是讲CPU里有哪些寄存器。寄存器可以分成通用和专用。专用的寄存器是只有固定用途的寄存器，而通用寄存器可以根据实际需要使用。可以看成预定义常量和变量，或是操作系统中的系统内存和用户内存。

专用寄存器有：

  • 程序计数器PC
  • 指令寄存器IR
  • 存储器数据寄存器MDR
  • 存储器地址寄存器MAR
  • 程序状态字寄存器PSWR

这里只是提一下这些寄存器的名字，后面讲CPU的控制原理的时候还会提到这些寄存器，到那个时候才能理解这些寄存器在干什么。这里提一下就当是在声明变量。

处理寄存器外，CPU中还有一个指令译码器IR，用于识别指令中的操作码。还有一个控制单元CU，大名叫微操作信号发生器。它是CPU控制功能的核心。

CU的实现方式在复习PPT中被列成了重点，我不得不看了一下。CU的实现大致分两种，组合逻辑控制器和微程序控制器。其实控制的微操作和程序设计一样，也是模块化的。组合逻辑控制器追求速度，却无法拓展，难以调试，难以实现自动化设计。微程序控制器的特点与之相反。（我没搞懂什么是自动化设计）

除了这些外，CPU中还有ALU，但这不是本章的重点。

时序系统

时序系统是CPU的工作基础。和游戏一样，CPU的工作也有基本的时间单位。这种和最小时间单位有关的系统就是时序系统。

这里自顶向下地介绍整个时序系统。指令周期是指从取指令、取数到完成指令整个过程需要的时间。各种指令所需的指令周期不同。指令周期会拆成机器周期（CPU）周期，每个机器周期干一个特定的活，比如取值周期、取数周期。机器周期又要完成若干微操作，每个微操作占用的时间叫做节拍。每个节拍最终由几个脉冲组成。脉冲是最小的时间单位。

指令执行过程

这一部分是CPU控制原理的核心。

指令执行过程分成三个阶段：取指令阶段、分析取数阶段和执行阶段。

取指令阶段

从宏观上来讲，这一阶段把指令从主存中取出来并存到指令寄存器中。具体来说分以下几步：

  1. (PC)->MAR
  2. CU向存储器发读命令 Read
  3. 取出的指令存到MDR中 M(MAR)->MDR
  4. 把MDR的内容送到IR中 (MDR)->IR
  5. PC自增 (PC)+1->PC

分析取数阶段

根据指令，取操作数。由前几章的内容可知，指令中的操作数可能表达得十分“晦涩”，可能要通过多次间接寻址才能得到。

如果操作数不用寻址，那么就不用进行此阶段。

比如要取@R0，即以R0的值为地址，到主存中取数。那么操作有以下几步：

  1. (R0)->MAR
  2. Read
  3. M(MAR)->MDR

执行阶段

现在我们有了函数，有了函数参数，接下来的任务就是执行指令并将结果保存。

比如把数相加的执行阶段指令有以下几步（MAR已经是目标存储寄存器的地址）：

  1. (R1)+(Y)->Z
  2. (Z)->MDR
  3. Write

比如转移A步指令的执行阶段有以下几步：

  1. (PC)->Y
  2. Ad(IR) + (Y) -> Z
  3. (Z)->PC

微程序原理

基本概念介绍

之前CPU执行的每一步操作，都叫做微操作。对于指令来说，这些微操作都是不可再分的操作。但是从微操作的角度来看，微操作还可以分成很多个更细致的操作，比如打开某个逻辑门等。这些更细致的操作叫微命令。不同的微操作之间可能会公用相同的微命令。引入程序设计的思想，微命令的重用和模块化非常关键。微程序控制的思想也因此被提出来了。

一个机器指令就对应一个微程序。一个微程序里可以分成多个微指令，微指令就是一个一个函数。和CPU的指令类似，微指令也分为操作码和地址码。但微指令的地址码只包括下一条要执行的微指令的地址，而不是存数据的地址。在微指令中，微命令就是原子操作，和程序中的语句相同。

微指令编码

微指令编码指对微指令的操作码编码。操作码译码的结果是得到一个01序列，表示执行哪些微命令。

最显然的两种编码法是直接编码法和最短编码法。前者令操作码每一位都表示一个微命令是否执行，后者进行完全编码，每次只能产生一个微命令的输出。由于微命令可以并行，但又不是每种操作都能并行，因此第一种方法编码长度过长，而第二种方法无法进行并行。

一种折衷二者的方案是：事先知道哪些操作不能并行，把这些操作分成一组，进行完全编码。整个操作码就被分成了一个一个完全编码的字段。

课后有一道这方面的题目。考试估计会考。

组成部件

  • 控制存储器CM，存了一堆微程序
  • μIR，微指令寄存器，和IR类似
  • 微地址形成部件，用于形成初始微地址和后续微地址
  • μMAR，微地址寄存器，和MAR类似，但不是从内存而是从CM中取指令