Discussoes de Programacao e Tecnologia

Geração de Números Aleatórios Muito Grande

18 respostas
javaprogramação
G
Gabriel_Brandao

Estou gerando uma matriz muito grande de números aleatórios, a matriz tem o tamanho de 20.000X20.000 (400 Milhões de posições) como a matriz é muito grande precisei aumentar o tamanho da heap da JVM (para evitar o erro Exception in thread “main” java.lang.OutOfMemoryError: Java heap space) compilando usando o seguinte comando:
java -jar -Xms0m -Xmx4G Teste.jar

Até aí ok, quando eu uso o range de números aleatórios de 0 à 10, o programa executa tranquilo, mas quando eu aumento o range para 0 à 100.000.000 eu recebo o erro Java heap espace novamente.

Gostaria de entender o porque isso acontece, já que o tamanho de um inteiro é sempre 4bytes, independente de que valor seja esse inteiro, não é ?? Logo não deveria faltar espaço para a JVM apenas porque aumentei o range dos números aleatórios mesmo mantendo o tamanho da matriz.

Segue o código:
Teste.java:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package teste;

import java.util.ArrayList;
import java.util.Random;

public class Teste {
    
    public static int TAM = 20000;
    private static final int rangeNumerosAleatorios = 100000000;//11;
    public static ArrayList<ArrayList<Integer>> matrizDeNumeros;

    public static void main(String[] args) {

        System.out.println(Thread.currentThread().getName());
        preencherMatriz();
        System.out.println("Matriz preenchida");
        //imprimirMatriz();
    }
    
    
    public static void preencherMatriz() {
        Random numero = new Random(2); // inicia semente para sempre gerar a mesma matriz
        ArrayList<Integer> linha;

        matrizDeNumeros = new ArrayList<ArrayList<Integer>>(TAM);
        for (int i = 0; i < TAM; i++) {
            linha = new ArrayList<Integer>();

            for (int j = 0; j < TAM; j++)
                linha.add(numero.nextInt(rangeNumerosAleatorios));

            matrizDeNumeros.add(linha); // adiciona uma linha a cada posição, formando uma matriz
        }
    }
    
    public static void imprimirMatriz() {
        for (int i = 0; i < matrizDeNumeros.size(); i++) {
            for (int j = 0; j < matrizDeNumeros.get(i).size(); j++)
                System.out.print(matrizDeNumeros.get(i).get(j) + " ");

            System.out.println("");
        }
    }
}

Saída quando executo com TAM = 20000 e rangeNumerosAleatorios = 100000000;

imagem_2022-05-14_150916305
imagem_2022-05-14_150916305771×173 6.17 KB

Alura Desenvolvimento Back-End Java Sua Carreira em desenvolvimento back-end Java: dos fundamentos à arquitetura de sistemas...

18 Respostas

H
hugokotsubo

O problema, acredito eu, é que vc está usando Integer e não int.

Um int ocupa 4 bytes, mas um Integer não.

O que pode estar acontecendo é que esta classe possui um cache interno para valores pequenos. Então para valores até 10 ele usa as instâncias do cache (na prática, são poucas instâncias sendo reaproveitadas, daí consome menos memória).

Para valores maiores, como não estão no cache, ele acaba criando novas instâncias, consumindo mais memória.

G
Gabriel_Brandao

como eu resolveria isso, usando ainda um ArrayList de Integer ??

S
staroski

Isso não é uma matriz, é uma lista de listas.

No seu caso a implementação dessa lista está na classe ArrayList que, internamente, utiliza um array para armazenar seus elementos.
Quando esse array é preenchido, o ArrayList vai alocar um novo array 50% maior e copiar o conteúdo do array antigo para o novo.
Provavelmente é nesse momento que a memória está acabando.

Já que você tem um número fixo de elementos, utilize uma matriz bidimensional ao invés de uma lista de listas.

H
hugokotsubo

Não use Integer, tente com um array de int.

