0

Se me ha pedido calcular la sumatoria de los enteros aleatorios en un arreglo de 100 millones de de posiciones, para esto he aumentado el tamaño del heap y el stack ejecutandolo con el comando "java -Xxs512m -Xss512m lab01" sin embargo aún despues de haber probado hasta con un tamaño de stack de 1024m aún sale este error:

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)
...
...
...

Para el manejo de los valores estoy usando la clase BigInteger, pero después de probar con estos aumentos de memoria ya no sé que más pueda hacer al respecto...

Este es el codigo:

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));
  }
}
3
  • tu problema es que estas llamando recursivamente a la funcion.. porque estas haciendo eso? si con un for alcanza?
    – gbianchi
    Commented el 19 feb. 2018 a las 3:22
  • En el trabajo me piden que debe ser recursivo para analizar su complejidad Commented el 19 feb. 2018 a las 3:58
  • analizar la complejidad de una suma de un array? pero la complejidad es la misma que con un for. Las llamadas recursivas se usan para otras cosas, no para sumar numeros sin mas...
    – gbianchi
    Commented el 19 feb. 2018 a las 4:06

2 respuestas 2

0

Ten en cuenta que si haces 100000000 de llamadas recursivas, significa que todas las variables que tenga la función se van acumulando. Por ejemplo, en cada llamada creas un BigInteger que aproximadamente ocupa 44B (mira https://stackoverflow.com/questions/15301249/how-much-space-does-biginteger-use), eso significa que tu programa necesitaría unos 4400000000 que aproximadamente es 4,4GB de memoria solo para BigInteger (necesitará mucha más, para los punteros de los parámetros, puntero de la función, etc) y esta memoria solo se libera al retornar la función.

Piensa que para analizar la complejidad de un algoritmo, no necesitas ejecutarlo sino analizar su código.

Otra cosa es que aún así quieras ejecutarlo por otra razón, entonces tendrías que optimizarlo intentando evitar la creación de memoria, etc. pero es improbable que sea lo que te pidan (ya que directamente la mayor optimización es hacer un simple for como comenta @gbianchi).

0

Una forma de lograr implementar una metodo recursivo mas alla del limite de llamadas recursivas, es haciendo uso de un concepto conocido en ingles como "tail recursion".

Al implementarlo en java, efectivamente estamos evitando usar el stack de llamadas y en cambio manejamos un stack propio.

El codigo resultante seria asi:

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

Y la implementacion de Invocation, RecursiveInvocation y DeferredInvocation, estan disponibles aqui: https://bitbucket.org/klaimmore/pruebas-maven/raw/e5317fe2cb7b68074704ee719e753b2f293c9c8a/src/main/java/klaimmore/pruebasmaven/recursion/Invocation.java

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.