來源是：id, pid,name1, 0, a2, 1, b3, 1, c我們預(yù)期的結(jié)果是：id,pid,name,upnum,uplevel,downum,downlevel1, 0, a, 0, 0, 2, 1 2, 1, b, 1, 1, 0, 03, 1, c, 1, 1, 0, 0這里，name是人的名字，id標(biāo)識(shí)每個(gè)人，pid表示父id，例如，人a是人b的上級(jí)。upnum表示他總共有多少個(gè)上級(jí)，uplevel表示他有多少個(gè)上級(jí)，downnum和downlevel差不多是這樣為了得到這個(gè)結(jié)果，我想我有兩種方法1.使用數(shù)據(jù)庫，比如oralce，我用connect byand nocycle，一切正常。但是對(duì)于每個(gè)人，我必須再次運(yùn)行“connect by”sql，似乎很慢。而且我們必須在客戶端安裝一個(gè)oracle，有些客戶端不喜歡它。如果我們使用h2或一些嵌入式數(shù)據(jù)庫，我們可以使用nocycleoracle的特性嗎？但我想它也很慢。或者我們應(yīng)該制作id的索引？2.使用java hashMap來存儲(chǔ)id和pid的關(guān)系，但是當(dāng)數(shù)據(jù)變大時(shí)，可能會(huì)出現(xiàn)out of memory的異常。代碼怎么寫？什么是最好的方法？還是有更好的方法？比如一些圖形算法或圖形數(shù)據(jù)庫（數(shù)據(jù)庫）？
1 回答
回首憶惘然
TA貢獻(xiàn)1847條經(jīng)驗(yàn) 獲得超11個(gè)贊
沒有真正需要數(shù)據(jù)庫。一個(gè)簡單的迭代和一個(gè)遞歸函數(shù)可以進(jìn)行所需的分析：
import java.util.ArrayList;
import java.util.List;
public class Graph {
private final List<Node> nodes;
private final Node root;
//Graph assumes unique id > 0, and only root with pid = 0
Graph(Node root){
this.root = root;
nodes = new ArrayList<>();
nodes.add(root);
};
void add(Node node){
nodes.add(node);
}
void analyze(){
//sort by pid so iteration goes from top level down
nodes.sort( (n1,n2) -> Integer.compare(n1.getPid(), n2.getPid()) );
for(Node node : nodes){
Node parent = getNode(node.getPid());
if (parent == null ) {
continue; //skip root
}
node.setUpLevel(parent.getUpLevel()+1); //add 1 to parent value
node.setUpNum(node.getUpNum() +1); //increment by 1
parent.setDowNum(parent.getDowNum() +1); //increment by 1
updateHigherLevels(node);
}
}
//recursively update higher levels
private void updateHigherLevels(Node node) {
Node parent = getNode(node.getPid());
if(parent == null) return;
parent.setDownLevel(node.getDownLevel() + 1);
updateHigherLevels(parent);
}
void print(){
//sort by id for nice printing
nodes.sort( (n1,n2) -> Integer.compare(n1.getId(), n2.getId()) );
String format = "\n%2s %3s %4s %5s %7s %7s %8s";
System.out.printf(format,"id","pid","name","upnum","uplevel", "downnum" , "downlevel");
for(Node node : nodes){
System.out.printf(format, node.getId(), node.getPid(), node.getName(), node.getUpNum(), node.getUpLevel()
, node.getDowNum(), node.getDownLevel());
}
}
Node getNode(int id){
for(Node node : nodes){
if(node.getId() == id) return node;
}
return null;
}
public static void main(String[] args) {
//make graph
Graph graph = new Graph(new Node(1, 0, "a"));
graph.add(new Node(2, 1, "b"));
graph.add(new Node(3, 1, "c"));
graph.add(new Node(4, 2, "d"));
graph.add(new Node(5, 2, "e"));
graph.analyze();
graph.print();
}
}
class Node {
private final int id,pid;
private int upnum = 0, uplevel = 0, downum = 0, downlevel = 0;
private final String name;
Node(int id, int pid, String name) {
super();
this.id = id;
this.pid = pid;
this.name = name;
}
int getId() { return id; }
int getPid() { return pid; }
String getName() { return name; }
int getUpNum() { return upnum; }
void setUpNum(int upnum) { this.upnum = upnum; }
int getUpLevel() { return uplevel; }
void setUpLevel(int uplevel) { this.uplevel = uplevel; }
int getDowNum() { return downum; }
void setDowNum(int downum) { this.downum = downum; }
int getDownLevel() { return downlevel; }
void setDownLevel(int downlevel) { this.downlevel = downlevel; }
}
輸出：
添加回答
舉報(bào)
0/150
提交
取消