Java中两种常用LCA算法的比较

Question

现在，我有两个解决问题的算法:给定一个通用(多路)树和任何节点名称数组，找到最深的共同祖先节点。

LCAComputer.java:

package com.github.coderodde.generallca;

/**
 * This interface specifies the API for methods computing multiple node LCAs.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 19, 2022)
 */
public interface LCAComputer {
    
    GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                String... nodeNames);
}

LCAComputerV1.java:

package com.github.coderodde.generallca.impl;

import com.github.coderodde.generallca.GeneralTree;
import com.github.coderodde.generallca.GeneralTreeNode;
import com.github.coderodde.generallca.LCAComputer;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * This class provides a method for computing general lowest common ancestors.
 * For each query node {@code n}, the algorithm computes the path from 
 * {@code n} to the root node. Then, it marches along all the paths upwards 
 * towards the root node incrementing the counts of each visited nodes. The 
 * first node whose counter reaches the number of query nodes, is the LCA.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 18, 2022)
 */
public final class LCAComputerV1 implements LCAComputer {
    
    public GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                       String... nodeNames) {
        List<List<GeneralTreeNode>> paths = new ArrayList<>(nodeNames.length);
        
        for (int i = 0; i < nodeNames.length; ++i) {
            GeneralTreeNode node = tree.getNode(nodeNames[i]);
            Objects.requireNonNull(
                    node,
                    "There is no node with name '" + nodeNames[i] + "'.");
            
            paths.add(getPathToRoot(node));
        }
        
        Map<GeneralTreeNode, Integer> visitedMap = new HashMap<>();
        
        for (List<GeneralTreeNode> path : paths) {
            for (GeneralTreeNode node : path) {
                visitedMap.put(node, visitedMap.getOrDefault(node, 0) + 1);
                
                if (visitedMap.get(node) == nodeNames.length) {
                    return node;
                }
            }
        }
        
        throw new IllegalStateException("Should not get here.");
    }
    
    private List<GeneralTreeNode> getPathToRoot(GeneralTreeNode node) {
        List<GeneralTreeNode> path = new ArrayList<>();
        
        while (node != null) {
            path.add(node);
            node = node.getParent();
        }
        
        return path;
    }
}

LCAComputerV2.java

package com.github.coderodde.generallca.impl;

import com.github.coderodde.generallca.GeneralTree;
import com.github.coderodde.generallca.GeneralTreeNode;
import com.github.coderodde.generallca.LCAComputer;
import java.util.Arrays;

/**
 * 
 * This class provides a method for computing general lowest common ancestors.
 * The algorithm moves all the query nodes to the level of the shallowest node,
 * and keeps moving all the nodes until they all visit a single node, which is
 * a LCA.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 19, 2022)
 */
public final class LCAComputerV2 implements LCAComputer {

    @Override
    public GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                       String... nodeNames) {
        GeneralTreeNode[] nodes = new GeneralTreeNode[nodeNames.length];
        
        for (int i = 0; i < nodes.length; ++i) {
            nodes[i] = tree.getNode(nodeNames[i]);
        }
        
        Arrays.sort(
                nodes,
                (n1, n2) -> { 
                    return Integer.compare(n1.getDepth(), n2.getDepth());
                });
        
        int minimumDepth = nodes[0].getDepth();
        
        for (int i = 1; i < nodes.length; ++i) {
            while (nodes[i].getDepth() > minimumDepth) {
                nodes[i] = nodes[i].getParent();
            }
        }
        
        // Here, nodes points to the visited nodes at the minimum depth:
        while (!visitingOnlyOneNode(nodes)) {
            for (int i = 0; i < nodes.length; ++i) {
                nodes[i] = nodes[i].getParent();
            }
        }
        
        return nodes[0];
    }
    
    private boolean visitingOnlyOneNode(GeneralTreeNode[] nodes) {
        for (int i = 0; i < nodes.length - 1; ++i) {
            if (nodes[i] != nodes[i + 1]) {
                return false;
            }
        }
        
        return true;
    }
}

GeneralTreeNode.java:

package com.github.coderodde.generallca;

import java.util.Objects;

/**
 * This class implements a node for general trees. It allows any number of 
 * child nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 18, 2022)
 */
public final class GeneralTreeNode {
    
    private final String name;
    private final int depth;
    private GeneralTreeNode parent;
    
    GeneralTreeNode(String name, int depth, GeneralTreeNode parent) {
        this.name = name;
        this.depth = depth;
        this.parent = parent;
    }
    
    public int getDepth() {
        return depth;
    }
    
    public String getName() {
        return name;
    }
    
    public GeneralTreeNode getParent() {
        return parent;
    }
    