Infelizmente não dá pra usar listas pra isso.

W
wldomiciano

Gostei da sua pergunta porque tem todas as informações.

Eu testei com o seu código e só rodou com sucesso depois que eu mudei -Xmx4G para -Xmx8G.

É possível aumentar o cache de Integer passando o argumento -Djava.lang.Integer.IntegerCache.high=1405238 para o comando java, mas 1405238 foi o máximo que consegui aumentar sem dar erro.

java -jar -Djava.lang.Integer.IntegerCache.high=1405238 -Xms0m -Xmx4G Teste.jar

Então eu pensei numa solução que parece funcionar. Eu criei meu próprio cache, ficou assim:

import java.util.ArrayList;
import java.util.Random;

public class Teste {
  private static final int TAM = 20000;

  private static final int rangeNumerosAleatorios = 100000000;

  private static final ArrayList<ArrayList<Integer>> matrizDeNumeros = new ArrayList<>(TAM);

  private static final Integer[] cache = new Integer[rangeNumerosAleatorios];

  public static void main(String... args) {
    System.out.println(Thread.currentThread().getName());

    initializeCache();
    preencherMatriz();

    System.out.println("Matriz preenchida");
  }

  private static void initializeCache() {
    for (int i = 0; i < rangeNumerosAleatorios; i++) {
      cache[i] = Integer.valueOf(i);
    }
  }

  private static void preencherMatriz() {
    Random numero = new Random(2);

    for (int i = 0; i < TAM; i++) {
      ArrayList<Integer> list = new ArrayList<>(TAM);

      for (int j = 0; j < TAM; j++) {
        list.add(cache[numero.nextInt(rangeNumerosAleatorios)]);
      }

      matrizDeNumeros.add(list);
    }
  }
}

Execute com:

java -jar -Xms0m -Xmx4G Teste.jar

Mas é muito melhor vc fazer com arrays comuns como já foi sugerido.

J
JGus

A explicação pro caso e como mudar o padrão.

G
Gabriel_Brandao

A questão é que aqui não está o código inteiro, estou implementando um programa que irá dividir a “matriz” em outras submatrizes e cada uma ficará com uma thread que por sua vez fará a busca por números primos e conta-los, além disso o usuário poderá escolher o tamanho dessa matriz, e o jeito mais fácil de implementar uma matriz dinâmica foi dessa forma, aqui no exemplo eu coloquei TAM = 20000; porém esse valor pode ser qualquer um que o usuário quiser. Portanto eu não sei se seria vantajoso eu trocar por uma matriz de int, o que você acha ?!

G
Gabriel_Brandao

isso deixaria meu código mais pesado ?

W
wldomiciano

A princípio parece que fica mais leve, na verdade.

Em termos de espaço, minha sugestão roda dentro dos 4 gigas de RAM que vc delimitou.

E em termos de processamento também é melhor porque sem o cache que eu criei, a JVM gerava um número aleatório e criava um Integer a partir dele, agora ela só precisa gerar o número e pegar o Integer correspondend que já está criado no cache.

Nas listas poderão existir vários Integer repetidos, o cache resolve isso também já que reaproveita as instâncias do cache.

Mas eu gostaria de saber o opinião dos colegas sobre isso, parece bom demais pra ser verdade, acho que estou deixando passar alguma coisa.

H
hugokotsubo

Você pode criar uma matriz com o tamanho que o usuário escolher:

Random random = new Random();
 
int tamanho = ... // usuário escolhe o tamanho 
int[][] matriz = new int[tamanho][tamanho];
for (int i = 0; i < tamanho; i++)
    for (int j = 0; j < tamanho; j++)
        matriz[i][j] = random.nextInt(100000000);

Não testei com a matriz gigante, mas acredito que deva gastar menos memória que uma lista de Integer.

D
davidbuzatto

