0

私のコードでは、多くのファイル パスのファイル ツリーを次のように作成する必要があります。

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 個のサブフォルダーのツリーを作成する速度を平均 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;
            }
        }
    }
4

2 に答える 2

0

基本的なアルゴリズムは私には良さそうに見えますが、FileTree呼び出すと不要なオブジェクトが多数作成addChildされ、それらが既に存在する (一般的な) ケースではすぐに破棄されます。パラメーターをコンストラクターに渡してみて、挿入する必要がある場合にのみオブジェクトを構築できます。

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

と： 

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

を渡す必要はないかもしれませんparentTree: で構築するだけthisです。

もう 1 つの最適化は、処理した前のパスから String オブジェクト (および関連する FileTree ノード) の配列を維持し、子を追加する前に前のパスとは異なるエントリが見つかるまでスキャンすることです。

于 2016-08-03T10:11:18.913 に答える
0

最初のものはより多くのメモリを消費するためLinkedHashMap、に置き換えることをお勧めします。HashMap主な違いは、HashMapエントリに対する反復の順序が保証されないことです。ただし、GUI で子を注文することもできます (おそらく、なんらかの順序設定があるはずです)。いくつかの参照については、この質問をご覧ください。

別の提案は、メソッドから実際の子ノードを返すことですaddChild

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

getその後、ループ内でマップを再度呼び出す必要はありません

FileTree nextParent = parentTree.addChild(...

そして不要に見える条件もある

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

現在の子がファイルの場合、ループに反復がないように見えます。したがって、安全に置き換えることができます

parentTree = parentTree.addChild(...

提案の後、ループ本体は次のようになります

for(...) {
    int type = if (i == (nodes.length - 1)) ? File.Type.FILE : FileNode.Type.DIR;
    parentTree = parentTree.addChild(new FileTree(nodes[i], type, parentTree);
}
于 2016-08-03T11:15:32.897 に答える