homework-09-程序员宅基地

0 需求

这次作业需要实现一个动态求解过程展示，在homework2里我们已经实现了对一维/二维矩阵的最大子矩阵和求解，并且能支持-h和-v（本次作业中没要求-a吧？）。程序需要再支持单步执行和自动执行，并且要有随机生成测试数据的功能。对于求解的每一步都用直观的图形展示。

1 分析

由于网页展示有加分，所以选择在网页上实现。

稍微分析了一下，觉得网页实现大概有这三种形式：

1. 用Javascript读入文件，通过Javascript计算最大子矩阵，再通过Javascript操作DOM来实现动态展示
2. 用html选择文件，Post文件到服务器端，服务端计算结果，并且不断和浏览器的Javascript交互，来实现动态展示
3. 基本和2类似，不过在文件Post到服务器端后，服务器端语言(Ruby,jsp,php,python等)计算完每一步的结果，保存为某种信息传输形式，并开辟一个可访问的接口。浏览器端的Javascript用Ajax从该接口获取信息，并在浏览器上展示出来。

第一种方法有一个很明显的好处，因为它是完全通过Javascript写的，不需要服务端来支持，只需要一个html文件就能在任何可访问html静态网页的地方运行。

第二种方法把任务分割了，服务器端负责计算，而浏览器端负责展示和绘图。该方式的难点在于浏览器与Javascript的交互比较难实现（先不考虑websocket），需要定义好交流的时序和通讯格式。

第三种方法的好处是，我可以选择一门我比较熟悉的语言来实现服务器端。浏览器发送一次请求之后，服务器段经过一次完整的计算求解，算出最后结果，并且把求解步骤保存成一种可供数据交互的格式（在这里我采用Json），浏览器从服务端再次获取求解过程数据，然后就可以脱离服务端来进行展示。一次计算需要2个http请求。

相比于方式一的纯javascript实现来说，这个方法（方法三）很好地分割了C(controller)和V(view)这两个视图，javascript作为一个浏览器语言，其主要目的是为静态的html增加一定的动态性，而如果把它当作一种计算的手段，虽然说原则上它完全可以完完成计算求值，但并不能很好地发挥Javascript的真正优势。如果把计算任务转交给服务器去实现，让高效的语言去实现计算，就可以让javascript专注于浏览器端的展示效果。这样代码编写起来功能也较为明确。

我使用的是方式三。

2 服务器端

这次我依然使用webpy这个轻量级python的web框架。实现功能很简单，仅用了2个url映射：

urls = ('/', 'Upload','/history','His')

其中根路径/对应到Upload处理类，/history对应到His处理类，其中Upload处理类有3个方法：

1. cacu ：传入待求解的矩阵和相关选项（-v,-h），对矩阵进行动态规划求解，并把求解过程转换为Json格式，存入his.json文件
2. GET：对于每个对根路径的请求，返回默认的index.html
3. POST：对于每个Post请求，首先判断是否有上传文件，如果有上传文件则读取文件，没有上传文件则根据网页的输入信息生成随机矩阵。之后传入cacu函数进行计算，后渲染新的index.html，展示所读取到的矩阵。

其中cacu求解过程使用了homework2中的单调队列求解方法，可以把所有的情况（-v,-h,一维）的情况都划归到同样的求解模型，简单有效。

而His处理类只有一个方法：

1. GET：读取His.json，返回所读取到的内容。

代码如下：

import web                                                                                          
import string                                                                                       
import random                                                                                       
import copy                                                                                         
import json                                                                                         
                                                                                                    
urls = ('/', 'Upload',                                                                              
                '/history','His')                                                                   
render = web.template.render('templates/')                                                          
d = [1,1,[[0]],5,5,-10,10]                                                                          
                                                                                                    
class His:                                                                                          
        def GET(self):
                f = open("his.json","r")
                s = f.read()
                f.close()
                return s

