StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy recursion in java is so slow compared to .net?
text
Body
copied!<p>I wrote an algorithm to find all the paths possible between two points. i wrote the algorithm in both c#.net and java. The algorithm produces around 40,000 possible paths. To my amazement the algorithm in C#.net took only 13 mins to complete (in i3 processor), while java could not complete even in 4 hrs.</p> <p>recursion may be slow in java , but i don't think this much.</p> <p>Is there anything i am missing ?</p> <p>Ok here is the requirement , a maze is a two dimensional array which contains numbers 0,1,2 and 3. 0 represents the walkable points, 1 represents the obstacle , 2 the starting point and 3 the exit point. the program was to find all the paths from point 2 to 3 by touching all 0s only one time. we cannot step over 1s as they are obstacles.</p> <h2>here is the code in C#.Net</h2> <pre><code>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(); } } </code></pre> <h2>and here is the program in Java</h2> <pre><code>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; } } </code></pre> <p>the ObservableStack is a normal stack made of array. i made it observable to connect it to applet to animate the traversal.</p> <p>I hope i have provided enough detail.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload