Como ler 100000 floats de valor 1000,00 de maneira rápida?

Programação Java
#1

É o seguinte, estou tentando fazer um programa de treinamento para a Maratona de Programação, em java, que possui uma entrada de dados pelo console violenta!

A lógica do exercício é muito simples, o único problema é realmente a entrada dos dados (espero que seja só a entrada!!) que está MUITO lenta, em relação a um programa equivalente em linguagem C ou C++.

O exercício é assim: a entrada possui 2 linhas do console, e a saída 1 linha.

Na 1ª linha, deve ser digitado um inteiro N, que deve estar entre 0 e 100000. Esse N indica o número de peças do exercício.

Na 2ª linha, deve-se digitar N valores int ou float, separados por um espaço cada. Exemplo: 1 2.2 3.3. Os valores podem variar entre 0.00 a 1000.00. Esses valores indicam a medida de cada peça.

Na 3ª linha, se tem a saída do programa, que deve apresentar na tela a QUANTIDADE DE PEÇAS que possuem medida ACIMA DA MÉDIA. (a média das medidas das peças)

O programa só termina de executar quando N for igual a 0.

Exemplo da execução do programa:

3
4 5 6
1
5
1 2 9 8 9
3
0

No primeiro caso de teste, N=3, portanto 3 medidas logo abaixo. A média entre 4,5 e 6 é 5.00, portanto, apenas uma medida ficou acima da média, a medida 6.
No segundo caso de teste, N=5, portanto 5 medidas logo abaixo. A média entre 1,2,9,8 e 9 é 5.80, portanto, 3 medidas ficaram acima da média, 9,8 e 9.
No terceiro caso de teste, N=0, portanto o programa termina.

Esse é o programa que fiz:

import java.util.Locale;
import java.util.Scanner;

/*
	Tive que deixar o nome da classe em minúsculo mesmo, 
	porque é exigido assim o nome do exercício na Maratona de Programação.
*/
public class pecas2 {  
	public static void main(String[] args) {
		
		int   N, qtdAcimaMedia;
		float medidas[], mediaDasMedidas;
		
		//Para poder digitar float com ponto, e não com vírgula.
		Locale.setDefault(Locale.US);
		
		Scanner sc = new Scanner(System.in);
		
		do {
			//Reseta as variáveis
			qtdAcimaMedia = 0;
			mediaDasMedidas = 0.0f;
			
			//Lê o número de peças
			N = sc.nextInt();
			
			//Sai do programa, se o número de peças for zero.
			if(N==0)
				break;
			
			//Instancia um array de floats.
			medidas = new float[N];
			
			//Pega os valores das medidas das peças e já vai somando para tirar a média depois.
			for(int i=0; i<N; i++) {
				medidas[i] = sc.nextFloat();
				mediaDasMedidas += medidas[i];
			}
			//Tira a média.
			mediaDasMedidas /= N;
			
			//Faz a contagem de quantas peças possuem medida acima da média.
			for(int i=0; i<N; i++) {
				if(medidas[i] > mediaDasMedidas)
					qtdAcimaMedia++;
			}
			
			//Apresenta a saída na tela.
			System.out.println(qtdAcimaMedia);
			
		} while(N!=0);
	}
}

Foi feito da maneira mais simples possível, mas não passou no teste do programa usado na Maratona de Programação (BOCA), excede o tempo limite.
Um professor meu deixou um Pentium 4 como servidor, com o BOCA rodando para analisar os códigos, para os alunos poderem submeter os exercícios.
Todos os alunos que fizeram em C ou C++ conseguiram resposta positiva do BOCA. Acho que sou o único que está tentando fazer todos os exercícios em java.

Já tentei modificar meu programa, usando LinkedList, ArrayList, Iterator, InputStreamReader e BufferedReader, mas mesmo assim, excede o tempo limite (que acho que é de 10s).

Alguém poderia tentar me ajudar, antes que eu tenha que descer meu nível, de Java para C?

#2

Nesse tipo de concursos a saída também é importante.
Em vez de fazeres um println para cada ocorrencia do ciclo, usa um stringbuilder e faz um único println no fim.

