What causes the error: stack, heap or the type of data handled?

Question

What causes the error: stack, heap or the type of data handled?

Navigation

#1 by (0 votes)
#2 by (0 votes)

0

I have been asked to calculate the sum of the random integers in an array of 100 million positions, for this I have increased the size of the heap and the stack by executing it with the command "java -Xxs512m -Xss512m lab01" however still After testing up to a stack size of 1024m, this error still occurs:

Exception in thread "main" java.lang.StackOverflowError
    at java.math.BigInteger.<init>(BigInteger.java:606)
    at lab01.array_sum_aux(lab01.java:27)
    at lab01.array_sum_aux(lab01.java:28)
    at lab01.array_sum_aux(lab01.java:28)
    at lab01.array_sum_aux(lab01.java:28)
...
...
...

I'm using the BigInteger class to handle the values, but after trying these memory increases I do not know what else I can do about it ...

This is the code:

import java.util.Random;
import java.math.BigInteger;

/**lab01 class declaration.
*@author: Kevin Gutierrez 
*@version: 18/02/18
*/

public class lab01 {

public static int[] array_generator(int n) {
    int[] arr = new int[n];
    Random ran = new Random();
    for (int i = 0; i < n; ++i) {
        arr[i] = ran.nextInt(10);
    }
    return arr;
}

public static BigInteger array_sum(int[] array) {
  BigInteger sum = new BigInteger("0");
  return array_sum_aux(array, 0, sum);
}

private static BigInteger array_sum_aux(int[] array, int i, BigInteger 
sum)
{
  if (i >= array.length) return sum;
  sum.add(new BigInteger(Integer.toString(array[i])));
  return array_sum_aux(array, i + 1, sum);
}


  public static void main (String args []) {
    int[] arr = array_generator(100000000);
    for (int i = 0; i < arr.length; ++i) {
      System.out.print(arr[i] + ", ");
    }

    System.out.println(array_sum(arr));
  }
}

java stack heap

asked by Kevin Gutierrez 19.02.2018 в 03:58

source

2 answers

Api de mercadopago does not display installment option Request the time in an AlertDialog

score 0 · Answer 1

Keep in mind that if you make 100000000 of recursive calls, it means that all the variables that the function has accumulate. For example, on each call you create a BigInteger that approximately occupies 44B (see link ), that means that your program would need about 4400000000 that approximately is 4.4GB of memory only for BigInteger (it will need much more, for the pointers of the parameters, pointer of the function, etc) and this memory is only released when returning the function .

Think that to analyze the complexity of an algorithm, you do not need to run it but analyze its code.

Another thing is that even if you want to run it for another reason, then you should optimize it trying to avoid creating memory, etc. but it is unlikely that it is what they ask you (since directly the greatest optimization is to make a simple for as comments @ Gbianchi).

score 0 · Answer 2

One way to achieve implement a recursive method beyond the recursive call limit, is to use a concept known in English as "tail recursion".

When deploying it in java, we are effectively avoiding using the call stack and instead managing our own stack.

The resulting code would be like this:

public static BigInteger array_sum(int[] array) {
    BigInteger sum = new BigInteger("0");
    return array_sum_aux(array, 0, sum).getFinalValue();
}

private static Invocation<BigInteger> array_sum_aux(final int[] array, final int i, final BigInteger sum) {
    if (i >= array.length) {
        return new TerminalInvocation<>(sum);
    }

    return new RecursiveInvocation<>(new DeferredInvocation<Invocation<BigInteger>>() {
        @Override
        public Invocation<BigInteger> invoke() {
            return array_sum_aux(array, i + 1, sum.add(new BigInteger(Integer.toString(array[i]))));
        }
    });
}

And the implementation of Invocation, RecursiveInvocation and DeferredInvocation, are available here: link