Java - OutOfMemoryError : Java heap space

Question

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.

Could you increase the heap size? That might work for you. In theory, you could only store the addition, and have it dynamically generate each string on the fly. But then you're trading less memory usage for for CPU. Also, if you know the total size (which you do, and for the Strings, you can calculate), then why not use a normal array? They will be far more efficient than an ArrayList. You could generate that array in your method and then return it maybe — cocomac
– cocomac, Commented May 18, 2022 at 2:29
The length of your elements will be part of a Fibonacci series. If the length of the first two elements are zero and one, then the length of element 100 will be 354,224,848,179,261,915,075. Good luck getting to 100,00 elements! — skomisa
– skomisa, Commented May 18, 2022 at 2:54
What kind of nonsense is closed "not reproducible or caused by typos"? It's eminently reproducible. There is a minor typo ('n' should be 'numStrings') but that is a transcription error. The question is a good one, and the answer is a good lesson to the naive programmer. — dangling else
– dangling else, Commented May 18, 2022 at 3:06
@user229044 - "what not to do" is surely useful for future readers. — dangling else
– dangling else, Commented May 18, 2022 at 3:08
@skomisa - I agree: the lack of the slightest effort to provide a valid close reason shows lack of concern for the OP. — dangling else
– dangling else, Commented May 18, 2022 at 3:18

dangling else · Accepted Answer · 2022-05-18 02:59:40Z

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

Thus the length of the N^th 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 N^th 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 10²⁰ characters.

You need to rethink your data structure.

Collectives™ on Stack Overflow

Java - OutOfMemoryError : Java heap space

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related