c# - 为什么java中的递归比.net慢？

Question

我编写了一个算法来查找两点之间所有可能的路径。我用 c#.net 和 java 编写了该算法。该算法产生大约 40,000 条可能的路径。令我惊讶的是，C#.net 中的算法只花了 13 分钟就完成了(在 i3 处理器中)，而 java 甚至在 4 小时内都无法完成。

递归在java中可能很慢，但我不这么认为。

我有什么遗漏的吗？

好的，这里是需求，迷宫是一个二维数组，包含数字0、1、2和3。0代表可行走点，1代表障碍物，2代表起点，3代表导出点。该程序只需一次触摸全 0 即可找到从点 2 到点 3 的所有路径。我们不能跨过 1，因为它们是障碍。

这是 C#.Net 中的代码

public class Maze
{
    //Represents each point in the Maze.
    private class Node
    {
        private int val;

        public Node(int num)
        {
            val = num;

            switch (num)
            {
                case 1: IsPit = true;
                    break;
                case 2: IsEntranceNode = true;
                    break;
                case 3:
                    IsExitNode = true;
                    break;
            }
        }
        public string Name { get; set; }

        public bool IsPit { get; private set; }
        public bool IsVisited { get; set; }
        public bool IsExitNode { get; private set; }
        public bool IsEntranceNode { get; private set; }

        public Node UpNode { get; set; }
        public Node DownNode { get; set; }
        public Node LeftNode { get; set; }
        public Node RightNode { get; set; }
    }

    #endregion

    //Number of pits in the maze.
    private int numberOfPits;

    //Stack traces the path traversed.
    private Stack<String> pathTraversed;

    //Represents the maze.All Nodes are wired to its adjacent nodes.
    private Node[,] Maze { get; set; }

    //Number of paths found.
    private int pathCount = 1;

    //displays a set.
    static void printSet(int[,] set)
    {
        Console.Write(" \t");
        for (var i = 0; i < set.GetLength(1); i++)
            Console.Write(i + "  ");

        Console.WriteLine("\n--------------------------");

        for (var i = 0; i < set.GetLength(0); i++)
        {
            Console.Write((char)(65 + i) + " | \t");
            for (var j = 0; j < set.GetLength(1); j++)
                Console.Write(set[i, j] + "  ");

            Console.WriteLine();
        }
    }

    static void Main(string[] args)
    {
        int[,] set2 = new int[7, 7] {   { 2, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 3, 1, 1 } 
                                    };          

        Console.WriteLine("\n\nSet 2");
        Console.WriteLine("=====");
        printSet(set2);

        Console.WriteLine("\nPath found");
        Console.WriteLine("==========");
        startTime = DateTime.Now;
        new Maze().AddPoints(set2).FindPaths();
        endTime = DateTime.Now;
        difference = endTime.Subtract(startTime).TotalMinutes;
        Console.WriteLine("Time taken in mins : " + difference);
        Console.WriteLine("\nPress any key to exit");
        Console.ReadKey();
    }

    //Adds points to the maze.Transforms a matrix to 2 dimensional connected nodes.
    public Program AddPoints(int[,] matrix)
    {
        Maze = new Node[matrix.GetLength(0), matrix.GetLength(1)];

        for (int i = 0; i < matrix.GetLength(0); i++)
        {
            for (var j = 0; j < matrix.GetLength(1); j++)
            {
                Node node = Maze[i, j];

                if (node == null)
                {
                    node = new Node(matrix[i, j]);
                    Maze[i, j] = node;
                }
                if (!(i - 1 < 0))
                    Maze[i - 1, j].DownNode = node;

                if (!(i + 1 > matrix.GetLength(0) - 1))
                {
                    var downNode = Maze[i + 1, j];
                    if (downNode == null)
                        Maze[i + 1, j] = new Node(matrix[i + 1, j]);
                    Maze[i + 1, j].UpNode = node;
                }

                if (!(j - 1 < 0))
                    Maze[i, j - 1].RightNode = node;

                if (!(j + 1 > matrix.GetLength(1) - 1))
                {
                    var leftNode = Maze[i, j + 1];
                    if (leftNode == null)
                        Maze[i, j + 1] = new Node(matrix[i, j + 1]);
                    Maze[i, j + 1].LeftNode = node;
                }

                node.Name = ((char)(65 + i)).ToString() + j.ToString();
                if (node.IsPit)
                    numberOfPits++;
            }
        }
        return this;
    }

    //Finds path between the start node and end node.
    public void FindPaths()
    {
        var startNode = Maze[0, 0];

        if (!startNode.IsEntranceNode)
            throw new Exception("Node is not starting node.");

        pathTraversed = new Stack<string>();

        pathTraversed.Push(startNode.Name);
        Traverse(startNode.RightNode);
        Traverse(startNode.DownNode);
        Traverse(startNode.LeftNode);
        Traverse(startNode.UpNode);
    }