#3

[EDIT] - post errado

#4

[quote=pmlm]Nesse tipo de concursos a saída também é importante.
Em vez de fazeres um println para cada ocorrencia do ciclo, usa um stringbuilder e faz um único println no fim.[/quote]

Não entendi. A especificação do exercício é essa: 2 linhas de entrada e 1 para saída, nessa ordem. Não posso ir acumulando todos testes para mostrar tudo no final, porque tem que ser nessa ordem, senão o programa BOCA vai me retornar dizendo: Wrong answer.

#5

Opa,

Tenta com essas modificações:

public class Pecas2 {

    public static void main(String[] args) {

        int N, qtdAcimaMedia;
        float medidas[], mediaDasMedidas;

        //Para poder digitar float com ponto, e não com vírgula.  
        Locale.setDefault(Locale.US);

        Scanner sc = new Scanner(System.in);

        do {
            //Reseta as variáveis  
            qtdAcimaMedia = 0;
            mediaDasMedidas = 0.0f;

            //Lê o número de peças  
            N = sc.nextInt();

            //Sai do programa, se o número de peças for zero.  
            if (N == 0) {
                break;
            }
            
            long  tempoInicial = System.currentTimeMillis();

            //Instancia um array de floats.  
            medidas = new float[N];
            
            N--;

            //Pega os valores das medidas das peças e já vai somando para tirar a média depois.  
            for (int i = N; i &gt; -1; i--) {
                mediaDasMedidas += medidas[i] = sc.nextFloat();
            }
            //Tira a média.  
            mediaDasMedidas /= N;

            //Faz a contagem de quantas peças possuem medida acima da média.  
            for (int i = N; i &gt; -1; i--) {
                if (medidas[i] &gt; mediaDasMedidas) {
                    qtdAcimaMedia++;
                }
            }

            //Apresenta a saída na tela.  
            System.out.println(qtdAcimaMedia);
            
            System.out.println(&quot;o metodo executou em &quot; + (System.currentTimeMillis() - tempoInicial)); 

        } while (N != 0);
    }
}

Ali ele mostra o tempo, ai pra mandar pro programa, tira as linhas senão demora pouca coisa a mais…

Aqui abaixo ta as minhas saidas:

Boa sorte

[]'s
Bertan

#6

Tente usar o BufferedReader no lugar do Scanner.

Além disso, pense com carinho se quer seguir adiante com Java. Acho difícil que você consiga bater códigos feitos em C ou C++. Tome cuidado que muitas maratonas contam o código do momento que é dado o “enter” até o momento que o processo encerra e, no caso do Java, isso envolve a inicialização e encerramento da VM. Também cuide pq muitas maratonas tem restrições de memória, que são dificílimas de se cumprir com Java.

#7

[quote=Bertan]Opa,

Tenta com essas modificações:

public class Pecas2 {

    public static void main(String[] args) {

        int N, qtdAcimaMedia;
        float medidas[], mediaDasMedidas;

        //Para poder digitar float com ponto, e não com vírgula.  
        Locale.setDefault(Locale.US);

        Scanner sc = new Scanner(System.in);

        do {
            //Reseta as variáveis  
            qtdAcimaMedia = 0;
            mediaDasMedidas = 0.0f;

            //Lê o número de peças  
            N = sc.nextInt();

            //Sai do programa, se o número de peças for zero.  
            if (N == 0) {
                break;
            }
            
            long  tempoInicial = System.currentTimeMillis();

            //Instancia um array de floats.  
            medidas = new float[N];
            
            N--;

            //Pega os valores das medidas das peças e já vai somando para tirar a média depois.  
            for (int i = N; i &gt; -1; i--) {
                mediaDasMedidas += medidas[i] = sc.nextFloat();
            }
            //Tira a média.  
            mediaDasMedidas /= N;

            //Faz a contagem de quantas peças possuem medida acima da média.  
            for (int i = N; i &gt; -1; i--) {
                if (medidas[i] &gt; mediaDasMedidas) {
                    qtdAcimaMedia++;
                }
            }

            //Apresenta a saída na tela.  
            System.out.println(qtdAcimaMedia);
            
            System.out.println(&quot;o metodo executou em &quot; + (System.currentTimeMillis() - tempoInicial)); 

        } while (N != 0);
    }
}