    public void setParent(GeneralTreeNode parent) {
        this.parent = parent;
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof GeneralTreeNode)) {
            return false;
        }
        
        GeneralTreeNode other = (GeneralTreeNode) o;
        return name.equals(other.name);
    }

    @Override
    public int hashCode() {
        // Generated by NetBeans IDE 12.6
        int hash = 7;
        hash = 19 * hash + Objects.hashCode(this.name);
        return hash;
    }
}

GeneralTree.java:

package com.github.coderodde.generallca;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 *
 * @author rodde
 */
public final class GeneralTree {
    
    private final Map<String, GeneralTreeNode> treeNodeMap = new HashMap<>();
    private GeneralTreeNode root;
    
    public GeneralTreeNode getNode(String name) {
        return treeNodeMap.get(name);
    }
    
    public void addRootNode(String name) {
        Objects.requireNonNull(name, "The node name is null.");
        
        if (treeNodeMap.containsKey(name)) {
            throw new IllegalArgumentException(
                    "The node named '" + name + "' is already in this tree.");
        }
        
        root = new GeneralTreeNode(name, 0, null);
        treeNodeMap.put(name, root);
    }
    
    public void addNode(String childNodeName, String parentNodeName) {
        GeneralTreeNode parentNode = treeNodeMap.get(parentNodeName);
        Objects.requireNonNull(parentNode, "The parent node is null.");
        
        GeneralTreeNode childNode = 
                new GeneralTreeNode(
                        childNodeName, 
                        parentNode.getDepth() + 1, 
                        parentNode);
        
        treeNodeMap.put(childNodeName, childNode);
    }
}

BenchmarkApp.java:

package com.github.coderodde.generallca;

import com.github.coderodde.generallca.impl.LCAComputerV1;
import com.github.coderodde.generallca.impl.LCAComputerV2;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public final class BenchmarkApp {
    
    private static final int NUMBER_OF_TREE_NODES = 1000_000;
    private static final int NUMBER_OF_QUERIES = 100_000;
    private static final int MAXIMUM_QUERY_LENGTH = 50;
    
    private final long seed;
    private final GeneralTree tree = new GeneralTree();
    private final LCAComputer lcaComputerV1 = new LCAComputerV1();
    private final LCAComputer lcaComputerV2 = new LCAComputerV2();
    
    public BenchmarkApp(long seed) {
        this.seed = seed;
        buildTree();
    }
    
    public void warmup() {
        doRun(false);
    }
    
    public void benchmark() {
        doRun(true);
    }
    
    private void doRun(boolean print) {
        Random random = new Random(seed);
        List<GeneralTreeNode> result1 = new ArrayList<>(NUMBER_OF_QUERIES);
        List<GeneralTreeNode> result2 = new ArrayList<>(NUMBER_OF_QUERIES);
        String[][] queries = getQueries();
        
        long startTime = System.currentTimeMillis();
        
        for (int i = 0; i < NUMBER_OF_QUERIES; ++i) {
            result1.add(
                    lcaComputerV1.computeLowestCommonAncestor(
                            tree,
                            queries[i]));
        }
        
        long endTime = System.currentTimeMillis();
        
        if (print) {
            long duration = endTime - startTime;
            
            System.out.println(
                    lcaComputerV1.getClass().getSimpleName() 
                            + " in " 
                            + duration 
                            + " milliseconds.");
        }
        
        startTime = System.currentTimeMillis();
        
        for (int i = 0; i < NUMBER_OF_QUERIES; ++i) {
            result2.add(
                    lcaComputerV2.computeLowestCommonAncestor(
                            tree,
                            queries[i]));
        }
        
        endTime = System.currentTimeMillis();
        
        if (print) {
            long duration = endTime - startTime;
            
            System.out.println(
                    lcaComputerV2.getClass().getSimpleName() 
                            + " in " 
                            + duration 
                            + " milliseconds.");
            
            System.out.println("Algorithms agree: " + result1.equals(result2));
        }
    }
    
    private void buildTree() {
        Random random = new Random(this.seed);
        List<GeneralTreeNode> createdNodeList = new ArrayList<>();
        tree.addRootNode("Root");
        GeneralTreeNode root = tree.getNode("Root");
        createdNodeList.add(root);
        
        for (int i = 1; i < NUMBER_OF_TREE_NODES; ++i) {
            String childName = Integer.toString(i);
            int index = random.nextInt(createdNodeList.size());
            GeneralTreeNode parentNode = createdNodeList.get(index);
            tree.addNode(childName, parentNode.getName());
            createdNodeList.add(tree.getNode(childName));
        }
    }
    
    private String[][] getQueries() {
        String[][] queries = new String[NUMBER_OF_QUERIES][];
        
        for (int i = 0; i < NUMBER_OF_QUERIES; ++i) {
            queries[i] = generateQuery();
        }
        
        return queries;
    }
    
    private String[] generateQuery() {
        Random random = new Random(this.seed);
        int queryLength = random.nextInt(MAXIMUM_QUERY_LENGTH) + 1;
        String[] query = new String[queryLength];
        
        for (int i = 0; i < query.length; ++i) {
            query[i] = Integer.toString(random.nextInt(NUMBER_OF_TREE_NODES));
        }
        
        return query;
    }
}