    //Traverses a node.
    private void Traverse(Node node)
    {
        if (node == null)
            return;

        if (node.IsEntranceNode || node.IsPit || node.IsVisited)
            return;

        if (node.IsExitNode)
        {
            pathTraversed.Push(node.Name);
            if (pathTraversed.Count == Maze.Length - numberOfPits)
            {
                var msg = "Path " + pathCount++ + " : " + string.Join("->", pathTraversed.Reverse());
                Console.WriteLine(msg);
            }
            pathTraversed.Pop();
            return;
        }

        pathTraversed.Push(node.Name);
        node.IsVisited = true;

        Traverse(node.RightNode);   //
        Traverse(node.DownNode);    // Move to Next Node
        Traverse(node.LeftNode);    //  
        Traverse(node.UpNode);      //

        if (node.Name != pathTraversed.Peek())
            throw new Exception("Error in Logic.");

        node.IsVisited = false;
        pathTraversed.Pop();
    }
}

这是 Java 程序

public class PathFinder
{
  public static void main(String[] args){
    int[][] set1 = new int[][] { { 2, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 3, 1, 1 }};
    ObservableStack<String> observableStack = new ObservableStack<String>();
    StackObserver stackObserver = new StackObserver(plotter);
    Maze maze = new Maze(set1,(IPathFinderStack<String>)observableStack);
    maze.findPaths();                   
  }
}

public class Maze {

private Node[][] nodes;

IPathFinderStack<String> pathTraversed;

private int numberOfPits = 0;

private  int result = 0;

public  Node[][] getVector(){
    return nodes;
}

public Maze(int[][] matrix ,IPathFinderStack<String> stack){
    pathTraversed = stack;
    addNodes(matrix);
}   

public void addNodes(int[][] matrix)    {

    int rows = matrix.length;
    int cols = matrix[0].length;

    nodes = new Node[rows][cols];

    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            Node node = nodes[i][j];

            if (node == null){
                node = new Node(matrix[i][j]);
                nodes[i][j] = node;
            }

            if (!(i - 1 < 0))
                nodes[i-1][j].setDownNode(node);

            if (!((i + 1) > rows - 1))
            {
                Node downNode = nodes[i+1][j];
                if (downNode == null)
                    nodes[i + 1][j] = new Node(matrix[i+1][j]);
                nodes[i + 1][j].setUpNode(node);
            }

            if (!(j - 1  < 0))
                nodes[i][j-1].setRightNode(node);

            if (!(j + 1 > cols - 1)){
                Node leftNode = nodes[i][j+1];
                if (leftNode == null)
                    nodes[i][j+1] = new Node(matrix[i][j+1]);
                nodes[i][j+1].setLeftNode(node);
            }

            String name =  new String(new char[] {(char) (65 + i), (char)(48 + j)});

            node.setName(name);

            if (node.isPit())
                this.numberOfPits ++;
        }
    }
}

public void findPaths(){    

    Node startNode = nodes[0][0];

    pathTraversed.push(startNode.getName());

    Traverse(startNode.getRightNode());
    Traverse(startNode.getDownNode());
    Traverse(startNode.getLeftNode());
    Traverse(startNode.getUpNode());
}   

private void Traverse(Node node){   

        if (node == null)
            return ;

    if (node.isEntrance() || node.isVisited() || node.isPit())
        return ;

    if (node.isExit()){

            pathTraversed.push(node.getName());
        if (pathTraversed.getLength() == (nodes[0].length * nodes.length) - numberOfPits){
            String msg = "Path found" + (++result);
            Logger.Log(msg);
            Logger.Log(pathTraversed.toString());
        }

        pathTraversed.pop();
        return;             
    }

    pathTraversed.push(node.getName());
    node.setVisited(true);

    Traverse(node.getRightNode());
    Traverse(node.getDownNode());
    Traverse(node.getLeftNode());
    Traverse(node.getUpNode());

    node.setVisited(false);
    pathTraversed.pop();        
}
}

public class Node
{
private String name;
private int val;
private boolean isPit;
private boolean isVisited;
private boolean isEntrance;
private boolean isExit;

private Node downNode;
private Node upNode;
private Node leftNode;
private Node rightNode;

public Node(int val){
    this.val = val;
    this.isPit = (val == 1);
    this.isEntrance = (val == 2);
    this.isExit = (val == 3);
    this.isVisited = false;         
}

public String getName(){
    return this.name;
}

public void setName (String name) {
    this.name = name;
}

public boolean isPit(){
    return isPit;
}

public boolean isVisited(){
    return isVisited;
}

public void setVisited(boolean isVisited)   {
    this.isVisited = isVisited;
}

public boolean isEntrance(){
    return isEntrance;
}

public boolean isExit(){
    return isExit;
}

public Node getDownNode(){
    return downNode;
}

public void setDownNode(Node node){
    downNode = node;
}

public Node getUpNode(){
    return upNode;
}

public  void setUpNode(Node node){
    upNode = node;
}

public Node getLeftNode(){
    return leftNode;
}

public void setLeftNode(Node node){
    leftNode = node;
}

public Node getRightNode(){
    return rightNode;
}   

public void setRightNode(Node node) {
    rightNode = node;
}
}   