Ali ele mostra o tempo, ai pra mandar pro programa, tira as linhas senão demora pouca coisa a mais…

Aqui abaixo ta as minhas saidas:

Boa sorte

[]'s
Bertan
[/quote]

Muito obrigado por compartilhar sua solução, mas acho que tem algo errado ai.
Essa parte do código não está executando devidamente, pelo menos não no meu computador.

mediaDasMedidas += medidas[i] = sc.nextFloat();

No exemplo com N=3, e medidas = 4,5,6, a resposta deveria ser 1, e não 0.
(4+5+6)/3 = 5.00, o do seu código está dando 7.00

#8

[quote=ViniGodoy]Tente usar o BufferedReader no lugar do Scanner.

Além disso, pense com carinho se quer seguir adiante com Java. Acho difícil que você consiga bater códigos feitos em C ou C++. Tome cuidado que muitas maratonas contam o código do momento que é dado o “enter” até o momento que o processo encerra e, no caso do Java, isso envolve a inicialização e encerramento da VM. Também cuide pq muitas maratonas tem restrições de memória, que são dificílimas de se cumprir com Java.[/quote]

Como que eu faria para usar o BufferedReader, sem ter que dar um cast depois (algo do tipo Float.parseFloat)? Acho que casts devem atrasar bastante o programa.
Obrigado pelo conselho, o ideal seria eu dominar tanto C, C++ e Java, mas a verdade é que estou aproveitando a maratona como uma forma de querer aprender java, e não pra vencer ela. (embora eu ache sacanagem aceitarem somente essas 3 linguagens, sabendo que C,C++ são mais “rápidos” que java).

#9

E você acha que o Scanner não vai fazer parseFloat?

O problema é que ele ainda trata separadores de linha multiplataforma, através de expressões regulares.
No caso do reader, você realmente vai ler bytes puros, e fazer conversões extritamente necessárias.

#10

Não entendi isso aqui.

E como eu faria "conversões extritamente necessárias", sendo que não manjo muito de Java?
Tenho certeza que alguma coisa assim não é muito esperta:

String s, str[];

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
s = br.readLine();
str = s.trim().split(" ");

for(int i = n; i &gt; 0; i--)
     media += medidas[i] = Float.parseFloat(str[i]);
#11

O Scanner aceita como separadores de linha o \n, o \r\n, etc. Por isso, existe um esforço grande para saber se uma linha terminou.

#12

  1. Durante os testes, você deve fazer a leitura a partir de um arquivo (é como será enviado para seu System.in durante a maratona), caso contrário, você vai estar medindo o tempo que você leva para digitar os números. Apenas na hora de submete-lo, troque novamente para o System.in.

  2. Fiz o programa abaixo. Não é bonito, mas é bem rápido.

[code]import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.util.Locale;