class Upload:
        def cacu(self,f,n,m,h,v):
                his = []
                que = [[-1,0]]
                maxv = {
     'sum':f[0][0],'a':0,'b':0,'c':0,'d':0}
                if h or v:
                        for i in range(0,n):
                                if h:
                                        f[i] += f[i]
                                if v:
                                        f += [f[i]]
                M = m
                if h:
                        M = 2*m
                N = n
                if v:
                        N = 2*n
                for i in range(0,n):
                        p = [0]*M
                        for j in range(i,min(N,i+n)):
                                sumv = 0
                                que = [[-1,0]]
                                for k in range(0,M):
                                        while len(que)>=1 and k-que[0][0]>m:
                                                que.pop(0)
                                        p[k] += f[j][k]
                                        sumv += p[k]
                                        nowv = {}
                                        nowv['sum'] = sumv-que[0][1] 
                                        nowv['a'] = i % n 
                                        nowv['b'] = (que[0][0]+1)%m
                                        nowv['c'] = j % n
                                        nowv['d'] = k % m
                                        if nowv['sum']> maxv['sum']:
                                                maxv = copy.deepcopy(nowv)
                                        his.append({
     'max':maxv,'now':nowv})
                                        while len(que)>=1 and que[len(que)-1][1]>sumv:
                                                que.pop(len(que)-1)
                                        que.append([k,sumv])
                f = open("his.json","w")
                json.dump(his,f)
                f.close()

        def GET(self):
                return render.index(*d)

        def POST(self):
                x = web.input(myfile={})
                low = string.atoi(x['low'])
                hig = string.atoi(x['hig'])
                if x['myfile'].value!= '':
                        if x['myfile'].filename == '':
                                return render.index(*d)
                        f = x['myfile'].value
                        f = f.split("\n")
                        n = string.atoi(f[0].replace(",",""))
                        m = string.atoi(f[1].replace(",",""))
                        f = f[2:]
                        f = [[string.atoi(j) for j in i.split(",")] for i in f if i is not '']
                else:
                        n = string.atoi(x['hsize'])
                        m = string.atoi(x['lsize'])
                        f = []
                        for i in range(0,n):
                                f += [[]]
                                for j in range(0,m):
                                        f[i].append(random.randint(low,hig))
                self.cacu(f,n,m,"h" in x,"v" in x)
                return render.index(n,m,f,n,m,low,hig)


if __name__ == "__main__":
        app = web.application(urls, globals()) 
        app.run()

 3 网页端

 稍微总结了一下网页端的需求：

1. 需要选择一个矩阵文件
2. 用户可以自己定义一个矩阵的大小，要生成一个随机矩阵
3. 要有单步执行和自动运行功能
4. 需要有回滚功能
5. 要动态展示当前最大的矩阵，当前计算的矩阵

对于需求1,很容易可以使用一个<input type="file">来请求用户输入文件，而<input type="submit">能够把所选取的文件上传到服务器。而当用户并没有选取文件时，需要几个<input type="text">来读取矩阵大小，随机数范围。

对于单步执行，只需要使用“指针”对得到的历史记录数组进行随机访问就能实现单步执行，而且回滚功能也异常简单。

对于自动执行，可以使用setTimeout(function,ms)，这个函数向浏览器请求一个功能：在ms毫秒之后，唤醒（执行）function函数。于是我们可以在单步执行的函数的末尾加入setTimeout，于是每次单步执行完之后，经过一段时间又会自动执行单步，来达到很简单的自动执行功能。

对于动态显示其实很简单，只需要对画出的table元素进行动态设置颜色和方框就行。

解释一下index.html里涉及到的几个函数和全局变量：

1. NOWB ：表示当前步数
2. SPEED：表示当前执行速度，speed=0时只允许单步执行。
3. HIS：历史执行信息数组，从服务器端口获取到的
4. set_color：对指定的(i,j)表格元素设置颜色
5. set_border：对指定的(i,j)表格元素设置边框属性
6. get_json：使用Ajax从/history上获取json格式的历史信息，存入HIS变量
7. draw：对传入的步骤数x和类别w进行绘制指定颜色和边框，它调用了set_color和set_border
8. renew：把所有表格设置为初始颜色和边框
9. draw_it：对NOWB进行绘制，调用draw
10. draw_next：把NOWB+1,并调用draw_it绘制
11. draw_last：把NOWB-1,并调用draw_it
12. auto_go：当速度大于0时，调用draw_next进行下一步绘制，当数度小于0时，调用draw_last绘制。并且当速度不为0（也就是正在自动执行）时，在函数的最后执行setTimeout(auto_go,1000/Math.abs(SPEED))，这意味着速度越大，执行的周期越短，频率越大。
13. stop：设置SPEED=0,停止自动执行
14. go：传入参数x，把速度SPEED加上x，在这里，go函数只被>>和<<按钮调用，分别使用了go(1)和go(-1)，也就是说每一次按按钮则增加1或减少1的速度。
15. check：对输入的随机信息进行有效性判断，在这里规定了所生成的矩阵长宽都必须是正整数，随机数的下界小于等于上界，矩阵长宽都不能大于50

index.html 

