0
이 문제를 해결하는 방법 : http://www.cs.duke.edu/csed/newapt/drawtree.html 아래 코드를 작성했지만 너무 느리게 실행되는 것 같습니다. FOR 루프를 사용하여 모든 자식 노드를 검사하는 더 빠른 방법이 있습니까? 대기열이 도움이 될까요?재귀 함수의 런타임을 향상시키는 방법
public class DrawTree {
HashMap<String, ArrayList<String>> map =
new HashMap<String, ArrayList<String>>();
ArrayList<String> drawing = new ArrayList<String>();
String root;
public String[] draw(int[] parents, String[] names) {
for(int x=0; x<parents.length; x++)
{
int parentindex = parents[x];
//root name
if(parentindex==-1)
{
root=names[x];
if(!map.containsKey(names[x]))
{
map.put(names[x], new ArrayList<String>());
}
continue;
}
//add parent, child to map
if (!map.containsKey(names[parentindex]))
map.put(names[parentindex],
new ArrayList<String>());
map.get(names[parentindex]).add(names[x]);
}
sketch("",root,false);
return drawing.toArray(new String[drawing.size()]);
}
//***IMPROVE RUN TIME - different algorithm??***
//method takes root and prefix?
public void sketch(String parent, String child, boolean addPipe){
StringBuilder toAdd = new StringBuilder();
//don't need to add connector pipe
if(!addPipe)
{
//number of spaces to add to prefix
int spaces = parent.indexOf('-')+1;
//add spaces to prefix
while(spaces>0)
{
toAdd.append(" ");
spaces--;
}
toAdd.append("+-"+child);
}
//index of pipe in parent, -1 if parent doesn't have pipe
int parentPipe = parent.indexOf('|');
//need to add connector pipe & parent has pipe
// (is a child of a subtree)
if(parentPipe>0)
{
//number of spaces to add to prefix
int spaces = parent.indexOf('-')+1;
//add spaces to prefix
while(spaces>0)
{
if(spaces==parentPipe) toAdd.append('|');
else toAdd.append(" ");
spaces--;
}
toAdd.append("+-"+child);
}
//need to add pipe and parent doesn't have pipe
if(addPipe && parentPipe<0)
{
int spaces = parent.indexOf('-')+1;
while(spaces>0)
{
if(spaces==2) toAdd.append('|');
else toAdd.append(" ");
}
toAdd.append("+-"+child);
}
//add child to list of tree drawing
String node = toAdd.toString();
drawing.add(node);
//System.out.println(node);
//loop through list of children, passing each recursively
//...count level?
if(map.containsKey(child))
{
//System.out.println("map works");
for(int x = 0; x<map.get(child).size(); x++)
{
boolean pipe = false;
if(x<(map.get(child).size()-1)) pipe=true;
//System.out.println(map.get(child).get(x));
sketch(node, map.get(child).get(x), pipe);
}
}
}
이 질문은 [codereview.se] (http://codereview.stackexchange.com/)에 더 적합합니다. – cheeken
"느리게"정의하는 기준은 무엇입니까? 특정 타이밍이 있습니까? – kosa
하나의 개선점은 map.containsKey (key)입니다. 그것은 map.get (key)와 거의 같은 시간을가집니다. containsKey를 호출하고 하나씩 가져 오는 것은 의미가 없습니다. 더 나은 사용'List list = map.get (key); if (list == null) {list = new ArrayList (); map.put (key, list);} list.add (something);' –