Program efficiency and java.lang.OutOfMemoryError: Java heap space

Question

The problem is to remove every 2nd element until the last one remains. (Assuming the elements are placed in circle)

My program works fine for small values of n but when i use a large value it gives me a java.lang.OutOfMemoryError: Java heap space message.

Can some help me out as to what I need to do to make my code more efficient and solve this error.

Thank You!

import java.util.*;

public class ArrayLists {
    public static void main(String[] args) {
        ArrayList myList = new ArrayList();
        int n = 23987443;
        for (int i = 1; i <= n; i = i + 2) {
            myList.add("" + i);
        }

        Object x = myList.get(myList.size() - 1);
        Object y = myList.get(myList.size() - 1);
        while (myList.size() != 1) {
            if (x == y) {
                for (int i = 0; i <= myList.size() - 1; i++) {
                    myList.remove(i);
                }
            } 
            else {
                x = y;
                for (int i = 1; i <= myList.size() - 1; i++) {
                    myList.remove(i);
                }
            }
            y = myList.get(myList.size() - 1);
        }
        System.out.println("Winner:" + myList);
    }
}

Are you sure this problem statement is complete "The problem is to remove every 2nd element until the last one remains." ? — Avinash Singh, Mar 09 '13 at 22:39
This is not related to the answer of the question, but why are you using x and y as Object when you know your list contain Strings? — Kakalokia, Mar 09 '13 at 22:41
The most obvious thing is don't use strings (change `"" + i` to `i`) but apart from that, what in the *devil* is this trying to do?! — Boann, Mar 09 '13 at 22:43
http://stackoverflow.com/questions/37335/how-to-deal-with-java-lang-outofmemoryerror-java-heap-space-error-64mb-heap — fonZ, Mar 09 '13 at 22:44
Can you say what your program is doing as I suspect it would be much more efficient done another way. — Peter Lawrey, Mar 09 '13 at 22:49
BTW: You are not just removing every second element, you are removing the odd elements sometimes and removing the even elements sometimes. — Peter Lawrey, Mar 09 '13 at 23:13
@AvinashSingh let me put it in another way. Assume there are 5 ppl standing in a circle labled 1,2,3,4,5. Now every 2 person gets eliminated. If we r starting with the person lable 1, person lable 2 gets eliminated then 4 now repeat it till one person remains. — ik024, Mar 12 '13 at 10:10
@AliAlamiri I have ued it as i was getting an error when i used x and y as int or string. The error said "Expected Object" so i had to use an object. That function returns an object so it shud be assigned to an object. — ik024, Mar 12 '13 at 10:19
@Boan u can refer my previous comments to understand the problem more clearly. — ik024, Mar 12 '13 at 10:21
@PeterLawrey Read my previous comment b4 u read this.X=last eliment b4 iteration,Y=last eliment after iteration. The statement if(x==y) m using it to check if the last eliment is the same after the iteration,if its same den it means its previous eliment was eliminated,so d nxt one to b eliminated wud b the one labled 1. Hope i was clear enough. — ik024, Mar 12 '13 at 10:31

score 2 · Answer 1 · answered Mar 09 '13 at 22:40

2

You're building a huge list of strings. So you'll need enough memory to hold all the list. You could make it less consuming by initializing the list with the appropriate size, avoiding temporary copies to enlarge the list:

int n = 23987443;
List<String> myList = new ArrayList<String>(23987443);

You could also use a List<Integer> instead, since that's what the list contains actually.

But a huge list of strings needs lots of memory. Enlarge the heap size with

java -Xmx1024m ...

for example (1024 MB of heap)

answered Mar 09 '13 at 22:40

JB Nizet

678,734
91
1,224
1,255

how wud i use java -Xmx1024m in my program and where wud i use it(The exact statement as well). Any link to understand it wud very much appreciated – ik024 Mar 12 '13 at 10:34
The example is in the answer. -Xmx is a JVM option, that you pass to the java executable when launching your program: `java -Xmx1024m -cp myjar.jar com.foo.bar.MyMainClass`. – JB Nizet Mar 12 '13 at 11:25
Thank you. Well i wud like to know if i can change the heap size in my program directly instead of in command line. – ik024 Mar 12 '13 at 12:44

