Ciel's blog
文章 标签 分类 系列
Ciel's blog

Coursera 课程《算法，第一部分》全编程作业 100 分总结

Ciel Yang  收录于  类别 学习 课堂笔记
     约 4124 字   预计阅读 9 分钟 

算法课程的作业都很精巧、很有趣，但是全都拿到 100 分可真是不容易，这里记录个人的满分心得，也算式阶段性的小总结。

第一周 Percolation

第一周的作业相对简单，更多的是为了让学生熟悉作业流程，而且引发编程的兴趣——毕竟能够解决复杂的现实问题比进行单调的数理分析有趣得多。本题的绝大部分编程要点在说明文档中都有详细的阐述，此处不再赘述。 唯一需要注意的就是“回流”（washback）问题的处理，即引入了最下层虚拟区块引发了不明显的 bug：如果当前系统确实渗漏，可能有一些实际没有连通到最上层的开放区块，因为和最底层的开发区块相连，经由虚拟区块联通到了最上层。解决方案就是额外再维护一个并查集，其中没有最下层虚拟区块，只是为了判断各个区块是否真的和顶层相连。也无需担心这样会拖慢系统的运行，毕竟数据集较小的时候额外的并查集操作不会耗费太多时间，而数据集较大的时候不引入虚拟区块的迭代判断更加耗时。

第二周 Queues

Deque 类的实现较为简单，安装课堂中正常的栈或者队列的实现方法都可以，个人实现的时候使用了双向链表。而 Permutation 类实际上依靠 RandomizedQueue 就能很轻松解决，不多赘述，所以关键在 RandomizedQueue 的实现。

因为涉及随机化的存取，所以使用数组作为底层数据存储结构比较方便（而且个人已经使用链表实现了 Deque，这里再用数组算是对课程的全面复习了）。这里面要注意：

  • 题目要求删除随机元素的时候操作时间是常数级，那么就不能想当然的直接使用数组的删除办法了。解决方法很简单，毕竟这个队要求完全随机化，那么就无需特别在意它的内部存储顺序，直接把待删除的元素和最后的元素交换，然后删除末尾元素即可
  • 本类中无需保证队列的 FIFO 属性，那么无需像基本队列的数组实现一样维持一个队首引用，然后不断进行复杂的首尾引用关系判断和计算，反倒应该类似栈的实现

迭代器的实现难点在于多个迭代器必须各自独立，还要保证都是对数据进行随机遍历。实际的实现方法是每个迭代器都是底层数据存储数组的下标的不同排列，这样在迭代访问的时候就能保证随机性，而且迭代器之间也不会产生相互影响（毕竟不能使用 remove() 也无需过度担心副作用）。而产生排序的方法使用课程提供的库函数 StdRandom.permutation() 即可，不要自己另写。

第三周 Collinear Points

本周的作业较为简单，首先不要在暴力解法上浪费太多时间，毕竟测试极其简单而且和快速解法的思路有不小差别。直接看快速解法的各种细节。

  • 后面的排序对稳定性有要求，那么比较方法也要注意相等值的判断，如果写错了后面是没法修正的
  • double 类型的比较有不少麻烦的地方，虽然题目建议直接比较即可，但是最好调用库函数 Double.compare() 更安全
  • 排序方法使用库方法 Arrays.sort()，效率更高也能保证稳定性

题目的参考资料给出的其实是以每一个点为端点的，包含 4 个点及以上点的线段集的求解方法，那么拓展这个解法的时候不可避免的就会碰到重复计数的问题。如果根据几何性质去思考共线、端点等问题，程序代码会飞速膨胀，而且解法效率也不会有多高。实际上，完全可以依靠稳定的排序来解决这个问题：

  1. 先对包含每个点的数组进行排序，也是下面步骤的迭代区域
  2. 在 1 得到的点排序结果数组上进行迭代，进行题目参考治疗提供的斜率排序，能得到每个点为端点的合要求的线段集，但是要注意：
    • 每次迭代都要对 1 中的结果进行复制，因为我们要靠点排序来去重复，如果不进行复制那么上一次斜率排序可能会对下一次造成干扰
    • 只要 Point 的代码完全符合要求，那么斜率排序的结果必然是相同的斜率基准点在排序结果首位（斜率为负无穷）
    • 每一段符合要求的线段，如果开始的端点比斜率基准点小，那么这个线段一定已经被记录了，可以跳过

