现代程序设计作业9

问题需求

这次作业要求将之前做过的最大子数组和问题的动态规划过程用程序展示出来，并实现控制输入文件、随机生成文件、逐步执行、自动逐步执行和改变模式等功能。

解决方案

由于在网页上实现有加分，又本着顺便学一学web开发的想法，我选择了网页实现。html是完全静态的很好学，但javascript跟我之前接触过的语言有较大不同，学起来花了不少时间（当然乍一看js还是跟主流语言很像的）。

文件读入

首先在读入文件上花了点功夫。我想实现的是一个最常见的上传文件的功能。包含一个浏览按钮，点击后弹出文件浏览器，选择之后再提交，并让js获取文件进行之后的处理。控件之类的很好弄，关键是如何把文件提交到本地。

我一开始是想获得所选文件的本地路径，再由js去打开，后来意识到这是办不到的，因为不可能让js直接获取到客户端的文件，这是极为不安全的，只能通过用户主动提交。明白这一点后就知道了所要做的就是把提交的文件拦下来。

通过查资料了解到有专门的FILE API来实现这个功能。要做的就是获取input控件并取得它的files属性，该属性就是所提交的文件数组，取file=files[0]即可。然后再用FileReader对象将该文件读取进来reader.readAsText(file)。

这里遇到了问题。reader有一些叫做onload、onprogress之类的属性，这些属性会在读取文件的相应时机被触发、并执行所设定的动作。这些属性是函数对象，一般是用匿名函数的方法对其赋值。我按照网上的方法令reader.οnlοad=function(){sStr = reader.result;}，然后调用reader.readAsText(file)，之后再输出sStr的值。令我百思不得其解的是其值竟然为空。更奇怪的是在之后别的地方再输出sStr又出现了正确的结果。这种情况在当时看起来是极其奇怪的。

事实证明这种及其不符合常理的情况的出现往往是因为在关键的地方理解错了。后来看了一些代码我才明白，这些触发事件是异步处理的。在执行reader.readAsText(file)之后并不会等reader.onload执行完毕，而是直接向下执行。这就解释了刚才那种看起来很不合理的情况：先输出了一次是空的，再输出就又正确了。这说明第一次输出时文件还没读完。这也解释了我一开始看别人代码时的疑问：为什么reader.readAsText(file)一般都是最后一句，之后的过程都放在reader.onload里。这样就解决了文件的读入。

计算

之后要做的就是计算了。我又想让js直接调用我之前写好的程序，查了一下后发现只有ActiveX能做到，还需要设置浏览器的安全等级。后来意识到这跟之前一样，是很不安全的行为，应该时刻注意web应用是基于用户的请求的，如果网页能随意执行本地程序，那哪还有安全可言。于是我只能将原来的程序改写为js，顺便也优化一下，-a参数的代码太长了而且也不是动态规划，没有改写那部分。js毕竟是弱类型，写起来还是比较容易，正则表达式这个东西一句话解决了之前的一大段代码。

单步功能

改写完成后就要实现单步功能了。这个问题更是困扰了我很长时间（大概有一个下午）。我的想法一直局限于让计算过程中途暂停，等待用户响应。我查了很久关于程序暂停的资料，发现都实现不了我想要的。后来发现js实际上是单线程的，越发的感觉难以实现。后来还是forwil同学提醒了我：直接保存单步状态。我瞬间觉得我就一脑残！好吧这个问题就这么瞬间解决了。

自动单步

然后就是自动单步功能了。自动一步一步执行倒是容易实现，但如何停止？注意如果用循环实现，在循环过程中页面是无法响应的。主要还是因为js的单线程。

后来我又发现了setTimeout函数，这个函数可以在经过设定的时间后执行一些代码。这样通过递归调用就能实现了。比如要执行一个函数f，那么在函数f内调用setTimeout(f,1000)就会每隔一秒执行一次f。通过设置停止标志就可以停止（if(timetostop)return;)。

但问题又来了：这样的停止是不完美的。这个情况有些复杂。setTimeout相当于向事件队列中添加事件。一般的停止过程是这样的：点击停止->timetostop变为true->当事件队列中的函数执行时判断发现timetostop=ture直接退出。但有时候我可能点击了停止后马上又点击开始，那么timetostop会被改为false，这时还未轮到执行的队列中的函数就无法停止了。也就是说这种方法无法立即停止函数，而是要等到想停止的函数执行时让它退出。

后来我又发现了setInterval方法和clearInterval方法，前者是定期的执行某个表达式，后者是清除某个setInterval开始的事件队列。这不是很好！这两个函数可以非常简单干净的实现我想要的功能。

