CODEWITHSUNDEEP
java
Ram Santiago
Ram Santiago

Reputation: 27

Java - OutOfMemoryError : Java heap space

I'm trying to create an string arraylist with a size 100,000, wherein every element after the first two is the previous two strings concatenated. The problem is, I run out of memory before I even reach 100 strings. I plan to use this arraylist to do a binary search and output a letter in the string based on the input given, which is the index of the string, and the index of the letter within the string.

Here's the code

    public static void generateSequence(int numStrings, ArrayList<String> input){
        String temp = "", S1, S2;
        for(int i = 0; i < n; i++) {
            if(i == 0) {
                input.add("H");
            }
            else if(i == 1) {
                input.add("A");
            }
            else {
                S1 = input.get(input.size() - 2);
                S2 = input.get(input.size() - 1);
                temp = S1.concat(S2);
                input.add(temp);
                temp = "";
            }
        }
    }

I'm not sure how to be more efficient with the memory usage to get the arraylist I need for this, so any advice would be helpful. Thank you.

Upvotes: 0

Views: 259

Answers (1)

dangling else
dangling else

Reputation: 448

So the Nth element is the concatenation of the N-1th and N-2th elements?

Thus the length of the Nth element is the sum of the lengths of the two previous elements.

You're talking about a huge amount of storage. This code shows you how much storage the Nth entry needs.

    double n0 = 1, n1 = 1;
    for (int i=2; i<=100; i++) {
        double n2 = n1 + n0;
        System.out.printf("%4d : %e\n", i, n2);
        n0 = n1;
        n1 = n2;
    }

The 49th entry has 12 billion characters (so that's about 24 billion characters overall; or about 48 GB).

The 100th entry (counting from 1) has over 5 x 1020 characters.

You need to rethink your data structure.

Upvotes: 7

Related Questions