ObservableStack 是一个由数组组成的普通堆栈。我将其连接到小程序以实现遍历动画。

我希望我已经提供了足够的细节。

Answer 1

我采用了不同的编码方式，并且速度更快。

import java.util.ArrayList;
import java.util.List;

public class PathFinder {
    public static void main(String[] args) {
        int[][] set1 = new int[][]{{2, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 3, 1, 1}};

        long start = System.nanoTime();
        Maze maze = new Maze(set1);
        List<String> paths = new ArrayList<String>();
        maze.findPaths(0, 0, new StringBuilder(), paths);
        System.out.printf("Paths found %,d%n", paths.size());
        long time = System.nanoTime() - start;
        System.out.printf("Took %,.1f seconds%n", time / 1e9);
    }
}

class Node {
    final int num;
    private boolean traversed;
    private final String name;

    Node(int num, String name) {
        this.num = num;
        this.name = name;
    }

    public boolean isTraversed() {
        return traversed;
    }

    public void setTraversed(boolean traversed) {
        this.traversed = traversed;
    }

    public String getName() {
        return name;
    }

    public boolean isExit() {
        return num == 3;
    }

    public boolean isPit() {
        return num == 1;
    }
}

class Maze {
    private final Node[][] nodes;
    private final int rows, cols;
    private final int nonPits;

    public Maze(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;

        nodes = new Node[rows][cols];
        int nonPits = 0;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++) {
                nodes[i][j] = new Node(matrix[i][j], "" + (char) ('A' + i) + (char) ('0' + j));
                if (!nodes[i][j].isPit())
                    nonPits++;
            }
        this.nonPits = nonPits;
    }

    public void findPaths(int x, int y, StringBuilder path, List<String> paths) {
        if (x < 0 || x >= cols) return;
        if (y < 0 || y >= rows) return;
        Node node = nodes[y][x];
        if (node.isTraversed() || node.isPit()) return;

        node.setTraversed(true);
        int length = path.length();
        path.append(node.getName());
        if (node.isExit()) {
            if (path.length() == nonPits*2) {
                paths.add(path.toString());
                if (paths.size() % 10000 == 0)
                    System.out.printf("... found %,d paths%n", paths.size());
            }
        } else {
            findPaths(x - 1, y, path, paths);
            findPaths(x + 1, y, path, paths);
            findPaths(x, y - 1, path, paths);
            findPaths(x, y + 1, path, paths);
        }

        path.setLength(length);
        node.setTraversed(false);
    }
}

打印

Paths found 40,616
Took 81.1 seconds

<小时/>

很多时间都花在记录路径上。如果它只是计算路径(需要相同数量的递归)

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class PathFinder {
    public static void main(String[] args) {
        int[][] set1 = new int[][]{{2, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 3, 1, 1}};

        long start = System.nanoTime();
        Maze maze = new Maze(set1);
        long[] count = {0L};
        maze.findPaths(0, 0, 1, count);
        System.out.printf("Paths found %,d%n", count[0]);
        long time = System.nanoTime() - start;
        System.out.printf("Took %,.1f seconds%n", time / 1e9);
    }
}

class Node {
    final int num;
    private boolean traversed;
    private final String name;

    Node(int num, String name) {
        this.num = num;
        this.name = name;
    }

    public boolean isTraversed() {
        return traversed;
    }

    public void setTraversed(boolean traversed) {
        this.traversed = traversed;
    }

    public String getName() {
        return name;
    }

    public boolean isExit() {
        return num == 3;
    }

    public boolean isPit() {
        return num == 1;
    }
}

class Maze {
    private final Node[][] nodes;
    private final int rows, cols;
    private final int nonPits;

    public Maze(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;

        nodes = new Node[rows][cols];
        int nonPits = 0;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++) {
                nodes[i][j] = new Node(matrix[i][j], "" + (char) ('A' + i) + (char) ('0' + j));
                if (!nodes[i][j].isPit())
                    nonPits++;
            }
        this.nonPits = nonPits;
    }

    public void findPaths(int x, int y, int depth, long[] count) {
        if (x < 0 || x >= cols) return;
        if (y < 0 || y >= rows) return;
        Node node = nodes[y][x];
        if (node.isTraversed() || node.isPit()) return;

        node.setTraversed(true);
        if (node.isExit()) {
            if (depth == nonPits) {
                count[0]++;
                if (count[0] % 10000 == 0)
                    System.out.printf("... found %,d paths%n", count[0]);
            }
        } else {
            findPaths(x - 1, y, depth + 1, count);
            findPaths(x + 1, y, depth + 1, count);
            findPaths(x, y - 1, depth + 1, count);
            findPaths(x, y + 1, depth + 1, count);
        }
        node.setTraversed(false);
    }
}

打印

Paths found 40,616
Took 58.5 seconds