public class pecas2 {
private static boolean quant = true;
private static float medidas[];
private static int lidos;
private static long tempoAntes;;

public static void main(String[] args) throws Exception {
	// Para poder digitar float com ponto, e não com vírgula.
	Locale.setDefault(Locale.US);

	tempoAntes = System.currentTimeMillis();
	BufferedInputStream reader = new BufferedInputStream(new FileInputStream(new File(&quot;c:/temp/entrada.txt&quot;)));
	byte[] buffer = new byte[4096];

	StringBuilder digitos = new StringBuilder();

	while (true) {
		int size = reader.read(buffer);
		for (int i = 0; i &lt; size; i++) {
			if (buffer[i] == ' ') {					
				appendNum(digitos);
			} else if ((buffer[i] == '\n' || buffer[i] == '\r')) {
				if (digitos.length() &gt; 0)
				{
					if (quant) {
						inicializarMedidas(digitos);
					} else {
						appendNum(digitos);
						calcular();
					}
				}
			} else {
				digitos.append((char) buffer[i]);
			}
		}
	}
}

private static void inicializarMedidas(StringBuilder num) {
	int n = Integer.parseInt(num.toString());		
	if (n == 0) 
	{
		System.out.println(&quot;O programa executou em &quot; + (System.currentTimeMillis() - tempoAntes));
		System.exit(0);
	}
	
	medidas = new float[n];
	quant = false;		
	num.delete(0, num.length());
}

private static void calcular() {
	// Cálculo da média
	float media = 0;
	for (float medida : medidas)
		media += medida;
	media /= medidas.length;
	// Vê quantos são acima da média
	int soma = 0;
	for (float medida : medidas)
		if (medida &gt; media)
			soma++;

	// Impressão da soma.
	// Se puder ser em arquivo fica mais rápido pois dá para usar um buffer
	System.out.println(soma);
	// Reseta as variáveis		
	quant = true;
	lidos = 0;
}

private static void appendNum(StringBuilder num) {
	if (num.length() == 0) return;
	
	medidas[lidos++] = Float.parseFloat(num.toString());
	num.delete(0, num.length());
}

}
[/code]

Na minha máquina, o programa todo executou em 557ms. O seu programa (modificado para ler do arquivo), rodou em 2726 ms.
Seu programa modificado:

[code]/*
Tive que deixar o nome da classe em minúsculo mesmo,
porque é exigido assim o nome do exercício na Maratona de Programação.
*/
public class pecas2 {
public static void main(String[] args) throws FileNotFoundException {

	int   N, qtdAcimaMedia;
	float medidas[], mediaDasMedidas;
	
	//Para poder digitar float com ponto, e não com vírgula.
	Locale.setDefault(Locale.US);
	
	Scanner sc = new Scanner(new File("c:/temp/entrada.txt"));
	long tempoAntes = System.currentTimeMillis();
	do {
		//Reseta as variáveis
		qtdAcimaMedia = 0;
		mediaDasMedidas = 0.0f;
		
		//Lê o número de peças
		N = sc.nextInt();
		
		//Sai do programa, se o número de peças for zero.
		if(N==0)
			break;
		
		//Instancia um array de floats.
		medidas = new float[N];
		
		//Pega os valores das medidas das peças e já vai somando para tirar a média depois.
		for(int i=0; i<N; i++) {
			medidas[i] = sc.nextFloat();
			mediaDasMedidas += medidas[i];
		}
		//Tira a média.
		mediaDasMedidas /= N;
		
		//Faz a contagem de quantas peças possuem medida acima da média.
		for(int i=0; i<N; i++) {
			if(medidas[i] > mediaDasMedidas)
				qtdAcimaMedia++;
		}
		
		//Apresenta a saída na tela.
		System.out.println(qtdAcimaMedia);
		
	} while(N!=0);
	System.out.println("O programa executou em " + (System.currentTimeMillis() - tempoAntes));
}

}
[/code]

O arquivo de entrada está em anexo. Coloquei 100.000 entradas.

Observação:
Sem imprimir a saída (que também é uma operação lenta), meu programa roda em 160ms, contra 2.066ms do seu.
Isso demonstra o quão lenta a leitura usando Scanner. Meu programa gasta praticamente todo processamento imprimindo a saída, enquanto o seu, processando a entrada.

#13

PS: Se você está treinando para maratona, o ideal é usar um site onde você possa submeter seu programa, e ele faça o teste igual uma maratona faria.
Dê uma olhada no SPOJ: http://br.spoj.pl

Aí além de validar sua saída, o site também fornecerá uma massa de dados considerável na entrada, prevendo todas as situações de exceção.
Sem falar que nesse site tem um monte de exercícios bem legais. :slight_smile:

#14

Muito obrigado pela sua colaboração ViniGodoy!!!

Eu ia perguntar justamente como utilizar um entrada por arquivo, e que pudesse ser lida em bytes.

Obrigado pela sugestão do SPOJ, depois que eu ficar um pouco mais “acostumado” com java, vou ver se faço alguns exercícios de lá.

Vou ler e entender o código que você postou, e se não tiver problemas para você, vou tentar submeter ele.

