一亩三分地论坛

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

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

[Stanford] Algorithms: Design and Analysis, Part 1 Week # 4

[复制链接] |试试Instant~ |关注本帖
grassgigi 发表于 2014-5-27 05:45:22 | 显示全部楼层 |阅读模式

[Coursera]Algorithms: Design and Analysis #4 - 2014-05-26@Stanford

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

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

x
本帖最后由 grassgigi 于 2014-5-27 05:46 编辑

ex.png

pr.png

评分

1

查看全部评分

breezet 发表于 2014-5-27 10:34:35 | 显示全部楼层
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-5-27 14:54:36 | 显示全部楼层
看来我还是太弱了...
2014-05-27 14:51:43的屏幕截图.png
2014-05-27 14:52:28的屏幕截图.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

emulator 发表于 2014-5-28 12:38:08 | 显示全部楼层
我也来交作业咯~~~
hw4.png
hw4p.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

PincessR 发表于 2014-5-29 03:59:45 | 显示全部楼层
想请教楼上各位 用的是什么语言。 我用Java,设计的数据结构就是Node, Graph。和作业3一样,我觉得这样的效率很低,因为需要将所有vertex变成Node,然后traverse the whole matrix to find its adjacent Nodes and add them as neighbors. 想问问有没有更简便的办法可以直接对这些数据进行操作的。谢谢
回复 支持 反对

使用道具 举报

songyangUSTC 发表于 2014-5-31 18:35:31 | 显示全部楼层
好开心啊~第二遍才弄对 01.JPG 02.JPG

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-1 03:10:04 | 显示全部楼层
PincessR 发表于 2014-5-28 14:59
想请教楼上各位 用的是什么语言。 我用Java,设计的数据结构就是Node, Graph。和作业3一样,我觉得这样的 ...

我周三的作业用的是Hashmap, 用Node其实应该挺快的,快捷又方便,lecture上他说用doubly linked list
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-6 01:54:20 | 显示全部楼层

程序部分要跪了。。所以有些问题想请教你。。首先目前的问题是:
1 1
1 2
1 5
1 6
1 7
1 3
1 8
1 4

这个要怎么画? “1 1 "怎么画? 另外就是 4 没有Outdegree,那为什么没有"4 4”这一行?
我的reverseGraph坏了就是这个问题。。。可以给点意见么?

第二个问题是SCC,请看图,想问问我这个思路是否正确?因为答案好像跟正确答案不一样
https://coursera-forum-screenshots.s3.amazonaws.com/91/6d7fc0ec5311e3ae8fafcde7f82495/IMG_3531.JPG

回复 支持 反对

使用道具 举报

Sandysunshine 发表于 2014-6-7 10:28:18 | 显示全部楼层
交作业啦,呼呼~~
algorithm programming 4.jpg
algorithm problem set 4.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

breezet 发表于 2014-6-7 16:29:59 | 显示全部楼层
麻倉枼 发表于 2014-6-6 01:54
程序部分要跪了。。所以有些问题想请教你。。首先目前的问题是:
1 1
1 2

抱歉才看到。。。
1 1那个我也觉得挺奇怪的,貌似我当时是把它删掉了?
这个reverse graph的思路我感觉是对的,但是replace original node之后有一条边没改,就是original graph上的3->1。。
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-7 20:27:49 | 显示全部楼层
breezet 发表于 2014-6-7 03:29
抱歉才看到。。。
1 1那个我也觉得挺奇怪的,貌似我当时是把它删掉了?
这个reverse graph的思路我感觉 ...

我几乎每一部分都写了三种不一样的方法可是都无法挽救DFS运行速度慢的事实。。。明天就要交了怎么破,你解释下怎么能运行得快点。。我是写了vertices list 和 main edge list两部分,每个vertex 的index相对应main edge list部分的这样的structure
回复 支持 反对

使用道具 举报

breezet 发表于 2014-6-7 20:29:54 | 显示全部楼层
麻倉枼 发表于 2014-6-7 20:27
我几乎每一部分都写了三种不一样的方法可是都无法挽救DFS运行速度慢的事实。。。明天就要交了怎么破,你 ...

要快的话用C/C++应该就足够快了吧。。。算法上应该都是一样的
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-7 21:20:29 | 显示全部楼层
breezet 发表于 2014-6-7 07:29
要快的话用C/C++应该就足够快了吧。。。算法上应该都是一样的

不是啊,论坛那里有人用JAVA写的只需要30秒,我刚才试过最基本的while loop, 从 1 到875714 按顺序加进一个empty arraylist,这样竟然也需要1分钟。。。怎么破。。我已经用三种办法写出第一个DFS了,SCC却做不出来。。我现在需要解决的是究竟是我电脑问题还是我的程序问题。。你需要看的话我们可以私聊我让你看看我写的
回复 支持 反对

