파일 트리 개체에서 여러 경로를 구문 분석합니다. 효율적인 알고리즘이 있습니까?

Question

내 코드

dir1/file1 
dir1/dir2/file2 
dir1/dir2/file3 

FileTree 객체 시각화 예로서 많은 파일 경로의 파일 트리를 작성해야합니다 :

dir1 
|_file1 
|_dir2 
    |_file2 
    |_file3 

이 나무는 그래픽 형태로 토런트 콘텐츠 파일 시각화에 사용됩니다. 또한 동적으로 파일 진행 상황을 보여주기 위해 사용됩니다. 작은 수의 하위 폴더 및 파일에서는 효과적으로 작동하지만 경로가 10,000보다 큰 경우 많은 메모리와 시간 (> 4 초 및 50MB RAM)이 필요합니다.

그래프를 만드는 효율적인 알고리즘이 있습니까? 가장 중요한 것은 그래프 작성 속도입니다. 알고리즘 구현의 예는 어떤 언어로도 작성할 수 있지만 나에게 중요하지 않습니다 .-) 미리 감사드립니다. 이 목적을 위해

내 자바 코드 :

FileTree root = new FileTree(FileTree.ROOT, File.Type.DIR); 
FileTree parentTree; 

for (String pathToFile : paths) { 
    parentTree = root; 
    String[] nodes = FileIOUtils.parsePath(pathToFile); /*String.split(File.separator)*/ 

    for (int i = 0; i < nodes.length; i++) { 
      /* The last leaf item is a file */ 
     if (i == (nodes.length - 1)) { 
      parentTree.addChild(new FileTree(nodes[i], 
       File.Type.FILE, parentTree)); 
     } else { 
      parentTree.addChild(new FileTree(nodes[i], FileNode.Type.DIR, parentTree)); 
     } 

     FileTree nextParent = parentTree.getChild(nodes[i]); 
      /* Skipping leaf nodes */ 
     if (nextParent != null && !nextParent.isFile()) { 
      parentTree = nextParent; 
     } 
    } 
} 

FileTree 클래스 :

는

public class FileTree { 
    public static final String ROOT = "/"; 
    /* The name for pointer to the parent node */ 
    public static final String PARENT_DIR = ".."; 

    protected String name; 
    protected boolean isLeaf; 
    protected FileTree parent; 
    protected Map<String, FileTree> children = new LinkedHashMap<>(); 

    public FileTree(String name, int type, FileTree parent) { 
     this(name, type, parent); 
    } 

    public FileTree(String name, int type) 
    { 
     this(name, type, null); 
    } 

    public FileTree(String name, int type, FileTree parent) 
    { 
     this.name = name; 
     isLeaf = (type == File.Type.FILE); 
     this.parent = parent; 
    } 

    public synchronized void addChild(FileTree node) 
    { 
     if (!children.containsKey(node.getName())) { 
      children.put(node.getName(), node); 
     } 
    } 

    public boolean contains(String name) 
    { 
     return children.containsKey(name); 
    } 

    public F getChild(String name) 
    { 
     return children.get(name); 
    } 

    public Collection<FileTree> getChildren() 
    { 
     return children.values(); 
    } 

    public Set<String> getChildrenName() 
    { 
     return children.keySet(); 
    } 
} 

편집 :

1000 트리를 만드는 속도를 달성 할 수 있었다은을 하위 폴더 평균 0.5-1 초 (초기 30 초).