Quanto ao tipo, uma referência a um Integer ocupa 64bits em arquiteturas 64bits, o que é basicamente o padrão hoje em dia, enquanto um int ocupa 32bits. Sendo assim, mesmo com o reaproveitamento dos objetos, só as referências aos objetos Integer já ocupam o dobro dos inteiros normais… Se dá para usar int, use int.

W
wldomiciano 1 like

Então, David, eu concordo com vc sobre usar int e até comentei isso na minha primeira resposta.

Mas eu comentei que parece que fica mais leve em comparação com o código que o Gabriel apresentou inicialmente e levando em conta as restrições propostas (usar ArrayList e máximo de 4GB de RAM). Deste ponto de vista, vc acha que minha solução faz sentido?

Outra coisa: Achei curioso o que vc comentou sobre o Integer ocupar 64 bits e fui procurar mais um pouco sobre isso.

Na minha pesquisa descobri que o Integer, na verdade, ocupa 16 bytes (128 bits). São 12 bytes só de header.

Já em computadores de 64 bits com um -Xmx grande tipo 64G o Integer ocupa 24 bytes. São 16 bytes de header e mais 1 byte de padding para completar o multiplo de 8.

Só que isso é na Hotspot, pois como a especificação não estipula como os objetos devem ser representados em memória, outras implementações poderiam usar tecnicas diferentes.

Achei bem interessante. Eu fiz os testes usando esta ferramenta do OpenJDK:
https://github.com/openjdk/jol

E seguindo este artigo (O link vai direto para a seção que fala do Integer):
https://shipilev.net/jvm/objects-inside-out/#_observation_compressed_references_affect_object_header_footprint

G
Gabriel_Brandao 1 like

Interessant, eu tava buscando mesmo essa informação

D
davidbuzatto

Eu falei da referência, não do objeto :wink:
Hoje em dia na vdd, dei mais uma pesquisada, as implementações de 64bits usam um algoritmo de compressão para as referências serem de 32bits. De novo, as referências à objetos, não os objetos em si.

W
wldomiciano

Ai, verdade, me perdoe, eu interpretei errado.

Sim, verdade, achei isto também! E descomprime se vc executar com -Xmx32G ou -XX:-UseCompressedOops (ou conforme necessário, imagino eu), deu pra ver por aquela ferramenta que citei.

H
hugokotsubo 1 like

Vc só quer a contagem dos números primos (ou seja, apenas a quantidade)?

Pergunto porque se for isso, talvez não precise criar uma matriz gigante com tudo. Por exemplo, e se cada thread recebesse o Random e a quantidade de números a serem verificados, e ela mesma gerasse os números?

Claro, é só uma ideia sem ter todo o contexto, é que não sei se realmente precisaria gerar todos os números de uma vez e mantê-los todos na memória durante todo o processo.

Sem contar que haverá muita repetição. Se a matriz tem 400 milhões de números e vc está usando um range de 0 a 100 milhões, muitos números se repetirão e haverá muita redundância, com várias threads verificando novamente os mesmos números (mas aí já seria uma otimização do algoritmo, de qualquer forma é outro detalhe para se pensar).

D
davidbuzatto 1 like

Uma abordagem single-thread seria:

  • Calcular os números primos de 0 a 100 milhões;
  • Armazená-los num conjunto implementado usando uma árvore de busca balanceada;
  • Calcular 400 milhões de números aleatórios e, para cada um, verificar a pertinência no conjunto. Se estiver contido, incrementa o contador.

Algo assim:

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

/**
 *
 * @author Prof. Dr. David Buzatto
 */
public class ContaPrimosAleatorios {
    
    // Crivo de Eratóstenes
    public static Set<Integer> primos( int max ) {
        
        Set<Integer> primos = new TreeSet<>();
        
        boolean[] crivo = new boolean[max + 3]; // 0, 1 e max
        int limite = (int) Math.sqrt( max );
        
        for ( int i = 2; i <= limite; i++ ) {
            if ( !crivo[i] ) {
                int c = 2;
                while ( i * c <= max ) {
                    crivo[i*c++] = true;
                }
            }
        }
        
        for ( int i = 2; i <= max; i++ ) {
            if ( !crivo[i] ) {
                primos.add( i );
            }
        }
        
        return primos;
        
    }
    
