느린 건물 목록 경로

Question

트리에서 노드 경로의 루트를 나타내는 해시 목록을 작성합니다. 내 기능은 작동하지만 큰 나무 구조보다 훨씬 느립니다. 더 좋은 방법이 있습니까? 한 가지 기능으로 목록을 작성하려고 시도했지만 필자가 원하지 않는 고유 한 해시를 얻습니다.

public ArrayList<Integer> makePathList(AbstractTree<String> tree){ 
    StringBuilder buffer = new StringBuilder(); 
    ArrayList<Integer> pl = new ArrayList<Integer>(); 
    ArrayList<StringBuilder> paths = getPaths(tree, buffer); 
    for(StringBuilder sb : paths){ 
     pl.add(sb.toString().hashCode()); 
    } 

    return pl; 
} 

public ArrayList<StringBuilder> getPaths(AbstractTree<String> tree, StringBuilder parent){ 
     ArrayList<StringBuilder> list = new ArrayList<StringBuilder>(); 
     parent.append("/"); 
     parent.append(tree.getNodeName()); 
     list.add(new StringBuilder(parent)); 

     if (!tree.isLeaf()){  
      int i = 0; 
      Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
      while (i < tree.getChildren().size()){ 
       list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
       i++; 
      } 
     } 
     return list; 
} 

UPDATE : 나는 그것을 짓을하는 방법을 트리 탐색하는 동안 해시가 잘못된 답을 제공하지만, 아마도 즉 만드는

마르신의 제안?

public ArrayList<Integer> getPaths(AbstractTree<String> tree, StringBuilder parent){ 
    ArrayList<Integer> list = new ArrayList<Integer>(); 

    parent.append("/"); 
    parent.append(tree.getNodeName()); 
    list.add(new StringBuilder(parent).toString().hashCode()); 

    if (!tree.isLeaf()){  
     int i = 0; 
     Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size()){ 

      list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
      i++; 
     } 
    } 
    return list; 
} 

Answer 1

주요 문제는 생성하는 중복 데이터의 양이라고 생각합니다. 트리의 모든 단일 리프에 대해 리프까지 이어지는 전체 경로의 복사본을 만들어 해당 경로의 해시를 계산합니다. 즉 하나의 최상위 노드 아래에 50,000 개의 잎이있는 경우 해당 노드의 경로 이름이 50,000 번 복사되고 해시 값이 50,000 번 계산됩니다.

공유 접두어가 리프 사이의 참조로 다시 사용되도록 구성 할 수 있고 이러한 접두어에 대한 해시 계산을 캐시에 저장하고 재사용하면 수행 할 실제 작업량을 크게 줄일 수 있습니다.

Answer 2

여기서 jvisualvm은 성능 병목 현상이 있습니까?

Answer 3

먼저 모든 경로 목록을 만든 다음 해시를 계산하면됩니다. 모든 경로의 목록의 크기는 O (n^3)입니다 (O (n^2) 개의 경로가 있으며 각 O (n) 길이) 이유는 무엇입니까? 왜 나무를 횡단하면서 해시를 계산하지 않는 것이 좋을까요? 이렇게하면 전체 하나를 n 시간 복잡성에서 제거 할 수 있습니다.

적절한 솔루션을위한 코드 (결과는 정수의리스트에 전달 끝)

public void getPaths(AbstractTree<String> tree, StringBuilder parentPath, 
    List<Integer> list) 
    StringBuilder newPath = parentPath.clone(); 
    newPath.append("/"); 
    newPath.append(tree.getNodeName()); 
    list.add(newPath.toString().hashCode()); 
    if (!tree.isLeaf()){  
    Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
    for (AbstractTree<String> child : tree.getChildren()){ 
     getPaths(child, newPath, list) 
    } 
    } 
} 

이 여전히 O (n은 2 ^). 그 이유는 O (n^2) 개의 문자열 (각각의 노드는 길이에 비례하는 경로 길이를 가짐)을 해시하기 때문입니다. 주어진 노드에 대해서만 해시를 사용한다면 O (N)까지 가져올 수 있습니다. a 해시 부모의 경로이며 어떤 식 으로든 그것을 수정합니다.

Furhter 최적화 포함 이 - 병렬 트리 탐색 - 똑똑 해싱하여 (아이 즉 해시 아이의 기능과 상위 경로 해시 아닌 전체 상위 경로).

Answer 4

나는 복잡성이 여전히 동일하다고 생각합니다. 해시 (O (n^2))의 인라인 생성을 사용하거나 재귀 (O (n^2 + n) = O (n^2)) 후에 수행하는 경우 상관 없습니다. 빠른 방법을 찾을 수있는 유일한 기회는 다른 장소에서 작업을하는 것입니다. 예 : 노드를 삽입하는 동안 경로를 해싱하고 다른 지점의 모든 해시 만 수집 할 수 있습니다.