Demo.java:

package com.github.coderodde.generallca;

public final class Demo {
    
    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        System.out.println("--- Seed = " + seed + " ---");
        
        BenchmarkApp app = new BenchmarkApp(seed);
        
        System.out.println(">>> Warming up...");
        app.warmup();
        
        System.out.println(">>> Warming up done.");
        System.out.println();
        
        System.out.println(">>> Benchmarking...");
        app.benchmark();
        
        System.out.println(">>> Benchmarking done.");
    }
}

LCAComputerTest.java:

package com.github.coderodde.generallca;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class LCAComputerTest {

    final LCAComputer lcaComputer;
    
    public LCAComputerTest(LCAComputer lcaComputer) {
        this.lcaComputer = lcaComputer;
    }
    
    @Test
    public void testComputeLowestCommonAncestor() {
        GeneralTree tree = new GeneralTree();
        
        tree.addRootNode("A");
        
        tree.addNode("B", "A");
        tree.addNode("C", "A");
        
        tree.addNode("D", "B");
        tree.addNode("E", "B");
        
        tree.addNode("F", "C");
        tree.addNode("G", "C");
        
        tree.addNode("H", "G");
        tree.addNode("I", "G");
        tree.addNode("J", "G");
        
        //                  A
        //                 / \
        //                /   \
        //               B     C
        //              / \   / \
        //             D   E F   G
        //                      /|\
        //                     H I J
        
        assertEquals(tree.getNode("A"), 
                     lcaComputer.computeLowestCommonAncestor(tree, "D", "H"));
        
        assertEquals(tree.getNode("G"), 
                     lcaComputer.computeLowestCommonAncestor(tree,
                                                             "I",
                                                             "H", 
                                                             "J"));
        
        assertEquals(tree.getNode("C"), 
                     lcaComputer.computeLowestCommonAncestor(tree, "F", "G"));
        
        assertEquals(tree.getNode("A"), 
                     lcaComputer.computeLowestCommonAncestor(
                             tree,
                             "D", "H", "G", "F"));
    }
}

LCAComputerV1Test.java:

package com.github.coderodde.generallca;

import com.github.coderodde.generallca.impl.LCAComputerV1;

public class LCAComputerV1Test extends LCAComputerTest {
    
    public LCAComputerV1Test() {
        super(new LCAComputerV1());
    }    
}

LCAComputerV2Test.java:

package com.github.coderodde.generallca;

import com.github.coderodde.generallca.impl.LCAComputerV2;

public class LCAComputerV2Test extends LCAComputerTest {
    
    public LCAComputerV2Test() {
        super(new LCAComputerV2());
    }    
}

评论请求

请告诉我想到的任何事。提前谢谢你。

Answer 1

编程“反”接口-走的路。

在LCAComputer中，我希望给出一个定义:对于节点n及其父p，LCA是p还是p的S父母。

(我更喜欢LCAfinder & lowestCommonAncestor()。

 --我还没有决定是否更喜欢一堆节点而不是一堆名字--两者都有吗？

如果我对 流处理感兴趣，我会考虑只提供一对任何东西。

)

GeneralTree和GeneralTreeNode：

我会很感激界面的。

在递归的情况下，我习惯于从根/节点开始树操作。

我希望能够迭代节点的子节点。

LCAComputerV1&2

我看到的是收集要处理的项目，而不是马上处理。

在visitingOnlyOneNode() (foundLCA()?)中，我可能使用

if (nodes.length <= 1)
    return true;
final GeneralTreeNode first = nodes[0];
for (int i = 1 ; i < nodes.length ; i++) {
    if (nodes[i] != first) {
        return false;
    }
}

保持简单，使用Random迁移到getQueries()时执行得很好：

   /* - pick a champion
    * - for every possible challenger, find LCA
    * - early out on <code>champion.getDepth()</code> 0
    */
    public GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                       String... nodeNames) {
        if (null == tree || null == nodeNames || 0 == nodeNames.length)
            return null;
        GeneralTreeNode
            champion = tree.getNode(nodeNames[nodeNames.length-1]);
        for (String name: nodeNames) {
            GeneralTreeNode challenger = tree.getNode(name);
            while (champion.getDepth() < challenger.getDepth())
                challenger = challenger.getParent();
            while (challenger.getDepth() < champion.getDepth())
                champion = champion.getParent();
            while (champion != challenger) {
                champion = champion.getParent();
                challenger = challenger.getParent();
            }
            if (0 == champion.getDepth())
                return champion;
        }
        return champion;
    }