CODEWITHSUNDEEP
javamemoryheap-memoryspaceout
ik024
ik024

Reputation: 156

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

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

Upvotes: 0

Views: 1081

Answers (3)

Gregor Ophey
Gregor Ophey

Reputation: 837

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)

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533502

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.

Upvotes: 1

JB Nizet
JB Nizet

Reputation: 691715

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)

Upvotes: 2

Related Questions