$def with(n,m,f,hsize,lsize,low,hig)
<html>
        <head>
        <title>HeiHei</title>
        <script type="text/javascript" src="./static/index.js"></script>
        <link rel="stylesheet" type="text/css" href="./static/index.css" />
        </head>
<body align="center" onload="get_json()">
        <h1>一维/二维最大子矩阵和求解图形化展示</h1>
        <p align="right">by <b>forwil 11091222</b></p>
        <form method="POST" enctype="multipart/form-data" action="">
                <hr/>
                <input type="file" name="myfile" />
                <br/>
                <input type="submit" value="Start" onclick="return check();">
                -h<input type="checkbox" name="h">
                -v<input type="checkbox" name="v">
                <br/>
                Row = <input type="text" name="hsize" id="hsize" class="t" maxlength="4" value="$hsize">
                Col = <input type="text" name="lsize" id="lsize" class="t" maxlength="4" value="$lsize">
                <br/>
                Random From = <input type="text" name="low" id="low" class="t" maxlength="4" value="$low">
                to = <input type="text" name="hig"  id="hig" class="t" maxlength="4" value="$hig">
                <hr/>
                <input type="button" value="Stop" onclick="stop()">
                <br/>
                <input type="button" value="<<" onclick="go(-1)">
                <input type="button" value="<" onclick="draw_last()" >
                Step:<span id="step">0</span>
                <input type="button" value=">" onclick="draw_next()">
                <input type="button" value=">>" onclick="go(1)">
                <br/>
        $if f:
                n = <b>$n </b>
                m = <b>$m</b>
                Speed = <b id="speed"></b>
                <table align="center" id="table">
                $for i in range(0,n):
                        <tr>
                        $for j in range(0,m):
                                <td>$f[i][j]</td>
                        </tr>
                </table>
                Now sum = <b><span id="now"></span></b><br/>
                Max sum = <b><span id="max"></span></b>
        </form>
</body>
</html>

index.js

                var NOWB = -1;
                var SPEED = 0;
                var set_color = function(i,j,co){
                        if (co!="" && i<n && j<m){
                                document.getElementById("table").rows[i].cells[j].style.background = co;
                        }
                }

                var set_border = function(i,j,st){
                        if (st!="" && i<n && j<m){
                                document.getElementById("table").rows[i].cells[j].style.border = st;
                        }
                }
                var get_json = function(){
                        var xmlhttp = new XMLHttpRequest();
                        xmlhttp.open("GET",window.location.href+"history",false);
                        xmlhttp.send();
                        HIS = eval("(" +xmlhttp.responseText+")");
                        n = document.getElementById("table").rows.length;
                        m = document.getElementById("table").rows[0].cells.length;
                        return true;
                }
                var draw = function(x,w,co,bo){
                        var i,j,a,b,c,d;
                        a = HIS[x][w]['a'];
                        b = HIS[x][w]['b'];
                        c = HIS[x][w]['c'];
                        d = HIS[x][w]['d'];
                        i = a -1;
                        do{
                                j = b -1;
                                i = (i + 1)%n;
                                do{
                                        j = (j + 1)%m;
                                        set_color(i,j,co);
                                        set_border(i,j,bo);
                                }while(j!=d);
                        }while(i!=c);
                        if (NOWB!=-1){
                                document.getElementById(w).innerHTML = HIS[x][w]['sum'];
                        }
                }

                var renew = function(){
                        var i,j;
                        for(i=0;i<n;i++)
                                for(j=0;j<m;j++)
                                {
                                        set_color(i,j,'white');
                                        set_border(i,j,'2px dotted black');
                                }
                }

                var draw_it = function(){
                        var i,j;
                        renew();
                        if(NOWB>=0){
                                draw(NOWB,'now',"#AAAAAA","");
                                draw(NOWB,'max',"","2px solid blue");
                        }
                }

                var draw_next = function(){
                        if(NOWB < HIS.length-1){
                                NOWB += 1;
                        }else{
                                SPEED = 0;
                        }
                        draw_it();
                        document.getElementById("step").innerHTML = NOWB+1;
                }

                var draw_last = function(){
                        if(NOWB>=0){
                                NOWB -= 1;
                        } else{
                                SPEED = 0;
                        }
                        draw_it();
                        document.getElementById("step").innerHTML = NOWB+1;
                }

                var auto_go = function(){
                        if (SPEED>0){
                                draw_next();
                        }
                        else if (SPEED<0){
                                draw_last();
                        }
                        if (SPEED){
                                setTimeout("auto_go()",1000/Math.abs(SPEED));
                        }
                }

                var stop = function(){
                        SPEED = 0;
                        document.getElementById("speed").innerHTML = SPEED;
                }

                var go  = function(x){
                        if (SPEED == 0){
                                SPEED = x;
                                auto_go();
                        }else{
                                SPEED += x;
                        }
                        document.getElementById("speed").innerHTML = SPEED;
                }

                var check = function(){
                        var hsize = document.getElementById("hsize").value;
                        var     lsize = document.getElementById("lsize").value; 
                        var low   = document.getElementById("low").value;
                        var hig   = document.getElementById("hig").value;
                        if (hsize<=0 || lsize <=0 || low>hig || hsize >50 || lsize > 50){
                                alert("Number your input isn't available!")
                                return false;
                        }
                        return true;
                }