score 1 · Answer 2 · answered Mar 09 '13 at 23:12

This uses less memory but is quote a bit faster as it is O(N * log N) instead of O(N^2 * log N)

public static void main(String[] args) {
    // for (int n = 1; n < 400; n++) {
    int n = 23987443;
    System.out.print(n + ": ");
    result(n);
    // }
}

private static void result(int n) {
    List<Integer> myList = new ArrayList<>(), myList2 = new ArrayList<>();
    for (int i = 1; i <= n; i = i + 2) {
        myList.add(i);
    }

    Integer x = myList.get(myList.size() - 1);
    Integer y = myList.get(myList.size() - 1);
    while (myList.size() != 1) {
        if (x == y) {
            for (int i = 1; i < myList.size(); i += 2) {
                myList2.add(myList.get(i));
            }
        } else {
            x = y;
            for (int i = 0; i <= myList.size() - 1; i += 2) {
                myList2.add(myList.get(i));
            }
        }
        List<Integer> tmp = myList2;
        myList2 = myList;
        myList = tmp;
        myList2.clear();

        y = myList.get(myList.size() - 1);
       // System.out.println("\t" + myList);
    }
    System.out.println("Winner:" + myList.get(0));
}

Note: if you use TIntArrayList instead of ArrayList<Integer> it will use about 1/5 of the memory.

Interesting that u have assigned x and y as int when i used it as int it was throwing error telling "object expected" ca u explain me why and how? Thanks — ik024, Mar 12 '13 at 10:38

Gregor Ophey · Accepted Answer · 2013-03-11T12:11:00.630

0

The answer to your problem can be computed with a closed form, for if you write the number of elements in your list as follows:

n = 2^m + l

where m is the largest power of 2, such that 2^m <= n

then the winner is w = 2*l + 1.

So here is a more efficient program:

public class ArrayLists {
  public static void main(String[] args) {
    int n = 23987443;
    int pow = Integer.highestOneBit(n);
    int l = n - pow;
    System.out.println("Winner:[" +((2*l)+1)+"]" );
  }
}

The answer for that value of n:

Winner:[14420455]

To be honest I did not come up with the solution myself, but remembered reading about the Josephus problem in the book "Concrete Mathematics" (Google will find a PDF, check out section 1.3)

edited Mar 11 '13 at 12:11

answered Mar 09 '13 at 23:54

Gregor Ophey

817
6
12

The answer is perfectly correct! Any more links like this where i can find an approach for a problem in a more mathematical way will be very much appreciated. Thanks! – ik024 Mar 12 '13 at 10:43
However i am not able to grasp the logic it will be very helpful if u can explain it relating it to my problem. Thanks Again. – ik024 Mar 12 '13 at 10:46
I think i have partially understood it :D – ik024 Mar 12 '13 at 13:01
Well, I said I remembered reading about it, not that I understood it myself :), however, for me it always helps to write out examples starting from n=1 going up, similar to what is done in the book on page 10, to guess a closed form that fits the results (e.g. (1.9)). Also the circle diagrams used to establish the recurrence (1.8) are very helpful. Proving the closed form is done with induction, showing that it is identical to the recurrence ... I can also recommend the book "Introduction to Algorithms" by Udi Manber, where proof by induction is used a method to design programs – Gregor Ophey Mar 12 '13 at 21:16
Well thank you for sharing it Gregor Ophey :) May u be blessed with more knowledge :D and keep sharing :) – ik024 Mar 13 '13 at 14:30
@ik024, since you are new on stackoverflow: If you think that one of the answers given here is solving your problem, what you would normally do, is to mark this answer as the accepted one. This will increase the poster's reputation (and your's, too). – Gregor Ophey Mar 14 '13 at 19:45
it seems v r oly allowed to select one as the right ans.... wat if v want to select 2 ans??? – ik024 Mar 16 '13 at 05:14
@ik024: Thanks for accepting my answer. I think (but I'm not sure) you can only choose one, so select the one that suits you best. You can always vote up other answers that you would consider helpful, too. – Gregor Ophey Mar 16 '13 at 11:00

Program efficiency and java.lang.OutOfMemoryError: Java heap space

3 Answers3