Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Jul 2010
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Efficiency of Two Alternate Java Methods

    I have a programming assignment and have two ways of solving a particular problem. I was wondering if one way was particularly more efficient or used less memory than another method.

    *We can only use queues for this assignment; we can't use arrays or array lists.

    I built a recursive function to find the shortest path in a node. (visited refers to a HashMap).

    The following code was before I realized we could use queues. I simply plug the key of the nodes into a string and then using a few conditional statements compare strings to find the shortest path. Our teacher was suggesting using queues (in which instead of adding the keys to the String and comparing I would add them to a queue as ints and then iterate over the finalized queue to print the shortest path). Is there really any advantage using the queue. My method seems just fine and produces the output my professor is looking for without using a queue and so honestly I see no advantage to recoding. I was looking for the advice / comments of more knowledgeable programmers to see if there would be a solid reason to recode.

    Thanks,
    Travis

    PHP Code:
        private String path(Node nd,int y) {
            if(
    nd==null//boundary condition - run into a null link
                
    return "";
                
            
    ////Boundary condition - ran into a circular path when we didn't want to
            //!firstPass allows us to search for paths from xNode to yNode where xNode==yNode
            //without getting stopped at the beginning since nd.getID()==y at the start in this case 
            
    if(nd.getID()==y&&!firstPass
                return 
    Integer.toString(nd.getID());
                
        
            if(
    visited.contains(nd.getID())) // Have run into previously searched node?
                
    return "";
                
            
    //Now if we go back to the same node we will get stopped
            //Helps in the case that xNode==yNode
            
    firstPass=false;
            
    visited.add(nd.getID()); //Make sure don't traverse this node again for left
            
            //Recursive Calls
            
    String lc path(nd.getLeft(),y);
            
            
    //Occasionally the search down the left and the search down the right
            //Will run into the same nodes. Without this piece of code searches down the right
            //would potentially get stopped prematurely because certain nodes had already 
            //been 'visited' when trying to find a path down the left, but they have not 
            //been 'visited' during the current search for a path down the right
            
    if(lc.contains(Integer.toString(nd.getRight().getID()))) {
                
    visited.remove(nd.getRight().getID());
            }
            
            
    //Search the right
            
    String rc path(nd.getRight(),y);
            
            
    //If there is a path down both the right and left of the current node
            
    if(lc.contains(Integer.toString(y))&&rc.contains(Integer.toString(y)))
            {
                
    //Return current ID plus the shorter path
                
    if(lc.length()<=rc.length()) {//Return left path if left path is shorter or equal to right path
                    
    return Integer.toString(nd.getID()) + " " lc;
                }
                else 
    //Right is shorter path
                    
    return Integer.toString(nd.getID()) + " " rc;
            }
            
    //Only the left side contains a path to the target node
            
    else if(lc.contains(Integer.toString(y)))
                return 
    Integer.toString(nd.getID()) + " " lc;
            
    //Only the right side contains a path to the target node
            
    else if(rc.contains(Integer.toString(y)))
                return 
    Integer.toString(nd.getID()) + " " rc;
            
    //Return nothing if none of these previous if none of the if statements are met
            
    else
                return 
    "";
        } 

  • #2
    New to the CF scene
    Join Date
    Jul 2010
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Reposted in proper forum.


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •