Algorithm Princeton part II (week2)

Week2的作业也是越来越难了啊，各种小细节没注意到，调了好几次才满了。。大家多多讨论~

这次作业就拿了90分。最后放弃调试了，因为错误都没了。剩下的就是 他觉得我内存用多了。我把所有用过的对象都申明为null，以此减少内存，但是还是太多。我想应该是我实现方法是有问题吧。我是这么做的。用一个二维数组来记录到每一个点最短的energy和。再用一个二维数组记录到每一个点的最短路径上一行的点，类似于edgeTo[].
然后我把topological order压入栈中，按照老师讲的方法来寻找最短路径，并且不断优化距离。中途也犯过很多错误，但是经过大量时间调试后都解决了。就是这个内存问题。
他测的是 五次水平删除后 这个Seam对象所占的大小。只有类成员才会占内存，所以我在每次删除后，都会将这些大型数组指向null。等到下次删除时，再重新生成这些数组。这样的确会浪费一些运行时间，但应该所占用内存会很小啊，怎么会还是这么大。不理解。
后来我也想过，每次删除后不释放那些大型数组，而是再次刷新。后来太累了，想不动了，就放弃了。
我觉得topological order总有BFS的影子。一直这么觉得。最短路径算法，就是一层层向外推进，被推到的点，都将被确认为最短路径点。然后以此作为根据，继续向外推进。一层一层，不就是BFS么。。。
还有一个教训，写代码最好的就是一口气写完。我本以为写的差不多了。然后就和一同学闲聊了好久。结果回来继续写发现第一次提交就44分，自己那种状态也没了，很浮躁。浪费了大量的时间来调试。而且把很多对的逻辑又改错了，走了挺多冤枉路。
Anyway, week2 终于又搞定了。应该还有三节课了吧，一定得跟下去啊。。。
大四了，大家都在玩了。我怎么越来越想放弃这门课了。。。虽然他对我的帮助真的很大。

Part2的作业比part 1更自由了，这次的作业好实用，之前攒的小技巧马上亮起来O(∩_∩)O~

基本思路：在算最短路径的时候加一个virtual top和virtual bottom，分别连接top row和bottom row，相当于找virtual top和virtual bottom的最短路径。

Tips：

1)      我比较迷糊所以就把energy用getter和setter包起来，统一用pixel（x,y）获取，不知道这样对计算时间有什么影响~

2)      新写了一个类acyc传入picture计算seam返回来，在SeamCarver里类变量只有picture，除了remove其他操作都在新类进行（这样SeamCarver看起来比较干净？）

3)      Horizontal和vertical的点relax扩展方向不一样~要跟topologicalorder的逻辑一致

Q：比较困扰的是throw exception，我都是单独拿出来判断，觉得每次调用前都判断很费时~大家有没有什么好的解决方案吖

交作业

这次作业有点像脑经急转弯，想通了很简单，想不通很麻烦。
我一开始写着写着，就用brute force方法去做了，结果很复杂，代码很长，写了也很久，然后timing肯定不通过，脑子都糊涂了。
然后突然开窍，5min就写完那个findverticalseam了。

正确的解法应该是：将energy矩阵，从左到右，从上到下，每个点遍历一边（这是Topological order），遍历时求出下一行对应点的disTo和edgeTo，就可以了。

这次作业真的太精彩！！直接实现了一个PS里的图像压缩算法！！超有成就感～

thomaschan 发表于 2015-4-3 01:11
这次作业真的太精彩！！直接实现了一个PS里的图像压缩算法！！超有成就感～

系统帅哦

letsdoit666 发表于 2015-4-3 18:29
交作业

哈哈，加油~

czbnlzd920706 发表于 2015-4-8 09:27
这次作业就拿了90分。最后放弃调试了，因为错误都没了。剩下的就是 他觉得我内存用多了。我把所有用过的对 ...

真心拼！distTo应该不需要用二维，中间的那些不用保存吧，只要保存最后一行，以及edgeTo就可以了。大四现在不学也过去了更辛苦，和你一起加油！

交作业啦，自己实现了路径搜索算法，还是蛮有趣的。

czbnlzd920706 发表于 2015-4-8 09:27
这次作业就拿了90分。最后放弃调试了，因为错误都没了。剩下的就是 他觉得我内存用多了。我把所有用过的对 ...

你可以试试只用color的int数组作为instance variable，然后dist和energy那些都在find方法里创建，我是这么做的，通过了

gqjapply 发表于 2015-4-13 01:42
你可以试试只用color的int数组作为instance variable，然后dist和energy那些都在find方法里创建，我是这 ...

好的。但有个疑问，放在外面申请和放在里面申请这些数组，类所占空间大小应该一样啊？就算我是在外面申请的，我每次操作结束后都让他指向null就不占内存了啊。。