Разобрать много путей в объекте дерева файлов. Есть ли эффективный алгоритм?

Question

Мой код требует создания файлового дерева из множества файловых путей, как

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

Пример визуализации объекта FileTree:

dir1
|_file1
|_dir2
  |_file2
  |_file3

Это дерево используется для визуализации торрент-файлов в графическом виде. Он также используется для динамического отображения прогресса файлов. В небольшом количестве подпапок и файлов это работает эффективно, но если пути> 10000, это занимает много памяти и времени (> 4 секунды и 50 МБ ОЗУ).

Есть ли эффективный алгоритм для создания такого графа? Наиболее важным для меня является скорость создания графика. Пример реализации алгоритма может быть написан на любом языке, для меня это не имеет значения:-) Заранее спасибо.

Мой 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;
            }
        }
    }

Answer 1

Основной алгоритм выглядит хорошо для меня, но вы создаете много ненужного 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,

Другая оптимизация может состоять в том, чтобы сохранить массив объектов String (и связанных с ними узлов FileTree) из предыдущего обработанного вами пути, и сканировать до тех пор, пока вы не найдете запись, отличную от предыдущей, перед добавлением дочерних элементов.

Answer 2

Я бы предложил заменить LinkedHashMap с HashMap потому что первый потребляет больше памяти. Основное отличие состоит в том, что HashMap не гарантирует порядок итерации по записям. Но вы можете заказать детей в графическом интерфейсе (возможно, у вас все равно есть настройки порядка). Посмотрите на этот вопрос для некоторых ссылок.

---

Еще одно предложение - вернуть фактический дочерний узел из метода. 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);
}