虽然每次排序之前有一次数组复制操作，理论上性能不会很好，但其实这样去重复操作更简单，而且直接调用系统的数组复制方法操作内存实际运行速度无需担心。

评分时会测试构造器是否对参数内容进行修改，因为传入了一维数组所以直接调用 clone() 方法即可修正相应的 bug。

第四周 8 Puzzle

首先，本题大的思路基本已经交代清除，不用自己操心，但是很多细节的地方还是安排了不少小坑。

其实只要编程细节不太差，无需过于在意，个人实测 Board 类内部无论是采用二位的 int 数组还是一维的 char 数组存储数据都不会对结果造成太大的影响。某些比较消耗资源的测试数据在必须使用题目提供的算法的情况下，优化的空间实际不大，至少个人的笔记本都是吃不消后面的大数据测试的，而且在实际评分测试的时候也不会有太多影响。 如果自己机器的内存够大而且想看到后面数据的测试情况，那么不妨使用题目建议的内存压缩方案。而本人的最终答案在多次测试之后也懒得再改，直接使用一维 int 数组，也算是节省了一点点内存同时没有涉及了一些优化方案的编写细节，算是个利于学习的折衷方案吧。

真正可能导致个人运行以及评分在较小数据就出现内存问题的原因是，把过多的数据无脑堆放到类的域中。本题中 Solver 类必须使用 MinPQ 类，把各种操作的中间值保存在优先级队列中，如果把 MinPQ 的实例声明为 Solver 的域，那么就会导致内存评分无法悉数通过。我们也应该明白 MinPQ 在 Solver 类的其他地方没什么作用，实际根本没有必要延长它的声明周期。 当然，在 Solver 类的域中缓存答案路径是没有问题的，毕竟其他的方法会用到而且实际使用内存也不多。只不过还可以只保存结果搜索节点的引用，在需要输出答案的时候再延迟计算路径，这样会对性能有一定的优化，毕竟测试不会对一个 Solver 对象反复要求输出答案。（也可以避免 PMD 对非 final 域的警告，个人认为是 PMD 的脚本写的不太完善，有警告也不重要。）

这个方面是最需要注意的，毕竟最后有一百多条时间测试且数据量比较大。虽然时间测试总分中占比不大，一部分无法通过也没有关系（个人第一次提交时间测试通过率为 91/125，但总分仍然为 95），但如果追求满分的话那就必须要全通过了。

首先，是 Board 类中的一系列优化：

  • 避免每次调用 manhattan() 和 hamming() 方法都要进行复杂的计算，毕竟每个 Board 生成之后就不会改变，最好缓存它们的计算结果。另外，最好把 Board 作成 Immutable Class，虽然在个别的域处理上要花费一些功夫，但是实际的运行时间会有很大节省，而且也保证了优先级队列排序时不会发生奇诡的 bug
  • isGoal() 方法不需要进行复杂的数组逐项对比，只需要比较 hamming 是否为 0 即可
  • 生成新的 Board 对象时候会有数组复制操作，一维数组较简单直接调用库方法 Arrays.copyOf()，效率更高，二位数组注意实现相应的深拷贝
  • 最好另外声明一个 private 的构造器用来直接对新的 Board 对象进行初始化，因为 twin() 和 neighbors() 中产生的新的 Board 对象和原有对象的各种参数变化极小，可以避免过多的 manhattan() 和 hamming() 计算。都是两个区块的内容发生调换，导致整体的数据产生变化，只要重新计算连个调换区块的 Manhattan Code 和 Hamming Code 然后和原有数据进行简单的加减操作即可