Mas percebo que tem algo de estranho na maratona, será que existe requisito mínimo de hardware para uma máquina poder ser “juiz”?
Porque assim, a primeira fase dela é regional (inclusive a faculdade onde estudo já sediou uma vez a fase regional), e foi utilizado (acho) uma máquina local da faculdade como sendo a máquina juiz.

Mas blz, depois vou procurar no site da SBC e ver se acho as regras.
Depois edito o post dizendo se o programa passou ou não.

#15

Não tem problema não. Só lembre-se de alterar novamente a entrada para o System.in.

Geralmente as maratonas descrevem os requisitos máximos que os programas podem ter. Pode ter certeza que se seu processo começar a ocupar vários MB em memória, ele será reprovado.
Se sua faculdade já participa desse tipo de evento, entre em contato com o professor responsável e veja os detalhes.

Outra coisa, aprenda a usar o profiler do Netbeans. Ele te apontará exatamente o local dos gargalos da sua aplicação.

E, claro, se quiser ganhar uma maratona dessas, o ideal é pegar um bom livro de algorítmos e debulhar, como esse aqui:
http://www.submarino.com.br/produto/1/166575/algoritmos:+teoria+e+pratica?franq=314766

#16

Acho que expliquei mal o exercício. O problema não está em quantas vezes o laço principal pode rodar, mas sim na quantidade de entradas que a variável medidas[] pode ter.

Me ensinaram como jogar a saída de um programa direto em um arquivo, então fiz um progra que pudesse gerar um arquivo de teste para o programa do exercício.

import java.util.Locale;

public class Gerador {
	public static void main(String[] args) {
	
		Locale.setDefault(Locale.US);
	
		int n = (int)(Math.random()*100000);
		System.out.println(n);
		for(int i = 0; i < n; i++)
			System.out.printf("%.2f ", (float)(Math.random()*1000.00));
	}
}

Estando no diretório do arquivo .java, executei os comandos pelo prompt:

javac Gerador.java
java Gerador >gerados.out

Depois tentei utilizar esse arquivo como entrada para o programa que o ViniGodoy me fez, mas não sei se coloquei “errado” o diretório para buscar o arquivo gerados.out (será que eu tinha que ter deixado como .txt mesmo?), mas o programa fica “inerte”, não dá erro, apenas fica com o prompt piscando. Dexei ele por um bom tempo até, e nada.

Se alguém puder fazer um teste, só para verificar se o programa é que está demorando muito, ou se eu estou fazendo algo errado.

#17

Vou testar nesse final de semana e ver o que é.

#18

[quote=jasonmalkav]Acho que expliquei mal o exercício. O problema não está em quantas vezes o laço principal pode rodar, mas sim na quantidade de entradas que a variável medidas[] pode ter.

Me ensinaram como jogar a saída de um programa direto em um arquivo, então fiz um progra que pudesse gerar um arquivo de teste para o programa do exercício.

import java.util.Locale;

public class Gerador {
	public static void main(String[] args) {
	
		Locale.setDefault(Locale.US);
	
		int n = (int)(Math.random()*100000);
		System.out.println(n);
		for(int i = 0; i < n; i++)
			System.out.printf("%.2f ", (float)(Math.random()*1000.00));
	}
}

Estando no diretório do arquivo .java, executei os comandos pelo prompt:

javac Gerador.java
java Gerador >gerados.out

Depois tentei utilizar esse arquivo como entrada para o programa que o ViniGodoy me fez, mas não sei se coloquei “errado” o diretório para buscar o arquivo gerados.out (será que eu tinha que ter deixado como .txt mesmo?), mas o programa fica “inerte”, não dá erro, apenas fica com o prompt piscando. Dexei ele por um bom tempo até, e nada.

Se alguém puder fazer um teste, só para verificar se o programa é que está demorando muito, ou se eu estou fazendo algo errado.[/quote]

Bom, normalmente não se usa “java Gerador” e sim “java -classpath . Gerador”

No Linux, além disso, é aconselhável dar um System.out.flush() antes de saír do programa.

#19