图论算法漫谈之网络流(二):Edmonds-Karp算法和Dinic算法

April 12, 2016 at 11:47 pm

本篇接着第一篇的内容,介绍如何使用增广路径的方法来求最大流。Ford-Fulkerson方法没有给出具体求增广路径的方式,如果增广路径的找法不好,甚至不能保证算法是多项式时间的。Edmonds-Karp算法和Dinic算法的出发点都是通过找“好”的增广路径,来降低时间的复杂度。其中Edmonds-Karp算法较为简单,但是算法的复杂度为,不适合实际使用;Dinic算法和Edmonds-Karp的算法非常类似,复杂度为,实际使用时还是较快的(通常在OJ等题目上都是够用的)。在实际应用中采用的大多是预流推进相关的算法,它们有更低的复杂度,我们在下一篇再介绍。 Edmonds-Karp算法 本来打算跳过这个并不实用的算法,不过考虑到它更加简单,使用它来解释一些概念会更加通俗易懂一些,所以这里还是先介绍它。 算法的思想很简单:我们每次都是在残量网络中找一条从s到t的最短路径作为增广路径,这里的最短路径是指无权图的最短路径,即仅仅取决于s到t所经过的边的数量。 算法的过程非常简单,唯一需要研究的是算法如何保证时间复杂度。我们知道无权图的最短路径可以通过BFS+队列在的时间内求得,我们只要证明我们一共只需要求次增广路径就行了。在此之前我们先证明一个引理: 引理 1: 记为残量网络中u到v的最短路径。在算法不断迭代求增广路径的过程中,源点s到任意点v的最短路径单调不减。 证明: 我们使用反证法。我们记第一次出现这样的顶点之前的残量网络为,我们找到一条最短路径作为最短路径,并取流,形成新的残量网络,导致了源点s到某些顶点的最短路径减小,我们记其中s到它的路径值最小的顶点为v,有 我们记s到v的最短路径中刚刚到达v之前的一个节点为u,即s到v的路径表示为,那么有 由于我们取的v是路径值最小的顶点,所以s到u的最短路径必然没有减少: 如果中存在边,那么 和假设不符,所以中不存在边;而中存在边,而我们只在最短路径上更新边,所以边在中s到u的最短路径上。那么 同样和原假设矛盾,所以原假设不成立,引理成立。 我们利用引理1来说明Edmonds-Karp算法的复杂度: 定理 1: Edmonds-Karp算法只需要求次增广路径。 证明: […]

图论算法漫谈之杂谈:最小生成树及相关算法(一)

April 10, 2016 at 5:55 pm