然后，是 Solver 类中的优化：

  • 使用一个优先级队列缓存所有待处理的搜索节点，需要在设计节点时加上一个布尔类型域以判断棋盘是否在 twin 路线
  • 搜索节点的比较方法要避免过多的相等情况，可以在优先级相等的情况下再判断 Manhattan Code 的大小
  • 在搜索节点中缓存 manhattan() 的调用结果,因为测试程序判断时间花费的方法是计算不同方法的调用次数，而非实际运行的时间（我个人仅仅使用这个优化方案就满分通过了），如果没有缓存那么就会看到最后的测试结果中数量夸张的 manhattan() 调用计数
  • 能用库函数的真的尽量用库函数，比如：个人写的数组复制操作无论如何比不过库函数的（毕竟直接操作内存块）
  • equals() 方法要注意各种细节，如：
    • null 判断
    • 同引用判断
    • 同类型判断

第五周 Kd Tree

本周的作业相对简单，毕竟主要的步骤都在视频中一一讲明，而且时间复杂度和空间复杂度的要求都相对宽松，也没有要求必须保证树的平衡。尤其暴力算法，无需过于操心，测试数据不会太庞大，这里也就不再讨论。

本题使用了 2d 树来分隔平面，而且还有相对精细的画图要求，还有矩形范围搜索，那么为了之后的操作方便不妨在树的每个结点都保存包含这个结点的最小的矩形。以这个结点做水平或者竖直的分割线就会把矩形分割为两部分，然后左子树和右子树分别位于两个子矩形内。 实际的矩形构建操作也很简单，根结点的矩形就是整个画布的大小，而后逐步分割矩形：

  • 水平分割矩形时使用点的 y 坐标
  • 竖直分割矩形时使用点的 x 坐标

无需在每个结点保存分割线的朝向，因为本题没有删除操作，而且朝向只有 2 种，只要在递归方法中加入布尔类型的参数进行判断即可，每次进入子树就反转布尔参数。（题目要求根结点按照竖直方向进行分割）

插入操作一定不要插入重复元素，而且每次递归方法都把父结点的矩形作为参数传入，方便子结点构建新的矩形。 搜索操作中的比较操作要重新设计，根据每个递归方法的布尔参数（分割方向）分别判断：

  • 水平分割：插入点 x 坐标小于当前结点 x 坐标，则在左子树，否则在右子树
  • 竖直分割：插入点 y 坐标小于当前结点 y 坐标，则在左子树，否则在右子树

递归遍历每个结点，从方法的布尔参数获取分割方向，同时结合结点的矩形确定分割线的长度：

  • 水平分割：等于结点 y 坐标的不超过矩形的线段
  • 竖直分割：等于结点 x 坐标的不超过矩形的线段

另外，注意每个结点的点要使用 0.01 粗细的笔划出，分割线则使用默认粗细的笔刷，否则分割线会覆盖结点；同时每次画点或线都要重新调整笔刷的粗细和颜色。

对每个结点先判断点是否在矩形内部，是则加入结果集合，然后判断是否要进入子树搜索：

  • 如果左子结点的矩形和目标矩形相交，则进入左子树搜索
  • 如果右子结点的矩形和目标矩形相交，则进入右子树搜索

注意：不要使用目标矩形是否包含子结点的点来进行判断，会遗漏部分符合条件的点。比如：假设左子结点为竖直分割，矩形不包含左子结点，但是仍然可能包含左子结点的右子树中的点。

理论上，可以剪枝部分搜索情况以加速搜索操作，即通过题目已经提供的矩形到点的距离的方法来进行判断。 比如：对一个结点进行搜索时，发现搜索点如果插入树中应该位于左子树，这个时候就取出右子结点的矩形，求这个矩形到搜索点的距离，如果结果小于已经得到的最短距离，那么就要去右子树搜索，否则可直接略过右子树的搜索。 这是因为，右子结点的矩形必定包含了包括它在内的所有子树中的点，而题目给出的矩形到点的距离就是点到矩形任意一点的最短距离，如果这个距离比已经搜索过的最短距离还要大那么右子树里面任何点都不可能距离目标点更近。

更新于 2019-04-25
 Coursera, Java
返回 | 主页