但还没完，后来我又想实现改变自动单步速度的功能。令人失望的是setInterval的周期是一开始就设定好的，中途不能更改。怎么办？我又查到clearInterval也能作用于setTimeout。注意setTimeout是通过自调用实现循环执行的！也就是说每次调用的时候我都能更改setTimeout的延迟参数！最终解决办法就出来了：用setTimeout自调用实现循环，而延迟参数设为全局变量speed。用户点击+-按钮时只要改变speed的值就可以了，这样就自动实现了变速，而且可以随时停止，甚至可以直接在前进的过程中直接点击后退。

着色

还有一个着色的问题。我要显示的最大子数组和的动规过程，自然要把每一步的中间结果显示出来。我用用色表示当前计算的状态，并给出红色区域的和。但只有这一个是不太直观的，最好还能显示出最优解的变化过程。于是我又保存了一个到当前状态为止所产生的最优解。因为这个区域可能和当前状态区域重叠，所以我想换一种方式把它标记出来，比如把区域的边界框起来。无奈不太会操作表格的边框，我最终选择了用不同的颜色标记。我用红色标记到目前为止得到的最优解，重叠的部分用橙色表示。

改变模式

关于改变模式，我实现了横向纵向连接的情况，用两个复选框让用户选择。具体实现在作业2中说过，把矩阵横向或纵向（或同时横向纵向）复制，然后利用单调队列即可实现。联通的部分没有实现，因为代码太长了，而且对那个模式单步也没什么意义。随机生成数据很简单就不多说了。

代码质量

命名规范

本来不想用全局变量的，后来发现好像不可能，最终决定让全局变量全部大写，其余的都全小写。变量名意思都比较明显，所以这样就足以表达清楚含义。

结构

这次对程序结构做了比较认真的分析，函数功能明确并且尽可能的减少了冗余与不一致。

注释

有足够的注释

单元测试

使用QUnit保证了每个模块的正确性。基于测试的开发的确是比较有效率的，但本次作业中大多错误都是理解性的，单元测试并没能提供多大帮助。

代码覆盖率

最终使用JSCover搞定。一开始试了scriptcover，无奈需要在服务器上测试，而且也有2年没更新了。JSCover也花了些功夫，因为几乎没有资料可查，最后还是看的官方的用户手册，几乎全看了一遍才找到我想要的基本功能。它是靠重新编译js文件插入分析代码实现的，但它的官方手册前面说了一大堆就是没说怎么重新编译。最后我丧心病狂的把覆盖率刷到100%。

截图

总结

这次作业让我发现了许多问题，也解决了这些问题，学到了不少东西，收获还是很大的。对js的学习让我对函数闭包与函数式编程有了更多的了解。js还是基于原型的语言，与主流语言大不相同，完全新的思想让我很感兴趣，不过这次作业没有用到，有时间再深入了解一下。

关于动态规划

其实准确的说我并没有用动态规划解决这个问题。最大子数组和一般最常用的是动态规划解法：以f[i]表示以第i个数为结尾的最大子数组和，那么如果f[i-1]>0则f[i]=f[i-1]+a[i]，否则f[i]=a[i]。这种做法非常简单，但如果要实现数组左右相连的情况就不是很好用了（其实也还好，如果要实现左右上下相连则有点麻烦了）。用动态规划的方法实现左右相连的时候，要先求最小子数组和，然后用全部的和减掉最小即可。一维的时候还比较方便，如果是二维左右上下都相连就不太好用了：首先要去掉中间的一段横条，剩下上下两个横条，再把这两条看成一个一维数组，求最小子数组，再用总和减去这个最小子数组。

我用的是另一种方法：用min[i]表示sum[1]到sum[i]的最小值，那么f[i]=sum[i]-min[i-1]。只要能维护min的值就好了。维护min的时候算是动态规划吧，min就是一个前缀最小值。当需要左右相连的时候，我采用了复制数组的方法。即令a[n+i]=a[i]，i = 1 to n，在这个是原来2倍的数组上求最大子数组和。但与之前有一点区别，就是之前的min[i]是前缀最小值，而现在min[i]是i之前连续最多n个sum的最小值。因为f[i]=sum[i]-min[i-1]，而min[i-1]=sum[j]，若i与j的差大于n则这个子数组区间超出了n个数，相当于重复了。于是现在min[i]是一个区间的最小值，而区间是随i单调递增的。这可以用单调队列维护。单调队列还是很好写的，写好之后无论是上下还是左右还是同时相连都可以用这一种方法解决了（如果上下左右都相连则把矩阵长宽都变为原来的2倍）。个人感觉这种做法更好。