FileTree root = new BencodeFileTree(FileTree.ROOT, 0L, File.Type.DIR); 
    FileTree parentTree = root; 
    /* It allows reduce the number of iterations on the paths with equal beginnings */ 
    String prevPath = ""; 
    /* Sort reduces the returns number to root */ 
    Collections.sort(files); 

    for (String file : files) { 
     String path; 
     /* 
     * Compare previous path with new path. 
     * Example: 
     * prev = dir1/dir2/ 
     * cur = dir1/dir2/file1 
     *  |________| 
     *   equal 
     * 
     * prev = dir1/dir2/ 
     * cur = dir3/file2 
     *  |________| 
     *   not equal 
     */ 
     if (!prevPath.isEmpty() && 
       file.regionMatches(true, 0, prevPath, 0, prevPath.length())) { 
      /* 
      * Beginning paths are equal, remove previous path from the new path. 
      * Example: 
      * prev = dir1/dir2/ 
      * cur = dir1/dir2/file1 
      * new = file1 
      */ 
      path = file.substring(prevPath.length()); 
     } else { 
      /* Beginning paths are not equal, return to root */ 
      path = file; 
      parentTree = root; 
     } 

     String[] nodes = FileIOUtils.parsePath(path); 
     /* 
     * Remove last node (file) from previous path. 
     * Example: 
     * cur = dir1/dir2/file1 
     * new = dir1/dir2/ 
     */ 
     prevPath = file.substring(0, file.length() - nodes[nodes.length - 1].length()); 

     /* Iterates path nodes */ 
     for (int i = 0; i < nodes.length; i++) { 
      if (!parentTree.contains(nodes[i])) { 
       /* The last leaf item is a file */ 
       parentTree.addChild(makeObject(nodes[i], parentTree, 
           i == (nodes.length - 1))); 
      } 

      FileTree nextParent = parentTree.getChild(nodes[i]); 
      /* Skipping leaf nodes */ 
      if (!nextParent.isFile()) { 
       parentTree = nextParent; 
      } 
     } 
    } 

Answer 1

기본 알고리즘은 나에게 좋아 보인다,하지만 당신은 바로 이미 존재하는 (공통)의 경우 멀리 던져 질 것이다 addChild를 호출 할 때 불필요한 FileTree 개체를 많이 만들 수 있습니다. 당신은 생성자에 매개 변수를 전달하려고하고 삽입 할 필요가있는 경우에만 개체를 ​​생성 할 수 :

public synchronized void addChild(String name, int type, FileTree parent) 
{ 
    if (!children.containsKey(name)) { 
     children.put(name, new FileTree(name, type, parent)); 
    } 
} 

과 : 그것은 parentTree를 전달할 필요하지 않을 수도 있습니다

if (i == (nodes.length - 1)) { 
    parentTree.addChild(nodes[i], File.Type.FILE, parentTree); 
} else { 
    parentTree.addChild(nodes[i], FileNode.Type.DIR, parentTree); 
} 

: 당신이 할 수있는 this으로 만드십시오.

또 다른 최적화는 String 객체 (및 연관된 FileTree 노드)의 배열을 처리 한 이전 경로에서 유지하고 하위 항목을 추가하기 전에 이전 항목과 다른 항목을 찾을 때까지 계속 스캔 할 수 있습니다.

Answer 2

LinkedHashMap을 HashMap으로 바꾸려면 먼저 메모리를 더 많이 사용하기 때문에 좋습니다. 가장 큰 차이점은 HashMap이 항목에 대한 반복 순서를 보장하지 않는다는 것입니다. 그러나 GUI로 아이들을 주문할 수 있습니다 (어쨌든 주문 설정이있을 수 있습니다). 참조 용으로 this question을 살펴보십시오.

---

또 다른 제안은 다시지도를

FileTree nextParent = parentTree.addChild(... 

---

와 get를 호출 할 필요가없는 루프 내에서 방법 그리고 addChild

public synchronized FileTree addChild(FileTree node) { 
    return children.putIfAbsent(node.getName(), node); 
} 

에서 실제 자식 노드를 반환하는 것입니다 불필요 해 보이는 조건이있다

if (nextParent != null && !nextParent.isFile()) { 
    parentTree = nextParent; 
} 

현재 자식이 파일이면 루프에 반복이없는 것처럼 보입니다. 그래서 안전하게 당신이 그것을 사용하는 것입니다 방법을 설명시겠습니까

for(...) { 
    int type = if (i == (nodes.length - 1)) ? File.Type.FILE : FileNode.Type.DIR; 
    parentTree = parentTree.addChild(new FileTree(nodes[i], type, parentTree); 
}