t********n
发帖数: 611 | 1 在做coursera 斯坦福那门算法课的作业，本来程序要跑10个小时，经过优化，只要4秒
钟跑完，还是很有成就感的啊，而且在工作中有时候看到程序跑的超慢，应该也许可以
用算法和数据结构进行优化的吧。我觉得面试考算法，还是比让你做个前端的表格啥的
更能考出智商高低。菜鸟一家之言，请大牛们解惑。 |
j*****8
发帖数: 3635 | 2 贴贴你的代码，看看啥神奇的改动从10小时减到4秒了
【在 t********n 的大作中提到】
: 在做coursera 斯坦福那门算法课的作业，本来程序要跑10个小时，经过优化，只要4秒
: 钟跑完，还是很有成就感的啊，而且在工作中有时候看到程序跑的超慢，应该也许可以
: 用算法和数据结构进行优化的吧。我觉得面试考算法，还是比让你做个前端的表格啥的
: 更能考出智商高低。菜鸟一家之言，请大牛们解惑。
|
p**r
发帖数: 5853 | 3 刷题很有用啊，尤其是做自己project的时候，
至于给公司干活，那就算了吧，
干得再好，还不如去kiss几下ass提拔的快。
【在 t********n 的大作中提到】
: 在做coursera 斯坦福那门算法课的作业，本来程序要跑10个小时，经过优化，只要4秒
: 钟跑完，还是很有成就感的啊，而且在工作中有时候看到程序跑的超慢，应该也许可以
: 用算法和数据结构进行优化的吧。我觉得面试考算法，还是比让你做个前端的表格啥的
: 更能考出智商高低。菜鸟一家之言，请大牛们解惑。
|
r******l
发帖数: 10760 | 4 说刷题无用的人也许本来那些东西都已经知道了，人家写出来的程序本来就是4秒钟的
那个版本。你经过刷题将10小时改进到4秒钟，显然刷题对你来说很有用。这个就跟小
马过河一样，老牛说水很浅，但是小松鼠照样能淹死。
【在 t********n 的大作中提到】
: 在做coursera 斯坦福那门算法课的作业，本来程序要跑10个小时，经过优化，只要4秒
: 钟跑完，还是很有成就感的啊，而且在工作中有时候看到程序跑的超慢，应该也许可以
: 用算法和数据结构进行优化的吧。我觉得面试考算法，还是比让你做个前端的表格啥的
: 更能考出智商高低。菜鸟一家之言，请大牛们解惑。
|
x******r
发帖数: 3489 | 5 re
【在 r******l 的大作中提到】
: 说刷题无用的人也许本来那些东西都已经知道了，人家写出来的程序本来就是4秒钟的
: 那个版本。你经过刷题将10小时改进到4秒钟，显然刷题对你来说很有用。这个就跟小
: 马过河一样，老牛说水很浅，但是小松鼠照样能淹死。
|
t********n
发帖数: 611 | 6 哦，有道理，对我来说还是很有用的
【在 r******l 的大作中提到】
: 说刷题无用的人也许本来那些东西都已经知道了，人家写出来的程序本来就是4秒钟的
: 那个版本。你经过刷题将10小时改进到4秒钟，显然刷题对你来说很有用。这个就跟小
: 马过河一样，老牛说水很浅，但是小松鼠照样能淹死。
|
t********n
发帖数: 611 | 7 给公司干活，可以写在简历上，比如，说我用某某算法，令这个项目的运行速度加快了
1000倍
不过我们老板会说， 别花时间想怎么优化了，就brute force, 15分钟写出来，能跑就
行，赶时间赶时间
【在 p**r 的大作中提到】
: 刷题很有用啊，尤其是做自己project的时候，
: 至于给公司干活，那就算了吧，
: 干得再好，还不如去kiss几下ass提拔的快。
|
t********n
发帖数: 611 | 8 import java.util.HashMap;
import java.io.IOException;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;
import java.util.*;
public class Cluster4{
public static void main(String args[]) throws FileNotFoundException,
IOException{
long startTime = System.currentTimeMillis();
String line;
String path = "/Users/***/documents/java/coursera_2/week_2/
problem_2/clustering_big.txt";
File nodeFile = new File(path);
if(!nodeFile.exists()) {
System.out.println("Failed to find file");
//do something
}
FileReader fr = new FileReader(nodeFile);
BufferedReader textReader = new BufferedReader(fr);
ArrayList arr = new ArrayList();
while ((line = textReader.readLine()) != null) {
if(line.length() > 0){
arr.add(line);
}
}//end while loop
Graph c = new Graph(arr);
int result = c.run(3);
System.out.println("cluster size is " + result);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("executing time: " + elapsedTime);
}// end method main
}// end class Clustering
class Graph{
public int clusterCount = 0;
public int labelLen = 0;
public ArrayList edges = new ArrayList();
//symbol map : 1100 : [1,4,7] symbol mapped with the node id list
// node map: 1 : Node object
// nodes: [1,2,3,4...] node id
public HashMap> symbolMap = new HashMap<
Integer,ArrayList>();
public ArrayList nodes = new ArrayList();
public HashMap nodeMap = new HashMap();
public Graph( ArrayList arr){
int pos = 0;
for(String s:arr){
String[] line = s.split("\s+");
if (line.length == 2){
this.clusterCount = Integer.parseInt(line[0]);
this.labelLen = Integer.parseInt(line[1]);
} else{
String ss = String.join("", line);
int name = Integer.parseInt(ss, 2);
int id = this.nodes.size() + 1;
Node a = new Node(name, id, ss);
this.nodes.add(id);
this.nodeMap.put(id, a);
if(this.symbolMap.containsKey(name)){
this.symbolMap.get(name).add(id);
} else {
this.symbolMap.put(name, new ArrayList());
this.symbolMap.get(name).add(id);
}// end if else
}// end if else
}// end for loop to populate edges and nodeMap
// System.out.println("nodes: " + this.nodes);
// for (Map.Entry e:this.nodeMap.entrySet()){
// ((Node)e.getValue()).show();
// }// end for loop
}// end Graph constructor
public int run(int k){
ArrayList masks = generate(this.labelLen);
for (int n: this.nodes){
System.out.println("now starting from node " + n);
// System.out.println("cluster size now: " + this.clusterCount);
Node curr = this.nodeMap.get(n);
if (!curr.explored){
ArrayList tmp = new ArrayList();
curr.explored = true;
tmp.add(curr);
int p = 0;
int arrSize = 1;
while(p != arrSize){
Node head = tmp.get(p);
tmp.set(p, null);
p++;
for (int mask: masks){
if (this.symbolMap.containsKey((head.name)^mask)){
for (int id: this.symbolMap.get((head.name)^mask
)){
if(id != n && !this.nodeMap.get(id).explored
){
this.nodeMap.get(id).explored = true;
tmp.add(this.nodeMap.get(id));
arrSize++;
this.clusterCount--;
}
}
}
}// end for loop
}
}// end if
}// end for loop
return this.clusterCount;
}// end method run
public static ArrayList generate(int len){
ArrayList result = new ArrayList();
result.add(0);
int bit = 1;
for (int i = 0; i < len; i++){
result.add(bit<
}// end for loop, add all one bit masks
for (int j = len - 1; j >0; j--){
for (int k = j - 1; k >=0; k--){
int one = ( 1 << j);
int two = ( 1 << k);
result.add(one^two);
}
}// end outer for loop, add all two bit masks
return result;
};
}// end class Cluster
class Node{
public int id;
public int name;
public int leader;
public int i ;// cluster size
public String s;
public ArrayList children;
public boolean explored;
public Node(int line, int id, String s){
this.id = id;
this.name = line;
this.i = 1;
this.s = s;
this.leader = id;
this.explored = false;
this.children = new ArrayList();
this.children.add(id);
}// end Node constructor
public static int dist(Node a, Node b){
int x = a.name;
int y = b.name;
return Integer.bitCount(x^y);
}// end method dist
public void show(){
System.out.println("node " + this.id + "; name: " + this.name + ";
string: " + this.s + "; leader: " + this.leader + "; size: " + this.i + ";
children: " + this.children);
}// end method show
public static void union(int i, int j, HashMap map){
Node a = map.get(i);
Node b = map.get(j);
Node small = null;
Node big = null;
// System.out.println("before union: ");
// a.show();
// b.show();
if(a.i <= b.i){
small = a;
big = b;
} else {
small = b;
big = a;
}// end if else
if(map.get(small.leader).children.size() > 0){
for(int child: map.get(small.leader).children){
map.get(child).leader = big.leader;
map.get(big.leader).children.add(child);
}// end for loop
}// end if
// System.out.println("mid union: ");
// a.show();
// b.show();
int newSize = map.get(big.leader).children.size();
for(int child: map.get(big.leader).children){
map.get(child).i = newSize;
}// end for loop
// System.out.println("after union: ");
// a.show();
// b.show();
}// end method union
}// end class Node
// result: cluster size is 6118
// executing time: 4365
【在 j*****8 的大作中提到】
: 贴贴你的代码，看看啥神奇的改动从10小时减到4秒了
|
t********n
发帖数: 611 | 9 不好意思，代码很乱很丑哈，反正做作业，只关心结果和运行时间。
是那门algorithms: design and analysis, part 2 的 第二周课后编程作业第二题。
【在 t********n 的大作中提到】
: import java.util.HashMap;
: import java.io.IOException;
: import java.io.FileNotFoundException;
: import java.io.FileReader;
: import java.io.BufferedReader;
: import java.io.File;
: import java.util.*;
: public class Cluster4{
: public static void main(String args[]) throws FileNotFoundException,
: IOException{
|
j******o
发帖数: 4219 | 10 不是说刷题无用，而是现在的趋势是只看刷题，风气很不好。
把运行时间从10小时减到4秒的牛人，每个公司有1，2个就了不起了，多数人干的还是
搬砖的活。 |
|
|
t********n
发帖数: 611 | 11 没啥神奇改动，第一次brute force, 20万个node, 一一对比找edge, 然后union find;
20,0000 * 20,0000
然后看了课程论坛学到一找，generate bit mapping, 缩短为 300 ＊ 20，0000 ， 这
次半小时跑完
然后看到不少人都是几秒钟搞定，再次优化，不用union find，直接bfs，然后4.3秒就
跑完了
【在 j*****8 的大作中提到】
: 贴贴你的代码，看看啥神奇的改动从10小时减到4秒了
|
f*******t
发帖数: 7549 | 12 刷题有用的，练熟后实现一个简单算法并AC只需10分钟，而练之前恐怕两小时都不见得
能调对。即使工作中用不到各种hacky的算法，但写代码的手感也很重要，写代码bug比
较少，工作效率会非常高。所以现在大公司考算法题还是很有必要的，比design和
culture fit有意义的多。 |
t********n
发帖数: 611 | 13 是啊，基础知识会了，然后又能优化，那是最好，不会干活只会做题，就走极端了
【在 j******o 的大作中提到】
: 不是说刷题无用，而是现在的趋势是只看刷题，风气很不好。
: 把运行时间从10小时减到4秒的牛人，每个公司有1，2个就了不起了，多数人干的还是
: 搬砖的活。
|
p**r
发帖数: 5853 | 14 你老板知道BF已经算不错的，
我老板只要出货，客户不抱怨就行。
速度慢？那最好，堆硬件，或者新一轮优化开发计划，都是钱啊。
【在 t********n 的大作中提到】
: 给公司干活，可以写在简历上，比如，说我用某某算法，令这个项目的运行速度加快了
: 1000倍
: 不过我们老板会说， 别花时间想怎么优化了，就brute force, 15分钟写出来，能跑就
: 行，赶时间赶时间
|
t********n
发帖数: 611 | 15 我老板一样一样一样地啊。。。
我觉得大家都应该像中国人一样，回家多少刷两题。。。
【在 p**r 的大作中提到】
: 你老板知道BF已经算不错的，
: 我老板只要出货，客户不抱怨就行。
: 速度慢？那最好，堆硬件，或者新一轮优化开发计划，都是钱啊。
|
t********n
发帖数: 611 | 16 更正一下，generate bit mapping, 缩短为 301 ＊ 20，0000，
这301 的来源： (24 choose 0) + (24 choose 1) + (24 choose 2) = 1 + 24 + (24
! / (2! * 24!)) = 301
find;
【在 t********n 的大作中提到】
: 没啥神奇改动，第一次brute force, 20万个node, 一一对比找edge, 然后union find;
: 20,0000 * 20,0000
: 然后看了课程论坛学到一找，generate bit mapping, 缩短为 300 ＊ 20，0000 ， 这
: 次半小时跑完
: 然后看到不少人都是几秒钟搞定，再次优化，不用union find，直接bfs，然后4.3秒就
: 跑完了
|
h****e
发帖数: 2125 | 17 我看你是螺丝拧多了拧出成就感来了。
【在 f*******t 的大作中提到】
: 刷题有用的，练熟后实现一个简单算法并AC只需10分钟，而练之前恐怕两小时都不见得
: 能调对。即使工作中用不到各种hacky的算法，但写代码的手感也很重要，写代码bug比
: 较少，工作效率会非常高。所以现在大公司考算法题还是很有必要的，比design和
: culture fit有意义的多。
|
f*******t
发帖数: 7549 | 18 不积跬步，无以至千里。刷题是练基本功。
【在 h****e 的大作中提到】
: 我看你是螺丝拧多了拧出成就感来了。
|
h****e
发帖数: 2125 | 19 刚毕业的可以，工作10年了还积跬步？
【在 f*******t 的大作中提到】
: 不积跬步，无以至千里。刷题是练基本功。
|
w*******9
发帖数: 11 | 20 学算法和刷算法题是两回事，你说的是学习算法，知其然切知其所以然，未来可以在工
作中应用。
而刷算法题则。。。 |
p**********u
发帖数: 67 | 21
printf("Finished!");
【在 j*****8 的大作中提到】
: 贴贴你的代码，看看啥神奇的改动从10小时减到4秒了
|
