Limites Computacionais

Aléssio Miranda Júnior

Prática: Limites Computacionais

Este roteiro é projetado para testar e visualizar na prática como o computador e a Máquina Virtual Java (JVM) lidam com limites físicos de memória e de processamento.

Experimento 1: Memory Limit (Estouro de Heap)

  • Quando falta memória para guardar instâncias e objetos, ocorre o Estouro de Memória (Out of Memory - OOM).
  • Em Java, costuma aparecer como java.lang.OutOfMemoryError: Java heap space.

Sua tarefa inicial é tentar alocar uma matriz quadrada cada vez maior no Heap (memória RAM) até que a memória acabe.

O que fazer:

  1. Execute o código a seguir.
  2. O programa tentará alocar matrizes preenchidas com o tipo long (8 bytes por elemento).
  3. Modifique o tamanho da matriz (variável N) e descubra qual é a ordem de grandeza que fará seu ambiente estourar.

Código: Memory Limit

public class ExperimentoMemoryLimit {
    public static void main(String[] args) {
        System.out.println("Iniciando teste de Memory Limit...");
        
        // Cada 'long' na matriz ocupa 8 bytes de memória.
        // Tente alterar o valor de N e observe quando a máquina falha!
        // Valores sugeridos: 10000, 20000, 30000, 50000...
        int N = 10000; 

        try {
            System.out.println("Alocando " + N + " x " + N + "...");
            long[][] matriz = new long[N][N];
            
            long bytes = (long) N * N * 8;
            long megaBytes = bytes / (1024 * 1024);
            System.out.println("Sucesso! Alocado: " + megaBytes + " MB.");
        } catch (OutOfMemoryError e) {
            System.out.println("\nESTOURO DE MEMÓRIA!");
        }
    }
}

Qual a ordem de grandeza?

Marque a alternativa (X) que descreve onde ocorreu o estouro:

Experimento 2: Stack Overflow (Pilha Recursiva)

  • Camadas de chamadas de funções e variáveis locais são empilhadas na Stack (Pilha de Chamadas).
  • Chamadas recursivas excessivas levam ao java.lang.StackOverflowError.

O que fazer:

  1. O código a seguir calcula o fatorial usando recursividade.
  2. Teste inicializando com o número 5.
  3. Altere para um número muito alto (ex: numero = 200000) e verifique o comportamento.

Código: Stack Overflow

public class ExperimentoStackOverflow {
    public static long fatorial(long n, int prof) {
        if (prof % 1000 == 0) System.out.println("Stack: " + prof);
        if (n <= 1) return 1;
        
        return n * fatorial(n - 1, prof + 1);
    }

    public static void main(String[] args) {
        long numero = 150000; 
        try {
            System.out.println("Resultado: " + fatorial(numero, 1));
        } catch (StackOverflowError e) {
            System.err.println("\nESTOURO DA PILHA DE CHAMADAS!");
        }
    }
}

Reflexão sobre a Stack

  • Em qual profundidade o seu programa travou?
  • Como contornar isso com o que estudamos até então? (Pense em laços iterativos for/while ao invés de recursão)

Experimento 3: Time Limit (Limite de Tempo)

Presencie na prática a diferença de lidar com processamento real entre Complexidades Assintóticas:

  • \(O(n^2)\) com Bubble Sort
  • \(O(n \log n)\) com a ordenação nativa do Java (Dual-Pivot Quicksort)

O que fazer:

  1. O programa gera um grande vetor de tamanho N com números aleatórios.
  2. Usamos System.currentTimeMillis() para verificar o tempo gasto pelo Bubble Sort e pelo Arrays.sort().

Código: Time Limit (Parte 1)

import java.util.Arrays;
import java.util.Random;

public class ExperimentoTimeLimit {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

Código: Time Limit (Parte 2)

    public static void main(String[] args) {
        int N = 50000; 
        int[] arrB = new int[N];
        int[] arrQ = new int[N];
        Random rand = new Random();
        
        for (int i = 0; i < N; i++) {
            arrB[i] = rand.nextInt(N);
            arrQ[i] = arrB[i];
        }

        long t1 = System.currentTimeMillis();
        bubbleSort(arrB);
        System.out.println("Bubble: " + (System.currentTimeMillis() - t1) + "ms");

        long t2 = System.currentTimeMillis();
        Arrays.sort(arrQ);
        System.out.println("Quick: " + (System.currentTimeMillis() - t2) + "ms");
    }
}

Tarefa de Análise de Tempo

Execute o código variando o tamanho de N (25000, 50000, 100000).

  • O que acontece com o Bubble Sort cada vez que dobramos N? Quantas vezes o tempo aumenta?
  • Compare a curva de tempo gasta pela classe nativa do Java com a complexidade \(N^2\).