使用道具 举报

breezet 发表于 2014-6-7 21:34:18 | 显示全部楼层
麻倉枼 发表于 2014-6-7 21:20
不是啊,论坛那里有人用JAVA写的只需要30秒,我刚才试过最基本的while loop, 从 1 到875714 按顺序加进 ...

一般不会是电脑问题的。。其实我用python也非常慢。。
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-7 23:04:39 | 显示全部楼层
breezet 发表于 2014-6-7 08:34
一般不会是电脑问题的。。其实我用python也非常慢。。

刚才重写第四次reverseGraph,花了47分钟运行时间, 目前第五个版本运行中,里面试用了linked list,连reverse process都没开始就已经突破天际了。。

我无语死了,现在怎么破好
回复 支持 反对

使用道具 举报

breezet 发表于 2014-6-8 10:27:23 | 显示全部楼层
麻倉枼 发表于 2014-6-7 23:04
刚才重写第四次reverseGraph,花了47分钟运行时间, 目前第五个版本运行中,里面试用了linked list,连re ...

http://www.1point3acres.com/bbs/thread-30666-1-1.html

参考一下这个里面的代码吧。。。
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-8 15:22:20 | 显示全部楼层
breezet 发表于 2014-6-7 21:27
http://www.1point3acres.com/bbs/thread-30666-1-1.html

参考一下这个里面的代码吧。。。

已经找到问题了,问题就是graph的写法太占用容量,arrayList的.contain()和.get(index)都几乎是O(n),但当初我一直认为是O(1)的,可是这就是事实。。
举个例子吧

                long currentEdgeSize = 0l;
                long currentVertex = 0l;
                List<Long> currentEdgeList = null;
       
                for(i=0; i< vertices.size(); i++){
                        currentVertex = vertices.get(i).longValue();
                        currentEdgeList = mainEdgeList.get(i);
                        currentEdgeSize = currentEdgeList.size();
                       
                        for(j=0; j< mainEdgeList.get(i).size(); j++){
                               
                                subVertex = currentEdgeList.get(j).longValue();
                               
                                subVIndex = verticesR.indexOf(subVertex);
                               
                                //mainEdgeListR.get(subVIndex).add(currentVertex);
                        }
                       
                        currentEdgeList.clear();               
                }

在还没加 //mainEdgeListR.get(subVIndex).add(currentVertex); 这部分是running time 大约0.09s,一加了
mainEdgeListR.get(subVIndex) 连.add()都没的时候就当机了
回复 支持 反对

使用道具 举报

breezet 发表于 2014-6-8 15:36:10 | 显示全部楼层
麻倉枼 发表于 2014-6-8 15:22
已经找到问题了,问题就是graph的写法太占用容量,arrayList的.contain()和.get(index)都几乎是O(n),但 ...

我记得貌似list就是比较慢,vector好像快一些,很久没用过c++了
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-8 16:22:44 | 显示全部楼层
麻倉枼 发表于 2014-6-8 15:22
已经找到问题了,问题就是graph的写法太占用容量,arrayList的.contain()和.get(index)都几乎是O(n),但 ...

我也是用java写的,读txt,构建第一个Graph要12s左右(用BufferedReader读),reverse 800ms左右,我看别人构建2个Gprah快的才1.2s,应该还可以改进。
我把数据放在ArrayList<Integer>[] 里面,vertex作为数组的index,edge放在ArrayList里面,reverse的话,遍历一次Graph就可以,ArrayList的add是average O(1)的操作
回复 支持 反对

使用道具 举报

麻倉枼 发表于 2014-6-8 23:22:42 | 显示全部楼层
本帖最后由 麻倉枼 于 2014-6-8 10:26 编辑
chouclee 发表于 2014-6-8 03:22
我也是用java写的,读txt,构建第一个Graph要12s左右(用BufferedReader读),reverse 800ms左右,我看别 ...

这个IDEA昨天也想出来了可是很难改所以才没改,于是就算了把原本程序run到现在。。。
我读取数据做第一个graph才3.0多,所以才不舍得啊
另外我也是用bufferReader,估计你多出来的9秒是因为你有三个list (2 arrayList + 1 Vector)的原因,而我只有真正意义只有两个arrayList (1 arrayList<Long> + 1arrayLst<arrayList<Long>>)所以才比你快点。。昨天真心想把EDGE的address memory 存起来然后把所有数据当做stack来跑。。跟你的做法一模一样。。

这是目前状态,还有第二个DFS,跑完应该出答案了,希望是正确的。。

Reading Time = 3.399 seconds
First DFS Running Time = 17331.588 seconds

Reversing Graph Running Time = 21042.748 seconds


回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 22:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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