    public static void main( String[] args ) {
        
        long antes = 0;
        long depois = 0;
        int maxPrimos = 100000000;
        int maxGeracao = 400000000;
        int contador = 0;
        
        Random gerador = new Random( 2 );
        
        antes = System.currentTimeMillis();
        Set<Integer> primos = primos( maxPrimos );
        depois = System.currentTimeMillis();
        System.out.printf( 
                "Conjunto de primos no intervalo [0, %d] gerados em %.4f segundos.\n", 
                maxPrimos, ( depois - antes ) / 1000.0 );
        
        antes = System.currentTimeMillis();
        for ( int i = 0; i < maxGeracao; i++ ) {
            int n = gerador.nextInt( maxPrimos );
            if ( primos.contains( n ) ) {
                contador++;
            }
        }
        depois = System.currentTimeMillis();
        
        System.out.printf( 
                "%d primos gerados aleatoriamente em %.4f segundos.\n",
                contador, ( depois - antes ) / 1000.0 );
        
    }
    
}

Na minha máquina o resultado foi esse aqui:

Conjunto de primos no intervalo [0, 100000000] gerados em 1,8760 segundos.
23043038 primos gerados aleatoriamente em 236,9550 segundos.

Usando a mesma semente o resultado tem que ser o mesmo na contagem. O tempo vai variar, é claro.

D
davidbuzatto 2 likes

Empolguei aqui…
Parece que, no final, o crime não compensa :rofl:
Precisa dar uma melhorada no código, mas pra testar está bom.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
 *
 * @author Prof. Dr. David Buzatto
 */
public class ContaPrimosAleatorios {
    
    // Crivo de Eratóstenes
    public static Set<Integer> primos( int max ) {
        
        Set<Integer> primos = new TreeSet<>();
        
        boolean[] crivo = new boolean[max + 3]; // 0, 1 e max
        int limite = (int) Math.sqrt( max );
        
        for ( int i = 2; i <= limite; i++ ) {
            if ( !crivo[i] ) {
                int c = 2;
                while ( i * c <= max ) {
                    crivo[i*c++] = true;
                }
            }
        }
        
        for ( int i = 2; i <= max; i++ ) {
            if ( !crivo[i] ) {
                primos.add( i );
            }
        }
        
        return primos;
        
    }
    
    private static Set<Integer> primos;
    private static Random gerador;
    
    public static void main( String[] args ) throws Exception {
        
        long antes = 0;
        long depois = 0;
        int maxPrimos = 100000000;
        //int maxGeracao = 400000000;
        int maxGeracao = 10000000;
        
        antes = System.currentTimeMillis();
        primos = Collections.synchronizedSet( primos( maxPrimos ) );
        depois = System.currentTimeMillis();
        System.out.printf( 
                "Conjunto de primos no intervalo [0, %d] gerado em %.4f segundos.\n", 
                maxPrimos, ( depois - antes ) / 1000.0 );
        
        // criando um novo gerador com a mesma semente pra cada processamento,
        // garantindo assim a mesma contagem de primos
        gerador = new Random( 2 );
        singleThread( maxGeracao, maxPrimos );
        
        for ( int i = 1; i <= 10; i++ ) {
            gerador = new Random( 2 );
            multiThread( i, maxGeracao, maxPrimos );
        }
        
    }
    
    private static void singleThread( int maxGeracao, int maxPrimos ) {
        
        long antes = 0;
        long depois = 0;
        int contador = 0;
        
        antes = System.currentTimeMillis();
        for ( int i = 0; i < maxGeracao; i++ ) {
            if ( primos.contains( gerador.nextInt( maxPrimos ) ) ) {
                contador++;
            }
        }
        depois = System.currentTimeMillis();
        
        System.out.printf( 
                "%d primos gerados aleatoriamente em %.4f segundos.\n",
                contador, ( depois - antes ) / 1000.0 );
        
    }
    
