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;
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.
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.
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.
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.
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 ?!
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.
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.
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.
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.
Eu falei da referência, não do objeto
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.
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.
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).
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.
Empolguei aqui…
Parece que, no final, o crime não compensa
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).
