Java Heap space error using ArrayList.

[AcousticBruce]

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?

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

[doWhile]

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

[AcousticBruce]

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?

[user0]

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]

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,

[AcousticBruce]

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.

[JosAH]

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

[AcousticBruce]

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.

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);
    }
}

[JosAH]

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:

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

[AcousticBruce]

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?

[JosAH]

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

[user0]

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]

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

[JosAH]

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