Почему это решение уровня MinDepth такое медленное по сравнению с рекурсивным решением? - PullRequest
Новая
       55

Почему это решение уровня MinDepth такое медленное по сравнению с рекурсивным решением?

0 голосов
/ 18 декабря 2018

Проблема в том, чтобы найти минимальную глубину бинарного дерева, чтобы при работе на следующем дереве: 

    *           :Level 1
   / \
  *   *         :Level 2
     / \
    *  NULL     :Level 3

вернуло бы mindepth равным 2.

Мне удалось получитьрекурсивное решение, которое превосходит 100% других решений в соответствии с leetcode, что для меня не имело смысла, так как это может быть настолько быстрым, если приходится посещать каждого потомка каждого узла (реализация DFS).

Вместо этого я решил сделать это способом BFS, а не DFS, и проверить, есть ли на каждом уровне узел, у которого нет дочерних элементов, и это будет минимальная глубина.

Вот мое рекурсивное решение: 

public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    else if (root.left == null) 
        return minDepth(root.right) + 1;
    else if (root.right == null) 
        return minDepth(root.left) + 1;
    else 
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

Вот мой уровень решения: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        ArrayList<TreeNode> q = new ArrayList<TreeNode>(); // We will store each new node here
        q.add(root); // add the root to our queue
        return root != null ? minDepthHelper(q, 0) : 0; // If the root node is null, dont bother and return 0

    }

    private int minDepthHelper(ArrayList<TreeNode> q, int depth){
        if(q.size() == 0) // Empty queue means nothing to do, so return
            return depth;

        int size = q.size(); // How many we will need to pop (the parents)
        for(int i = 0; i < size; i++){
            TreeNode curr = q.get(0); // FIFO!
            if(curr.left == null && curr.right == null){
                return depth +1; // If you have no children, then you are a leaf so return your depth. 
                                            // nodes 0 through size are on the same level, so any of them , if they have 
                                            // no children, will return the same value which will be min depth.
            }else{
                // Add only non-null children!
                if(curr.left != null)
                    q.add(curr.left);
                if(curr.right != null)
                    q.add(curr.right);
            }
            q.remove(0);
        }
        // Will only reach here if no nodes in level depth have no right and no left
        return minDepthHelper(q, depth+1);
    }
}

Может кто-нибудь объяснить, почему второе решение медленнее, хотя оно должно делать меньше сравнений?

1 Ответ

0 голосов
/ 18 декабря 2018

Я бы не стал придавать большое значение процентам LeetCode.Когда я отправляю ваше рекурсивное решение, оно показывает, что оно превышает 34%.LeetCode также показывает точно такой же пример кода для сегментов 100% и 34%.Можно только догадываться, каковы их тестовые случаи.Все реализации, которые я представил, выполняются за 1 мс, так что, скорее всего, все 41 из их тестовых случаев - очень маленькие деревья, так что различия в производительности совершенно незначительны.Вы также не знаете, какие древовидные структуры преобладают в примерах - все они могут быть более или менее сложными по времени, и в этом случае BFS имеет небольшое преимущество или вообще не имеет его над DFS.

При этомпомните, давайте оценим ваш код на больших тестовых примерах, чтобы увидеть, сможем ли мы получить некоторое понимание, которого нельзя достичь в среде тестирования черного ящика, которую предлагает LeetCode.

Прежде чем мы это сделаем, давайте рассмотрим вашу BFSрешение, которое использует рекурсию и манипулирует ArrayList, как если бы это была очередь.Это правда, что операции сдвига ArrayList амортизируются O (1), но использование ArrayDeque является гораздо более быстрой и более семантически подходящей структурой данных для операций с очередями в Java.

Кроме того, используя рекурсию в своей реализации BFS, вывы отрицаете одно из основных преимуществ BFS, заключающееся в том, что оно итеративное.Отсутствие необходимости манипулировать стеком вызовов должно значительно сократить накладные расходы.

Сложив все это вместе, я написал бы функцию BFS следующим образом: 

public int minDepth(TreeNode root) {
    ArrayDeque<Pair<TreeNode, Integer>> q = new ArrayDeque<>();
    q.offer(new Pair(root, 1));

    while (!q.isEmpty()) {
        Pair<TreeNode, Integer> curr = q.poll();

        if (curr.first != null) {
            if (curr.first.left == null && curr.first.right == null) {
                return curr.second;
            }

            q.offer(new Pair(curr.first.left, curr.second + 1));
            q.offer(new Pair(curr.first.right, curr.second + 1));
        }
    }

    return 0;
}

Теперь быстрый тест.Здесь BFS2 - ваша реализация BFS, а BFS - моя: 

long BFSTotal = 0;
long BFS2Total = 0;
long DFSTotal = 0;

for (int i = 0; i < 10000; i++) {
    TreeNode root = randomTree(10000);

    long start = System.currentTimeMillis();
    minDepthDFS(root);
    DFSTotal += System.currentTimeMillis() - start;

    start = System.currentTimeMillis();
    minDepthBFS(root);
    BFSTotal += System.currentTimeMillis() - start;

    start = System.currentTimeMillis();
    minDepthBFS2(root);
    BFS2Total += System.currentTimeMillis() - start;
}

System.out.println("BFS: " + BFSTotal);
System.out.println("BFS2: " + BFS2Total);
System.out.println("DFS: " + DFSTotal);

Этот код создает 10000 различных деревьев, каждое с 10000 узлами, созданными с использованием алгоритма броска монеты, и запускает алгоритмы для каждого дерева.,Вот результаты нескольких прогонов: 

BFS: 1906
BFS2: 5484
DFS: 3351

BFS: 1709
BFS2: 6101
DFS: 3773

BFS: 1527
BFS2: 5567
DFS: 3856

Продолжайте и запустите код самостоятельно и немного поэкспериментируйте.Я не думаю, что эти результаты являются абсолютно убедительными, но они укрепляют мои основные предпосылки: BFS превосходит DFS из-за меньших накладных расходов и потенциала для раннего освобождения (в худшем случае сложности времени одинаковы), а нерекурсивная реализация BFS используетэффективная структура данных превосходит рекурсивную реализацию BFS, которая использует неэффективную структуру данных.

Это также демонстрирует, что ваша реализация BFS примерно в два раза медленнее, чем ваша реализация DFS, что может объяснить ваши результаты LeetCodeно, опять же, я бы не решился сделать какие-либо выводы, учитывая, насколько крошечными кажутся их тестовые случаи.

...