    private static void multiThread( 
            int numThreads, int maxGeracao, int maxPrimos ) 
            throws InterruptedException, ExecutionException {
        
        long antes = 0;
        long depois = 0;
        int contador = 0;
        
        antes = System.currentTimeMillis();
        ExecutorService es = Executors.newFixedThreadPool( numThreads );
        List<ContadorDePrimos> tarefas = new ArrayList<>();
        for ( int i = 0; i < numThreads; i++ ) {
            tarefas.add( new ContadorDePrimos( 
                    maxPrimos, maxGeracao / numThreads ) );
        }
        List<Future<Integer>> resultados = es.invokeAll( tarefas );
        for ( Future<Integer> r : resultados ) {
            contador += r.get();
        }
        es.shutdown();
        depois = System.currentTimeMillis();
        
        System.out.printf( 
                "%d primos gerados aleatoriamente em %.4f segundos usando %d thread(s).\n",
                contador, ( depois - antes ) / 1000.0, numThreads );
        
    }
    
    private static class ContadorDePrimos implements Callable<Integer> {

        int maxPrimos;
        int maxGeracao;
        
        ContadorDePrimos( int maxPrimos, int maxGeracao ) {
            this.maxPrimos = maxPrimos;
            this.maxGeracao = maxGeracao;
        }
        
        @Override
        public Integer call() throws Exception {
            
            int contador = 0;
            
            for ( int i = 0; i < maxGeracao; i++ ) {
                if ( primos.contains( gerador.nextInt( maxPrimos ) ) ) {
                    contador++;
                }
            }
            
            return contador;
            
        }
        
    }
    
}

Conjunto de primos no intervalo [0, 100000000] gerado em 1,9840 segundos.
577024 primos gerados aleatoriamente em 6,5590 segundos.
577024 primos gerados aleatoriamente em 6,6110 segundos usando 1 thread(s).
577024 primos gerados aleatoriamente em 8,3490 segundos usando 2 thread(s).
577024 primos gerados aleatoriamente em 9,8760 segundos usando 3 thread(s).
577024 primos gerados aleatoriamente em 10,0480 segundos usando 4 thread(s).
577024 primos gerados aleatoriamente em 9,2710 segundos usando 5 thread(s).
577024 primos gerados aleatoriamente em 9,0170 segundos usando 6 thread(s).
577024 primos gerados aleatoriamente em 9,1350 segundos usando 7 thread(s).
577024 primos gerados aleatoriamente em 8,6150 segundos usando 8 thread(s).
577024 primos gerados aleatoriamente em 7,9760 segundos usando 9 thread(s).
577024 primos gerados aleatoriamente em 8,0510 segundos usando 10 thread(s).
Criado 14 de maio de 2022
Ultima resposta 17 de mai. de 2022
Respostas 18
Participantes 6

Topicos relacionados

Labirinto em Java 1 respostas Duvida Scanner com JOptionPane Resolvido 3 respostas Sobre carreira Resolvido 1 respostas Fiz esse CAÇA-PALAVRAS e preciso fazer com que a pessoa não possa digitar números e nem caracteres especiais. Caso digitar, exibir um aviso. Alguém consegue me ajudar? Resolvido 1 respostas Como salvar dados em duas tabelas em uma mesma tela. (JAVA) Resolvido 6 respostas
Alura Git Flow: entenda o que é, como e quando utilizar Entenda o que é Git Flow, como funciona seu fluxo com branches como Master, Develop, Feature, Release e Hotfix, além de vantagens e desvantagens.
Casa do Codigo Apache Kafka e Spring Boot: Comunicacao assincrona entre... Por Eduardo Felipe Zambom Santana — Casa do Codigo