4  效果展示

蓝色边框区域是目前最大矩阵，灰色区域是当前计算的矩阵。

5 其他

代码覆盖率

由于本次作业用了Python服务端和Javascript前台进行混合编写，所以需要分别测试两个的代码覆盖率。Js找到了一些包比如Jscover，但是因为我的网页是python动态生成的，搞了好久硬是没有把代码覆盖率测出来。

代码风格

由于实现功能较简单，所以没有采用面向对象的程序设计方法。看了一下Js发现Javascript的函数和Scheme十分相像，所以在Js内用了很函数式的编码方式，比如一般js定义一个函数是用function FUNCNAME(){}，而用函数式风格的定义就是var FUNCNAME= function(){}。因为js函数是基本类型的特性，再加上支持函数闭包，所以写起来还是很有模块化的，各个函数的功能明确。

命名风格

由于本人对长单词的深深恐惧感，所以命名采用C风格。在js中，全局变量统一用全大写表示，函数名如果是两个单词的话，用下划线隔开。如果单词长度超过6个，则取前4个。除了全局变量之外所有名称全用小写，比如“set_border” “get_json” “draw_it”。具体命名见上述浏览器端的说明。

时间记录

预计时间	5h	实际用时	7h
代码规范	0.0h		0.0h
具体设计	0.5h		1h
具体编码	3.5h		4h
代码复审	0.0h		0h
代码测试	0.5h		1h
测试报告	0.5h		0.5h

6 动态规划

严格来说，这次求解我并没有采用原先的经典动态规划来做，而是采用了单调队列来动态求值。这种方法能很好地用一个通用模型解决一维，-v,-h的情况。

我对动态规划的理解有这么几点：

1. 其本质是牺牲空间效率换取时间效率
2. 状态表示需要满足无后效性
3. 状态表示需要满足最优子结构

高中搞竞赛对动态规划题做得比较多，动态规划确实博大精深，往简单地说有最长递增子序列最长公共子序列，往难的有状态压缩动态规划、配合线段树后缀数组等高级数据结构的动态规划，还有各种基于单调性的优化方法。但总的来说还是离不开上面的3条规则。

想要理解动态规划的内涵，最简单的方法就是多接触各种模型，在这里推荐一下著名的vijos.org里的动态规划专栏：

https://www.vijos.org/p/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

下面分析和解释一下在本题中是如何使用单调队列来求解改问题的：

令sum[i]表示sigma{a[j],1<=j<=i}(其中sum[0]=0)，我们的目的是最大化sum[a]-sum[b]，即：

ans=Max{sum[a]-sum[b],0<=b<=a<=m}

从左向右循环，记录最小的sum[min]，对于每个i，以a[i]结尾的最大和的子串就是sum[i]-sum[min]，所以只需要不断更新sum[min]并计算最大的sum[i]-sum[min]就行了。时间复杂度也是O(N)。

为了限制长度i-min<=m，可以维护一个队列dd[]，其中队头是t,队尾是w。其中dd[i].value是其sum值，而dd[i].id是该sum值对应的i。

维护队列t-w按dd[].value从小到大排序，每次取出dd[t]便为需要的sum[min]。而每次计算完一个sum值需要插入到队尾。

若dd[t].id距离当前i大于m，也就是取得了不符合规定的区间，那么该dd[t]就不能被使用，显然该值同样不能被大于i的sum使用，所以应该让其出队。

新加入的sum[i]到dd[w]中需要做一次插入排序，而显然所有大于sum[i]的队列里的元素都应该被去除。

所以在一次循环中，每个点只会进入单调队列一次,而且再被插入的时候就会被淘汰。所以维护单调队列不会带来复杂度的增加，仅会带来常数的增加。所以时间复杂度依然为O(n^2*m)