ファイルツリーオブジェクトの多くのパスを解析します。効率的なアルゴリズムはありますか？

Question

私のコードは

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

FileTreeオブジェクトの可視化の一例として、多くのファイルパスのファイルツリーの作成が必要です。

dir1 
|_file1 
|_dir2 
    |_file2 
    |_file3 

このツリーは、グラフ形式で急流コンテンツファイルの可視化のために使用されています。また、ファイルの進行状況を動的に表示するためにも使用されます。 少数のサブフォルダとファイルでは効果的ですが、パスが10,000を超えるとメモリと時間がかかります（> 4秒と50 MB RAM）。

このようなグラフを作成するための効率的なアルゴリズムはありますか？私にとって最も重要なのはグラフ作成速度です。 アルゴリズム実装の例は、どの言語で書いても構いませんが、私にとっては関係ありません:-) ありがとうございます。

私のこの目的のためのJavaコード：

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個のサブフォルダのツリーを作成するの速度を実現することが可能であったAN平均は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); 
}