Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Is there anyway to optimise this recursive algorithm so I don't get an OutOfMemory error?

  1. #1
    Junior Member
    Join Date
    Oct 2012
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Is there anyway to optimise this recursive algorithm so I don't get an OutOfMemory error?

    My overall project is to create a tree and use Huffman coding to encode and decode a given file. I am at the point where I need to decode my file. To do this, i am having to step through my Huffman Tree until I reach a bottom most leaf and then return the Byte represented by that leaf. I traverse the tree according to the bit string given to the method. AKA if the current bit is 1, I go to childOne in the tree and so forth. The problem is that I keep getting an outOfMemory error. Is there any way to optimize this code so that it won't use as much memory?

    public static int decode(List<Integer> bitArray, HuffmanNode root, int startingPosition,
                              ArrayList<Byte> finalArray)
        {
        HuffmanNode childOne;
        HuffmanNode childZero;
        int currentBit = bitArray.get(startPosition);
        byte newByte;
     
                childOne = root.getChildOne();
                childZero = root.getChildZero();
                if(childOne == null && childZero == null)
                {
                   finalArray.add(root.getByteRepresented()); 
                   return startPosition;
                } 
                else if(currentBit == 1)
                {
                    startPosition++;
                    startPosition = decode(bitArray,childOne,startPosition,finalArray);
                }
                else
                {
                    startPosition++;
                    startPosition = decode(bitArray,childZero,startPosition,finalArray);
                }
     
             return startPosition;
     
    }

    I am needing to know the place in the bitArray that it ended as well as put the specified Byte into an array, so that is why I am putting the Byte into the array within the method and returning and int. Basically, is there any better way to get this done?


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default Re: Is there anyway to optimise this recursive algorithm so I don't get an OutOfMemory error?

    Your "out of memory" error is likely caused by an infinite recursion condition. Check that the base case actually exists so that the recursive algorithm has an exit.

  3. #3
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: Is there anyway to optimise this recursive algorithm so I don't get an OutOfMemory error?

    ... and check that your base case is actually reached. Eg print root to make sure you don't get "stuck".

    I'm wondering about the value startPosition in the recursive call. Shouldn't it increment? (I haven't read the code all that closely.). Also do you have to use recursion? Why not a while loop that "goes left/goes right" until it hits the bottom?
    Last edited by pbrockway2; June 20th, 2013 at 07:29 PM. Reason: silly android autocorrect...

Similar Threads

  1. [SOLVED] Cryptarithmetic Recursive Algorithm Help
    By IanSawyer in forum Algorithms & Recursion
    Replies: 0
    Last Post: November 23rd, 2012, 09:17 AM
  2. Recursive media file algorithm
    By mobinni in forum File I/O & Other I/O Streams
    Replies: 12
    Last Post: May 1st, 2012, 01:51 PM
  3. [SOLVED] I don't know why this error using get() method from the ArrayList class
    By juanp_1982 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: February 11th, 2012, 03:11 PM
  4. Replies: 5
    Last Post: March 16th, 2011, 08:55 PM
  5. [SOLVED] Experiencing a run time error, don't know what the problem is
    By scooty199 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 3rd, 2010, 10:21 AM