由于正好最近接触到了一些生成树相关的题目,所以稍微偏离一下原定的计划,讨论一下最小生成树(Minimum Spanning Tree,MST)以及相关的算法。本来打算汇聚到一篇里面,但是仔细整理一下发现内容还是比较多,而且寄希望于以后还能有所扩展,所以加上了个“一”,目前实际的内容一共只有两部分,之后的故事之后再说了。不出意外的话今天晚些时候还是会按照原计划介绍网络流的开篇。话不多说了。 最小生成树算法的基本思想 通常的MST问题是针对于无向图说的(有向图的MST会在下一篇中提到),指的是无向图G的一个连通、无环的子图(树)T,使得边权的和最小。举个简单的例子的话,就是几个网络节点之间要连通,那么希望总共花的网线长度最少。 MST问题是网络相关问题中比较简单的一类问题,也可能是最早被研究的问题,简单的一个原因是,解决MST问题的百分十九十以上的高效算法都是基于贪心思想的(似乎目前时间复杂度最优的算法并不是基于贪心的,但这有点远离实际应用了),MST问题能用贪心思想解决的原因和拟阵(matroid)模型有关,这部分的内容这里就不说了(Introduction to Algorithms 里有关于拟阵的一些简单的讨论,等有空再去研究这种偏数学的东西吧)。无论如何,不和拟阵打交道也可以理解MST问题及其算法。 MST问题可以使用贪心算法解决,所有基于贪心的MST算法的核心框架如下: 1. 初始时边集A是一个空集; 2. 我们不断地向A添加安全边(safe edge),所谓安全边是指如果在添加这条边之前A是某个MST边集的子集,那么添加之后A仍然存在某个MST,使得A是它的子集 3. 显然我们添加n-1条边之后算法结束,我们得到了MST 注意空集是任何边集的子集,所以一开始条件2是成立的。问题的核心当然是如何寻找安全边。我们已经说过不讨论其背后的本质,所以我们这里直接“突然”地给出定理(tarjan的书中给出的定理似乎比这个更加general一些,但是tarjan的数学太好,Introduction to Algorithms里的这个定理更加浅显易懂。以后有时间再仔细研究吧)。在这之前稍微介绍一下割(cut)的概念,这个概念在网络流中也扮演了相当重要的地位。图G的一个割是指图G顶点集V的一个划分(S, […]

图论算法漫谈之连通性(三):tarjan求双连通分量

April 7, 2016 at 1:24 pm

有了前两节的基础之后,我们回到无向图中,讨论有关双连通分量的问题。通常来讲,双连通分量分为两类,点双连通分量(也即一般意义上的biconnected component)和边双连通分量(也称为桥双连通分量)。我们先介绍点双连通分量,再介绍边双连通分量。 点双连通分量 我们定义一个无向图是点双连通的,如果这个图不存在割点;我们称图的一个极大的点双连通子图为点双连通分量。下图中,边(1,3)(1,4)(3,4)及相应顶点构成一个点双连通分量,边(2,3)(2,5)(3,5)及相应顶点构成另一个点双连通分量。 可以看到,多个点双连通分量之间可能共用一个顶点,而这个点是一个割点,这其实也是显然的,因为点双连通分量不能包含割点,所以每次遇到割点,必须把割点切开,相当于两边都带有一个割点。由于点可能带有重复,我们要使用边集(及相关的点)来表示一个点双连通分量,为此,我们定义等价关系e,表示两条边属于同一个简单圈(不带重复边不带重复点的封闭路径),容易验证等价关系e对应的每个等价类正好可以表示一个点双连通分量:首先,在同一个简单圈中不会因为移除任意一个顶点而变得不连通;两个共用一条边的简单圈实际上构成了一个更大的简单圈。 至此,类似于tarjan强连通分量算法需要求解属于同一个强连通分量的点,这里我们要求解属于同一个点双连通分量的边。和SCC类似,我们维护一个栈,并把边不断地压入栈中(需要注意的是无向图中一条边如果不在树上,那么它既可以是前向边,又可以是后向边,我们总是在它是后向边时已经把它压栈,所以注意不要把再前向边压栈从而造成重复,可以参看下面附上的例程),与此同时也计算low[]和dfn[]。一旦我们发现节点v的一个孩子满足,我们便发现了一个割点(若v是根,那么若v不是割点,那么图中没有割点,整个图是一个点双连通分量),那么显然要进行切割,我们把栈中直到(v, w)的边全部取出来,这些边便构成了一个点双连通分量。算法结束时,我们得到了所有点双连通分量。 下面我们证明算法的正确性,同样使用数学归纳法,我们以边的数量进行迭代。 如果边的数量为0,那么要么是空图,要么仅含有1个顶点,此时算法不输出任何点双连通分量。是正确的。(注意我们按照边来划分点双连通分量,如果没有边,则不构成点双连通分量)。 假设边数在小于等于e-1时均成立,我们要证明边数等于e时仍然成立。 我们先讨论最终算法得出的点双连通分量多于1个的情况,并记第一个从中剥离出来的点双连通分量为。按照算法流程,有一个对应的割点v(v不是根,否则算法只会得出一个点双连通分量),该点落于上。如果我们对图以v为根执行算法,根据算法的DFS流程,这个在原图上算法执行至v时的步骤是一样的,而根据假设,算法在边数小于e的图上执行是正确的,所以确实是一个点双连通分量。剩下来的图同样是边数小于e的图,而同样执行流程一样,所以算法必定可以正确执行。 我们接着需要讨论算法最终得出的点双连通分量只有1个的情况。如果算法出错,那么由定义可知结果图中存在割点。但这是不可能的,因为一旦发现割点,我们总是进行切割,那么必然不可能只有一个点双连通分量。 至此我们证明了算法的正确性。 下面附上一个示例程序: struct edge{ int x, y; }; […]

图论算法漫谈之连通性-番外篇(一):求解2SAT问题

April 5, 2016 at 7:02 pm

      本篇是关于图论连通性内容的一个番外篇,暂时不讨论有关连通性的其它性质和算法,而是介绍一个看起来和连通性并没有什么关系的问题,2SAT问题。尽管问题本身看似和连通性无关,但是接下来将会看到,使用SCC算法可以在线性时间内非常有效地求解2SAT问题,而且大多数SCC算法在产生强连通分量时同时提供了拓扑顺序这样的便利性,使得求解2sat问题几乎只需要调用一下SCC算法就可以了。 使用SCC算法求解2SAT问题       这里还是简单地介绍一下2SAT问题,对于SAT问题的更多内容可以参考wiki。我们首先有一个布尔变量及它们的非构成的集合,考虑一个例子,合取范式,若每一个合取范式中每一个析取项总是由两个元素(或是变量本身、或是它的非)组成,那么求解是否存在一组变量的取值,使得该合取范式为真,这样的问题即称为2适定性(2-satifiability, 2SAT)问题。从上面的例子可以看出,如果一个析取式只有一个元素,可以通过和自身进行析取转变为两个元素。       为了将问题转化为连通性问题,我们首先构造问题所对应的蕴含图,为此,我们以集合B中的每个元素(即n个变量以及它们的非)为顶点,对每个析取项,以和它等价的两条蕴含式在蕴含图中增加边。由于我们每次成对地增加边,所以建立的蕴含图有对偶性:改变所有边的方向,并改变所有顶点的标记,每一个顶点都改为,那么改变后的图和原图同构。       我们对建立的蕴含图求强连通分量,容易验证每一个强连通分量内部的点都必须有相同的真值。基于这个事实,我们证明2SAT问题有解当且仅当它的蕴含图中不存在一个变量,使得它和它的非处于同一个强连通分量。       必要性是非常好证的,这里略去,为了证明充分性,我们给出一个算法,在这种情况下给出一个可行解。我们首先求出蕴含图的强连通分量,然后进行缩点(condensation),使每个强连通分量用一个点表示,从而得到一个有向无环图(DAG)。我们首先对这些点进行拓扑排序,幸运的是,tarjan算法和Kosaraju算法生成SCC的时候已经给出了拓扑排序(Kosaraju算法按照拓扑顺序输出SCC,而tarjan算法则按照反向拓扑排序输出SCC),这个性质也比较好证明,这里也暂时略去。我们按照拓扑顺序遍历强连通分量,由于对偶性,每个强连通分量S都有对应的强连通分量,如果在S中,那么在中。遍历时,如果S未被标记,我们给S(即在S内的所有顶点)标记为TRUE,标记为FALSE,直至所有的节点被标记,从而得到一个解。 我们使用数学归纳法证明上述方式给出了2SAT问题的一个解。 初始情况下S是逆拓扑排序的第一点,所以它没有出度,将它标记为TRUE局部不会产生矛盾,同样也不会产生矛盾。 如果前面没有产生过矛盾,考虑当前强连通分量S,如果S已被标记,那么跳过即可,仍然不产生新矛盾;否则,将它标记为TRUE,按照顺序,所有指向它的节点都还没被遍历,可能导致的局部矛盾是它指向的已经被标记为FALSE的节点;但是反过来按照对偶性,所有标记为FALSE的节点向外指向的边均未被标记,所以这样的节点并不存在,所以仍然局部正确。 至此证明了该性质。 如果使用tarjan算法来求解2SAT问题,那么基本上不需要额外的步骤,这里就不附代码了。下面给出一些可以用来演练的习题,需要注意如何构建2SAT模型,以及如果将条件转化为合取范式(可以参考离散数学中一阶逻辑演算的相关内容)。 1. poj 3207 求解2SAT的特殊解 tarjan算法给出了求解2SAT问题的线性时间算法,唯一的缺陷是求法限定了解的给出方式,使得不容易应付一些简单的变形。举例来说,我们可能要求一类最优解,比如字典序解,即如果存在使取真的解,那么让它取真;否则如果能取真,则取真,以此类推。使用tarjan算法很难保证这一点。为此,这里再介绍一下一个比较简单通用,但是最坏时间复杂度为的算法。这里以求解字典序解为例,下面给出一个实际例子: 我们的策略很直观,我们取,看看是否能找到解,如果找到,就是我们要的解;如果不能,则取看看能不能找到;如果都找不到,那么2SAT问题无解。如果不对上式产生影响,那么只要有解,那么总是可行的,所以我们可以接着考虑的可能性了;当然对于例子不是这种情况,那么由于设定了,上式发生了更新: 注意由于所以1式可以直接忽略,并且由于,导致了第三项的必须为TRUE,所以我们仍然必须更新上式: 此时不存在单项,上式无法再更新。我们把设定一个变量的真值,然后根据这些单一的项不断更新,直至所有析取项都是两项的过程称为一次清除(purge)。具体实现上我们可以维护一个队列来保存这些更新过程中出现的单一项。 […]

图论算法漫谈之连通性(二):tarjan求强连通分量

April 1, 2016 at 9:53 pm

进行了简单的插曲之后,这一节我们回到有向图强连通分量的讨论中来,介绍使用tarjan算法来求有向的强连通分量,事实上这才是真正的正篇~ 很久之前写过一篇关于SCC tarjan算法正确性的文章,但仔细校验之后发现了不少错误,所以如果发现了错误,以本篇为准。 为了使行文流畅,这里还是和之前的文章一样,复习一下dfs搜索树中的一些基本的概念。我们仍然以下面的这张图为例: 下图描述了一个有向图,每一条边(包括实线边和虚线边)都对应了图中的一条边,每个节点中的数字代表了DFS访问的顺序,也即上一篇文章中提到的。这里使用不同的颜色标记了不同性质的边: 1. 图中蓝色的边是DFS搜索树上的边,称为树上边(tree edge),我们用表示一个树上边。 2. 图中红色的边是DFS搜索树上由祖先节点指向其子孙节点的边,称为前向边,容易知道移除前向边不会改变图的连通性,所以本文中我们基本可以忽略它。 3. 图中绿色的边是DFS搜索树上有子孙节点指向其祖先节点的边,称为后向边(frond),我们用表示一条后向边。 4. 图中橙色的边是DFS搜索树上由一棵子树指向另一棵子树上节点的边,称为交叉边(vine, cross link),我们用表示一条交叉边。 5. 图中黑色的边实际上是一棵搜索树上的节点到另一棵搜索树上的节点的边,称为跨树边,我们将会看到,跨树边在这里也发挥不了大的作用。 我们需要知道,不论是后向边还是交叉边,都满足。 tarjan算法也可以用简单的两个步骤来表示: […]

图论算法漫谈之连通性(一):tarjan求无向图割点

April 1, 2016 at 11:55 am

本文是图论连通性的第二篇文章,本来应该接着上一篇的思路,介绍tarjan求强连通分量,但是考虑到内容还是由浅入深比较合适,这里还是先介绍tarjan的一系列DFS算法中较为简单的一个,求割点,并由此介绍tarjan算法中常用的概念。 所谓无向图的割点(cut vertex),是指移除之后会使得的连通分量数量增加的点,对于一个连通图,就是移除之后,会导致剩下来的图变得不连通的点。这样的节点通常在网络通信模型中较为重要。 tarjan求解割点的算法步骤也非常简单: 1. 对于每个节点,使用dfs求low[v], dfn[v] 2. 每一个连通分量的dfs搜索树中,根节点是割点当且仅当有多于一个孩子;其它节点v是割点当且仅当至少有一个孩子w满足 这里还是重新介绍一下和的含义。即为节点前序遍历的序号。 指的是节点不通过其搜索树上的父节点在图中行走,直到遇到一个dfn不比它大的节点就停下来,这样子它能停下来的所有点中dfn的最小值。从递归的角度讲,low[v]取决于以下三种情况的最小值: 1. dfn[v](可以在自身处停下来) 2. dfn[u] for an edge (v, u) […]

2016

January 22, 2016 at 2:51 pm

这是2016年的第一篇文章。幸运的是我成功活到了2016年,病情似乎还没有马上进一步的恶化。不幸的是从2015年12月开始的Web项目一直持续到了现在也不算到了尾声。总之,在结束了主要代码的编写之后,在暂时结束了四处投医的乱心状态之后,还是需要做回自己。 首先还是想谈谈关于这次项目的内容。一个关于房屋租赁的Web系统,也算是第一个我亲力亲为,主打前端,兼任后端,偶尔还当一下需求分析人员、项目管理人员的两人小组大作业。这个原本1个月要完成的项目一直拖到现在快两个月也没有收官,可以说是处处充满着失败,其中,不想再挖坑的我无疑又挖下了许多坑。 作为唯一一个可以当作需求分析人员的成员来说,需求获取、分析阶段,实在是太糟糕了。客户确实是很糟糕,无法表述自己的需求,而我没能从中挖掘去客户的真正需求,是导致直到本月15日客户反馈说“很不好用”的根本原因。我只是从一个coder的角度,或多或少的掺杂了自己的一些想法,来意淫客户的需求,虽然存在少量的沟通,但在少量的沟通中,很少有获得有效的信息。而且更可怕的是我开始厌烦与这样的客户沟通,只能满口“客户是煞笔”这样的话语。关于需求的获取与分析,我只有对当初本科相关课程的良苦用心的深深感慨和没有好好学习的悔恨。当初的课程也是一个Web系统,也是从需求分析开始,一步一步模拟下来,然而真正实践起来时,确是困难重重。除了沟通的问题以外,没有很好的利用Web系统原型开发这一特点又是另一个大坑。虽然接到项目的第一天就吭哧吭哧地下载了Axure,但是在用三张几乎空白的页面第一次获取需求之后,就把它扔进了垃圾箱,没有再拿出来过。回想过来,如果再对原型开发有一个更好的认识,对Axure有更好的学习,也不会有这么多时间的消耗。 第二个坑则在于不擅长前端开发的我选择在项目中充当一个前端开发。虽然有Angularjs, Bootstrap, WebStorm这三样神器在手,对于前端几近一无所知的我来说,前端的编码路程确实各种坎坷。整个过程中唯一的亮点是选择了SPA和Angularjs,直到现在,我才敢说,SPA从用户体验上好上了一大截。说实话直到现在,《Single Page Web Application》我还没看到一半,当初这个决定,只能说是神来之笔,直接省去了大量的后端View开发,没有用到任何后端的View框架。除此之外,则尽是败笔了。对Angularjs的不熟悉直接导致一开始所有的代码都挤压在Controller里面,多个异步请求也并没有基于q库作任何的优化(包括性能上的和代码可读性上的),甚至胡乱的使用$watch大幅度降低程序的性能。在插件方面,又是由于不熟悉,没能使用一些好用的插件(如dialogs),而使用了一些不好的插件(Wdatepicker),甚至自己去手码部分的dialogs实现,耗费了大量的时间去造轮子,又耗费了大量的时间去移除(当然选择ueditor我是一点怨言都没有的,这也算是某种形式的广告)。 后端编写又是更大的一个坑了。在开发阶段,后端和前端的耦合性非常明显,前端功能的增加必定对应后端功能的增加,这种一一对应的关系直接导致了写完前端部分要立马补上后端部分,从而进行简单的调试。这一方面意味着我不可能只做前端,必须参与到后端的开发中去(当然我更希望开发后端而不是前端),另一方面则是意味着对于Java,对于Spring MVC体系的不熟悉的我必然会挖下新坑。总之后端代码经过我的揉合之后已经俨然变成了一坨翔,当然而前端代码也是,差别在于前端的翔直接被看到了,后端的翔看不见,我看见了,但我装作看不见。 一个叫做“续签”的功能可以说是为这个破烂不堪、伤痕累累的系统再次挖下了大坑。由于初期需求的把握不当,数据库设计的草率,导致这个功能不仅增加很困难、改动量大,而且系统性能也要为这一个小功能而大打折扣。再经过若干天的慢跑冥想之后,确定了这个功能的增加方式,吭哧吭哧的码了两天,算是KO了这个整个系统开发中难度最大的部分。但这个功能导致的系统改动是否会造成其它未被考虑的影响?我自己到现在还没能确定。可以说这是天大的一个坑了。 在主要开发结束之后,我就默默地在雪天里,躲在寝室里,默默地精卫填坑了。 本来是想借主要开发结束来缓缓心情,吐槽吐槽的,不知不觉对项目本身扯了一大堆无关紧要的东西。不知道这次项目开发还有没有其它的大坑,但是被我坑的最惨的无疑是另一位后端开发的同学了,作为后端大神,不仅要忍受一个煞笔想出来的各种奇葩的想法,还要写一些恶心的代码,有时候还要干体力活(是的,这个Web项目竟然还有体力活,大量的体力活!为此写了好几个脚本,最后还是变成了体力活!) 无论怎么说,一个东西的尾声往往就是另一个东西的序章,不知不觉在浙大的研究生生涯又过去了一大半了,看来这次,是无论如何,都要离开浙大了,当然,还有1年多一点,离别思绪还不是很浓,我也不自己瞎煽情了,只能说这个研究生,读的很失败吧,当初20瓶啤酒砸头的壮志豪言终究是一句戏话,像我这种人,再给个十年八年,也还是这副吊儿郎当的样子罢,没怎么好好学习,也没怎么好好学项目,别人是研究项目两不误,我是在寝室阅片无数,呵呵,我完蛋了。就这样吧,新的一年新的气象,也没必要再这样颓废下去了,患病以来感慨良多,看淡了很多,也不再那么心高气傲了,只求有某个公司啃收留我等什么都干不好的渣渣。 嘛,无论如何,毕竟是要迎新年了,还是道一声新年快乐。 新的一年,前方的路是怎样的呢?

ThinkSNS源码分析(四):MVC架构

June 25, 2015 at 10:47 pm

本篇更多的是对之前的内容进行总结、概括,并从中提炼出相关的概念来,可能代码上就没有多少了。但是我相信对之前的内容进行复习、补充学习无疑是非常有帮助的。 在开篇中,我们分析了有关模板渲染的知识,所谓的模板,实际上是将程序中的一些逻辑和程序实际要显示出现的页面分离开来。现在我们给这种要显示的页面一个更统一的名称,视图[View]。这就是MVC中的V。我们再来回顾一下视图到底是什么。它主要是一个html页面,告诉我们最终的页面长成什么样子,唯一缺少的是里面要填入的字段,举例来说,视图中包含了欢迎用户的“欢迎您,XXX”这样的显示效果,但具体是哪个用户,这个XXX,则不属于视图的范畴。某个角色需要告诉视图,这个XXX到底是什么。 在第三篇中,我们分析了有关和数据库交互的知识,并且知道了所有和数据库的操作最终都涉及到XXXModel类。现在我们也给它一个统一的名称,模型[Model]。这就是MVC中的M。在上一篇中提到,M,通俗地来讲就是数据。当然,这是一种非常表象的理解,而且是个并不完整的理解。举一个简单的例子来说,RegisterModel也是一个模型,但是数据库里似乎并不需要Register这样一张表。更一般地,我们把所谓的模型解释为业务逻辑。如果对于业务逻辑这个概念并不够熟悉的话,我们暂时可以这样说,一个程序中,除了视图以外的部分都可以称为业务逻辑(注意这是一种理解的需要,但是并不能把模型和业务逻辑等同起来,后面会有更详细地解释)。业务逻辑代表了整个程序的运作原理,而最终呈现在用户面前的视图只是方便和用户交互用的部分而已。同样的功能,我们可以在终端界面的小黑框中完成,也可以借由GUI展现出华丽的效果。对于同样一个系统,交给不同的两个小组做,最终的界面也肯定不一样,但是内部的功能是一致的。 按照这样的逻辑,似乎可以称之为MV模式,那么MVC中的C起到怎么样的作用呢?C代表的是控制器[Controller],以注册为例,当用户填写完资料点击提交按钮进行注册时,我们需要干什么呢?我们确实有一套判断用户信息是否合理的业务逻辑,包括用户名是否已经被注册,用户名是否包含非法信息,资料是否伪造等等,如果用户信息合理,我们还要实实在在的把用户信息存放到数据库中。这些都放在了RegisterModel中,在这之前,等等,当用户提交了请求后,谁来负责决定要使用注册模型[RegisterModel]呢?针对这么大的系统问这样的问题似乎太难回答了,我们回到一个简单的问题里去。假设我们现在完成了一个字符界面的计算器程序,它很简单,只能执行加减乘除四项运算。用户首先输入两个数,然后再输入一个命令,1表示对两个数执行加法,2表示对两个数执行减法,3表示乘,4表示除,5表示退出。当用户输入3 4 1的时候,终端界面会显示如“Result: 7”这样的结果,这就是所谓的一个很丑的“视图”。Web系统中用户的请求实际上对应了传统程序中用户的输入。这里的1,2,3,4,5实际上就代表了实际要执行的业务逻辑,1代表执行加法,输出结果。这里的输入可能在一个input()函数里处理,input()函数得到输入后,写一个if else之类的语句if(cmd == 1) add();这样以调用加法。还需要使用output()这类的函数输出视图。这样类比之后你是否对控制器的功能有了更清晰的掌握?对,在执行具体数据相关的业务逻辑之前,对于大部分系统,尤其是Web系统,我们需要有可以处理用户输入的逻辑,依据用户的输入执行具体的业务逻辑,这就是控制器的作用,可以认为它根据用户请求来“做决定”。 这是否和之前所说的“一个程序中,除了视图以外的部分都可以称为业务逻辑”相矛盾呢?实际上并没有。控制器本身也是广义上业务逻辑的一种,这是不可否认的。但是这个业务逻辑较为特殊,它本身并不处理具体的数据,而是起到找到处理数据工作人员的作用的人,看起来就像是经理,它本身不干活,而是让具体的员工来干活。也就是说,控制器处理的是数据无关的业务逻辑,而模型处理数据相关的业务逻辑。好了我们扯回来,回到注册这个例子。 我们在第二篇中讲过,当用户点击“提交注册”按钮之后,首先要有路由的过程,来找到具体的模块的具体的小模块,即所谓的Module和Action。现在我们就可以站在更高的角度看这个问题了。我们口口声声说的模块,实际上仅仅是针对这个模块的控制器,而每个action就可以理解为一个个小型的控制器。当用户提交请求后,通过路由系统,找到某个模块相关的控制器,再细化到具体的操作[Action],而这个action再来决定要使用哪个业务逻辑。还是以“提交注册”为例,首先交由路由,得到最终位置RegisterAction这个控制器的一个操作doStep1()中。进入之后,我们使用$this->register_mdel来判断用户名是否有效,邮箱是否有效,密码是否有效等等,如果都没有问题,我们使用$this->_user_model->add(...)方法执行用户的注册,即写入数据库,最后显示出“注册成功”字样的视图。 扯了这么多,相信你对MVC这个概念已经有了初步的认识,而且对于M, V, C这三个元素也能说出点一二三来了。下面我们以问答的形式来阐述一下MVC架构模式,并且分析一下这么做的好处,或者说不这么做的缺陷,解决对于MVC模型仍然的疑问。 问题一,MVC是什么,在ThinkSNS中对应的是哪一部分?MVC是一种针对计算机软件交互部分的架构模式,对于Web这种重交互的应用,它通常也做为整个系统的架构模式(如果你熟悉Java的图形界面开发,你就会发现Java标准API提供的图形控件都以MVC的方式实现,从那个角度来看,MVC只是你的程序中自己都可能不怎么重视的很小部分)。它将交互部分分成三个部分,模型、视图和控制器。在ThinkSNS中,每一个html模板都对应了一个视图,每一个XXXModel类都对应了一个模型,每一个XXXAction类都对应了一个控制器。 问题二,为什么要有V,如果没有V会发生什么事?V也就是我们所说的视图,它代表了界面。将界面和程序的其它部分分离开来是很早以前就有的一种编程思想。对于一份数据来说,它可以有很多的表现形式,而且这个表现形式可能经常发生变化,如果把表现形式糅杂在程序中,将来改动的时候就会非常复杂。这里举两个极端的例子来说明分离界面和程序其它部分的重要性。第一个例子是,对于同样的数据,电脑版和手机版的网页显示的内容显然不一样,当然还会有手机app,都要有不同的展现方式,它们的数据一样,仅仅是表现形式不一样,如果两者是糅杂在一起的,那么改动起来非常困难。第二个例子是,如果我们网数据库里存储了一个代表界面的html代码,那么将来这个程序恐怕是不可能转化成CS模式了,数据库里的数据完全无法复用。这些例子都表明,对于大型的系统来说,界面和程序的其它部分一定要分开。 问题三,为什么要有C,如果没有C会发生什么事?C也就是我们所说的控制器,它接收用户的请求,并调用具体的模型进行处理。我们前面说过,事实上C和M都属于业务逻辑,那么如果C和M揉合在一起会怎么样呢?当接收到用户请求后,直接交由M来处理。M需要首先解析用户的请求,接着需要和数据库交互,最终还要将结果告诉视图,渲染出最终的结果,可以说是极大任于一身。一旦数据库的表结构因为某种原因(如效率太差重新设计)发生了变化,天呐,我们又要在茫茫码海中捞针,去找和数据相关的业务逻辑。事实上,无论数据的存储方式、获取方式发生任何变化,只要最终的数据本身没有变化,程序中的这部分业务逻辑,尤其是解析用户请求、展示最终视图这部分逻辑,都不会发生变化。C和M糅杂在一起,改动起来非常麻烦。 MVC架构的出现解决了上述的三个问题,使得程序结构显得更加清晰,设计分工显得更方便。但是MVC架构本身并没有对V如何设计,M如何设计提出意见。除了C部分由于要承担M和V的通讯工作而基本统一外,V的设计和M的设计都是值得去思考的。关于V的设计不属于本系列的讨论范围,那更多偏向于前端设计。如前面反复说过的,M是和数据相关的业务逻辑,主要扯到的部分是数据库。会在番外篇中对ORM的内容进行讨论。 […]

ZOJ 3365 Integer Numbers

January 21, 2014 at 8:24 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3365 今天由于外力因素,没法干其它的事,于是在ZOJ上又水了水,算上这题,终于是AC400题了。回头想想,这个目标应该是在去年,还是前年就应该达成的,时间过得真快,不知不觉又被我水过去了两年么,果然已是拖延症晚期。 题目的大意是说小男孩写了一个连续的整数序列(n <= 50000),然后被腹黑的小女孩修改了一些数字,使得序列不再连续了。小男孩很伤心,希望你在修改尽量少的数字的前提下恢复序列的连续性,要求输出被修改的数字的个数和最终的序列,任何可行解都可接受,是个special judge。 考虑元素array[i],如果保持它不变,那么array[0]必须等于或者修改为array[i] - i,这是确定的,即所有元素都有保持它不变所需要的一个初值。拥有共同初值的元素构成一个等价类。元素最多的那个等价类中的所有元素就是需要保持不变的元素。使用O(n)的时间计算出所有元素的初值,问题就转化为求众数了。 一开始想用hash,后来想想C++没有hash,所以就有map求了一下,220 ms AC.后来发现ZOJ已经支持C++11,托STL设计者的福,仅修改了几行代码就有了unordered_map版本,150ms AC.但作为一个平均复杂度O(n)的算法来说,unordered_map在这个数据量上的表现并不理想。   #include <cstdio> #include <unordered_map> using namespace […]