Results 1 to 14 of 14
  1. #1
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default Java Heap space error using ArrayList.

    I have been doing Project Euler #14.

    I am really new to ArrayList, so I am imagining that since ArrayLists stores objects then its a bit different then a int[].

    Anyway if I put 1,000,000 in the main method with largestSequence(1000000);

    I get a Java Heap Space error.

    Can someone explain this and help me understand my inefficiency?

    Java Code:
    import java.util.ArrayList;
    
    public class Sequence {
    
        private ArrayList<Integer> sequenceList;
        private int num = 0, size = 0, largest = 0;
    
    
        public void largestSequence(int listToTry) {
            for (int i = 1; i <= listToTry; i++) {
                getSequence(i, false);
                checkIfLargest();
    
            }
            getSequence(largest);
            System.out.println("The largest sequence is from number " + largest);
        }
    
        public void getSequence(int seqNum) {
            getSequence(seqNum, true);
        }
        private void getSequence(int seqNum, boolean display) {
    
            sequenceList = new ArrayList<Integer>();
            sequenceList.add(seqNum);
            this.num = seqNum;
            do {
                if (this.num % 2 == 0) {
                    isEven(this.num);
                } else {
                    isOdd(this.num);
                }
            } while (sequenceList.get(sequenceList.size()-1) != 1);
    
            if (display) {
                displayInfo();
            }
        }
    
        //Odd Sequence calculation
        private void isOdd(int num) {
            this.num = 3 * num + 1;
            sequenceList.add(this.num);
        }
        //Even Sequence calculation
        private void isEven(int num) {
            this.num = num / 2;
            sequenceList.add(this.num);
        }
    
    
        // checking and displaying
        private void checkIfLargest() {
            if (sequenceList.size() > size) {
                size = sequenceList.size();
                largest = sequenceList.get(0);
            }
        }
        private void displayInfo(){
            System.out.println(sequenceList);
            System.out.println("With a length of " + sequenceList.size());
        }
    
    }
    
    
    
    //Main method and class
    class SequenceTest {
        public static void main(String[] args) {
            Sequence test = new Sequence();
            test.getSequence(13);
            test.largestSequence(50);
        }
    }
    The Error!

    Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2760)
    at java.util.Arrays.copyOf(Arrays.java:2734)
    at java.util.ArrayList.ensureCapacity(ArrayList.java: 167)
    at java.util.ArrayList.add(ArrayList.java:351)
    at Sequence.isEven(Sequence.java:48)
    at Sequence.getSequence(Sequence.java:29)
    at Sequence.largestSequence(Sequence.java:11)
    at SequenceTest.main(SequenceTest.java:5)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Nativ e Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Native MethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(De legatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at com.intellij.rt.execution.application.AppMain.main (AppMain.java:115)

    Process finished with exit code 1

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default

    The JVM has by default a limited amount of memory, and will throw this exception if it is exceeded. Increase the memory of the JVM using the command line argument -Xmx(size), for example -Xmx512M to increase to 512mb

  3. #3
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    Thanks for the info doWhile. I like your name.. haha.

    I know that at least test.getSequence(113383) throws the exception.

    A memory issue.. hmm.. could I have designed this different or do i need to do this memory adjustment?

  4. #4
    user0 is offline Senior Member
    Join Date
    Dec 2010
    Posts
    100
    Rep Power
    0

    Default

    Hi Acoustic. I am also relatively new to Java and have attempted this Euler problem # 14. It is a hailstone number sequence problem. I managed to solve this problem using a FOR loops and a HashMap to remember how many sequence items a particular number generates. I use the map to make the program faster - mine solves under 3 seconds.

    However, I know this problem can be solved more elegantly and much more faster, possibly using recursion. To be honest my recursion skills are not the best. Perhaps if anyone can suggest a more efficient and elegant solution, please post!

    Here is a link to the problem: Problem 14 - Project Euler

    Best,
    --user0--

  5. #5
    user0 is offline Senior Member
    Join Date
    Dec 2010
    Posts
    100
    Rep Power
    0

    Default

    Also - just a suggestion, you may want to use long instead of int, because the sequence may reach large numbers which are out of range for ints.

    Best,
    --user0--

  6. #6
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    Quote Originally Posted by user0 View Post
    Also - just a suggestion, you may want to use long instead of int, because the sequence may reach large numbers which are out of range for ints.

    Best,
    Well User, thank you very much. Actually changing everything to Long instead of int was the solution. I didn't realize the numbers went up to 3 + billion.

    I am not happy with my 9 or 10 seconds to solve, so I will check out this hashmap it sounds really efficient.
    Last edited by AcousticBruce; 01-03-2011 at 08:04 AM.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,679
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by AcousticBruce View Post
    Well User, thank you very much. Actually changing everything to Long instead of int was the solution. I didn't realize the numbers went up to 3 + billion.

    I am not happy with my 9 or 10 seconds to solve, so I will check out this hashmap it sounds really efficient.
    Even a brute force implementation uses +- 2 secs on my laptop (2.1 GHz, 2 cores). It surprises me that user0's implementation, which uses a form of memoizing, takes 3 secs.

    But what surprises me most is that Apple goofed with their clock driver in their iPhone; it has been done right in Unix already somewhere in the later seventies in the previous century ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    What brute force method Josah?

    I have a core duo 2.26 with 4gb ram and I am getting 9 or 10 seconds.

    run this code Josah.... tell me if you get 2 seconds.

    Java Code:
    import java.util.ArrayList;
    
    public class Sequence {
    
        private ArrayList<Long> sequenceList;
        private long num = 0, size = 0, largest = 0;
    
    
        public void largestSequence(long listToTry) {
            for (int i = 1; i <= listToTry; i++) {
                getSequence(i, false);
                checkIfLargest();
    
            }
            getSequence(largest);
            System.out.println("The largest sequence is from number " + largest);
        }
    
        public void getSequence(long seqNum) {
            getSequence(seqNum, true);
        }
        private void getSequence(long seqNum, boolean display) {
    
            sequenceList = new ArrayList<Long>();
            sequenceList.add(seqNum);
            this.num = seqNum;
            do {
                if (this.num % 2 == 0) {
                    isEven(this.num);
                } else {
                    isOdd(this.num);
                }
            } while (sequenceList.get(sequenceList.size()-1) != 1);
    
            if (display) {
                displayInfo();
            }
        }
    
        //Odd Sequence calculation
        private void isOdd(long num) {
            this.num = 3 * num + 1;
            sequenceList.add(this.num);
        }
        //Even Sequence calculation
        private void isEven(long num) {
            this.num = num / 2;
            sequenceList.add(this.num);
        }
    
    
        // checking and displaying
        private void checkIfLargest() {
            if (sequenceList.size() > size) {
                size = sequenceList.size();
                largest = sequenceList.get(0);
            }
        }
        private void displayInfo(){
            System.out.println(sequenceList);
            System.out.println("With a length of " + sequenceList.size());
        }
    
    }
    
    
    //.......................................
    //main method!!
    class SequenceTest {
        public static void main(String[] args) {
            //StringSequence test = new StringSequence();
            Sequence test = new Sequence();
            test.largestSequence(1000000);
        }
    }

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,679
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by AcousticBruce View Post
    What brute force method Josah?

    I have a core duo 2.26 with 4gb ram and I am getting 9 or 10 seconds.

    run this code Josah.... tell me if you get 2 seconds.
    It runs in +- 4.8 seconds on my laptop (it isn't the fastest laptop in the world ;-). My code runs in +- 1 second; here's the code, nothing clever in it:

    Java Code:
    public class T {
    	
    	private static long collatz(long n) {
    		
    		long c= 0;
    		
    		for (c= 0; n > 1; c++) {
    			n= (n%2 == 0)?(n/2):(3*n+1);
    			if (n <= 0) System.out.println("***");
    		}
    		
    		return c;
    	}
    	
        public static void main (String[] args) {
     
        	long nmax= -1;
        	long cmax= -1;
     
        	long start= System.currentTimeMillis();
        	
        	for (long n= 1; n <= 1000000L; n++) {
        		long c= collatz(n);
        		if (c > cmax) {
        			cmax= c;
        			nmax= n;
        		}
        	}
        	
        	System.out.println("cmax: "+cmax+" nmax: "+nmax);
        	System.out.println(System.currentTimeMillis()-start);
       }
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    AcousticBruce is offline Senior Member
    Join Date
    Dec 2010
    Location
    Indiana
    Posts
    202
    Rep Power
    4

    Default

    Yes your code runs in +-1 sec on mine.

    I know that if i rewrite my code, I will not use an Array or list until it finds the right number (I kinda like it displaying all the sequence).


    So you get 4 seconds with my code. I really need to know why it is running so well for you. My laptop is E6400 2.2Ghz and 4gb ram. yours is almost twice as fast. Maybe mine is set wrong?

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,679
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by AcousticBruce View Post
    So you get 4 seconds with my code. I really need to know why it is running so well for you. My laptop is E6400 2.2Ghz and 4gb ram. yours is almost twice as fast. Maybe mine is set wrong?
    More like 5 secs (4.8 or so); I ran your code from Eclipse without any special settings. It doesn't matter much if I run it from a shell using java.exe.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    user0 is offline Senior Member
    Join Date
    Dec 2010
    Posts
    100
    Rep Power
    0

    Default

    I ran it on my old linux machine, its ancient as the hills :) , and it takes about 2-3 secs using hashmap. Brute forcing on the same machine took about 10 secs. When I get a chance I shall run the code on my laptop which is much newer and see if it makes a difference.

    Not to drift off topic here but are you guys using some kind of code or software to time your code? If so please share. Each time I write and run something I tend to count the seconds in my head, until I realize I have created an infinite loop :D

    Thanks!
    --user0--

  13. #13
    user0 is offline Senior Member
    Join Date
    Dec 2010
    Posts
    100
    Rep Power
    0

    Default

    Ah - just saw JoSaH's code. He uses System.currentTimeMillis() and I think that's the answer to my question. Thanks JoSaH :)
    --user0--

  14. #14
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,679
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by user0 View Post
    Ah - just saw JoSaH's code. He uses System.currentTimeMillis() and I think that's the answer to my question. Thanks JoSaH :)
    You're welcome of course but that method isn't really accurate; it has to take the 'warming up' of the JVM into account (i.e. jit compilation because of hot spot triggering). To be more accurate one should run a piece of code a couple of times, then start timing and run the same code some more. At the end you'd take the average of the total elapsed time w.r.t the number of runs.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Replies: 5
    Last Post: 08-13-2010, 11:04 AM
  2. java out of memory error-heap space error
    By elsanthosh in forum NetBeans
    Replies: 4
    Last Post: 06-15-2010, 10:31 AM
  3. Java heap space,
    By babyboban in forum Advanced Java
    Replies: 18
    Last Post: 01-14-2010, 01:22 PM
  4. Java Heap Space
    By sandeeprao.techno in forum Advanced Java
    Replies: 19
    Last Post: 10-30-2008, 12:27 PM
  5. Java heap space error
    By gezzel in forum New To Java
    Replies: 19
    Last Post: 09-25-2008, 01:07 AM

Posting Permissions

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