一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 826|回复: 15
收起左侧

Algorithm Princeton part II (week2)

[复制链接] |试试Instant~ |关注本帖
18258170717 发表于 2015-4-1 11:33:12 | 显示全部楼层 |阅读模式

[Coursera]Algorithm part II #2 - 2015-3-20@Princeton

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

week8

week8

评分

1

查看全部评分

thomaschan 发表于 2015-4-3 01:11:47 | 显示全部楼层
这次作业真的太精彩!!直接实现了一个PS里的图像压缩算法!!超有成就感~
2015-04-03 01:05:36 的屏幕截图.png
2015-04-03 01:06:06 的屏幕截图.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-4-3 07:57:49 | 显示全部楼层
thomaschan 发表于 2015-4-3 01:11
这次作业真的太精彩!!直接实现了一个PS里的图像压缩算法!!超有成就感~

系统帅哦
回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-4-3 18:29:06 | 显示全部楼层
本帖最后由 gjxwin 于 2015-4-3 18:33 编辑

交作业
Screen Shot 2015-04-03 at 18.19.42.png


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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-4-3 19:07:18 | 显示全部楼层

哈哈,加油~
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| 18258170717 发表于 2015-4-8 09:35:41 | 显示全部楼层
czbnlzd920706 发表于 2015-4-8 09:27
这次作业就拿了90分。最后放弃调试了,因为错误都没了。剩下的就是 他觉得我内存用多了。我把所有用过的对 ...

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

使用道具 举报

Josh 发表于 2015-4-10 20:29:05 | 显示全部楼层
交作业啦,自己实现了路径搜索算法,还是蛮有趣的。
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gqjapply 发表于 2015-4-13 01:42:13 | 显示全部楼层
czbnlzd920706 发表于 2015-4-8 09:27
这次作业就拿了90分。最后放弃调试了,因为错误都没了。剩下的就是 他觉得我内存用多了。我把所有用过的对 ...

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

使用道具 举报

czbnlzd920706 发表于 2015-4-13 06:27:57 | 显示全部楼层
gqjapply 发表于 2015-4-13 01:42
你可以试试只用color的int数组作为instance variable,然后dist和energy那些都在find方法里创建,我是这 ...

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

使用道具 举报

gqjapply 发表于 2015-4-13 07:00:55 | 显示全部楼层
czbnlzd920706 发表于 2015-4-13 06:27
好的。但有个疑问,放在外面申请和放在里面申请这些数组,类所占空间大小应该一样啊?就算我是在外面申请 ...

这个我也不是太清楚了,按照java回收机制应该是这样,但他的OJ到底怎么测的具体也不知道。可能是删除的时候他不希望你用太多的空间吧,这个时候应该是不需要dist和energy那些数组的。他的memory检测有时候的确很奇怪,我们只能尽量精简吧。
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-4-13 07:45:31 | 显示全部楼层
gqjapply 发表于 2015-4-13 07:00
这个我也不是太清楚了,按照java回收机制应该是这样,但他的OJ到底怎么测的具体也不知道。可能是删除的时 ...

恩恩。多谢提示!我也觉得我那样子直接放在外面不太好。
回复 支持 反对

使用道具 举报

热情bruce的 发表于 2015-5-10 07:00:48 | 显示全部楼层
谢谢你们!谢谢coursera!
Screen Shot 2015-05-09 at 7.00.09 PM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

L.r_yoga 发表于 2016-5-23 13:56:39 | 显示全部楼层
Part2的作业比part 1更自由了,这次的作业好实用,之前攒的小技巧马上亮起来O(∩_∩)O~
基本思路:在算最短路径的时候加一个virtual topvirtual bottom,分别连接top rowbottom row,相当于找virtual topvirtual 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,我都是单独拿出来判断,觉得每次调用前都判断很费时~大家有没有什么好的解决方案吖

更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

elyn 发表于 2016-6-25 18:34:56 | 显示全部楼层
L.r_yoga 发表于 2016-5-23 13:56
Part2的作业比part 1更自由了,这次的作业好实用,之前攒的小技巧马上亮起来O(∩_∩)O~ 基本思路:在算最短 ...

请问删除那个方法,是把需要删除的像素点在picture里面设置为null 吗?很困惑怎么删除
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 13:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表