Leitura e Escrita Rápida (C vs C++ vs Java)

Versão TL:DR

• Se usarem Java e o problema exigir muito input, leiam antes com o FastScanner (essencialmente é só criar com FastScanner em vez de Scanner e tudo o resto é igual)
• Se usarem Java e o problema exigir muito output, escrevam antes com o FastPrint (essencialmente é só escrever com FastPrint.out.print em vez de System.out.print, não esquecer de no final fazer FastPrint.out.close() e tudo o resto é igual)
• Se usarem C++ e cin/cout, não será preciso para DAA, mas podem ler mais rápido se desligarem a sincronização (acrescentar std::ios_base::sync_with_stdio(false)) e podem escrever mais rápido se evitarem usar std::endl (usar antes um "\n")

Sobre a leitura

No Java, devido a vários motivos (como por exemplo o tamanho do seu buffer, ou facto de fazer o parsing do input) a classe Scanner é bastante mais lenta que um scanf do C.

Na maior parte dos problemas colocados em DAA isto não afeta a capacidade de ter Accepted em Java, mas nos casos onde o input é muito grande pode fazer um pouco de diferença, pois o tempo limite de execução no Mooshak tem de ser o mesmo para C, C++ e Java e a margem para separar diferentes classes de complexidade com tempos pequenos é muito curta (1s ou 2s de tempo limite são normalmente usado para que possa ter respostas rápidas ao submeter).

Assim, se o input for já na ordem das dezenas de milhar (use como regra base ser mais do que 50 mil números), aconselhamos fortemente que use um método melhor que o Scanner, nomeadamente um BufferedReader.

Para lhe facilitar a vida, disponibilizamos uma classe chamada FastScanner. Para usar basta:

• Fazer download do ficheiro FastScanner.java e colocá-lo no mesmo diretório do código que quer compilar.
• No seu programa basta substituir as occorrências de Scanner por FastScanner.
  Por exemplo, uma possível inicialização seria FastScanner in = new FastScanner(System.in), e depois poderia chamar in.nextInt(), in.nextLine(), etc.
• Não precisa de colocar a classe FastScanner no ficheiro a submeter, pois o Mooshak já a tem disponível.

De seguida apresentamos um pequeno exemplo de utilização e o ganho de eficiência (mostrando também uma melhoria no uso do cin no C++, que não é estritamente necessária para DAA, mas torna o seu código mais comparável com o uso do scanf).

#include <stdio.h>

#define N 10000000
int v[N];

int main() {
  for (int i=0; i<N; i++)
    scanf("%d", &v[i]);
  
  return 0;
}

#include <iostream>

#define N 10000000
int v[N];

int main() {    
  for (int i=0; i<N; i++)
    std::cin >> v[i];
  
  return 0;
}

import java.util.Scanner;

class read_slow {
    static final int N = 10000000;
    static int[] v = new int[N];
    
    public static void main(String[] args) {
	Scanner in = new Scanner(System.in);

	for (int i=0; i<N; i++)
	    v[i] = in.nextInt();	    
    }
}

#include <stdio.h>

#define N 10000000
int v[N];

int main() {
  for (int i=0; i<N; i++)
    scanf("%d", &v[i]);
  
  return 0;
}

#include <iostream>

#define N 10000000
int v[N];

int main() {
  std::ios_base::sync_with_stdio(false);
  
  for (int i=0; i<N; i++)
    std::cin >> v[i];
  
  return 0;
}

class read_fast {
    static final int N = 10000000;
    static int[] v = new int[N];
    
    public static void main(String[] args) {
	FastScanner in = new FastScanner(System.in);

	for (int i=0; i<N; i++)
	    v[i] = in.nextInt();	    
    }
}

Sobre a escrita

No Java, devido a vários motivos (como por exemplo o tamanho do seu buffer, escrevendo sempre que se muda de linha) a escrita diretamente com o PrintStream é bastante mais lenta que um printf do C.

Na maior parte dos problemas colocados em DAA isto não afeta a capacidade de ter Accepted em Java, mas nos casos onde o output é muito grande pode fazer um pouco de diferença, pois o tempo limite de execução no Mooshak tem de ser o mesmo para C, C++ e Java e a margem para separar diferentes classes de complexidade com tempos pequenos é muito curta (1s ou 2s de tempo limite são normalmente usado para que possa ter respostas rápidas ao submeter).

Assim, se o output for já na ordem das dezenas de milhar (use como regra base ser mais do que 50 mil números), aconselhamos fortemente que use um método melhor, nomeadamente um BufferedOutputStream.

Para lhe facilitar a vida, disponibilizamos uma classe chamada FastPrint. Para usar basta:

• Fazer download do ficheiro FastPrint.java e colocá-lo no mesmo diretório do código que quer compilar.
• No seu programa basta substituir as occorrências de System.out por FastPrint.out.
  Por exemplo, imprimir um inteiro n seria FastPrint.out.println(n), etc.
• Antes de terminar o programa deve chamar FastPrint.out.close();, para garantir que todo o conteúdo do buffer de escrita é enviado para o output.
• Não precisa de colocar a classe FastPrint no ficheiro a submeter, pois o Mooshak já a tem disponível.

De seguida apresentamos um pequeno exemplo de utilização e o ganho de eficiência (mostrando também uma melhoria no uso do cout no C++, que não é estritamente necessária para DAA, mas torna o seu código mais comparável com o uso do print - basta não usar o std::endl, que força o flush e impede uma escrita com buffer).

#include <stdio.h>

#define N 10000000

int main(int argc, char **argv) {
  for (int i=0; i<N; i++)
    printf("%d\n", i);
  
  return 0;
}

#include <iostream>

#define N 10000000

int main(int argc, char **argv) {
  for (int i=0; i<N; i++)
    std::cout << i << std::endl;
  
  return 0;
}

class print_slow {
    final static int N = 10000000;
    
    public static void main(String[] args) {
	for (int i=0; i<N; i++)
	    System.out.println(i);
    }
}

#include <stdio.h>

#define N 10000000

int main(int argc, char **argv) {
  for (int i=0; i<N; i++)
    printf("%d\n", i);
  
  return 0;
}

#include <iostream>

#define N 10000000

int main(int argc, char **argv) {
  std::ios_base::sync_with_stdio(false);
  
  for (int i=0; i<N; i++)
    std::cout << i << "\n";
  
  return 0;
}

class print_fast {
    final static int N = 10000000;
    
    public static void main(String[] args) {
	for (int i=0; i<N; i++)
	    FastPrint.out.println(i);
	FastPrint.out.close(); // Nao esquecer
    }
}

Saber mais

A máquina onde está instalado o Mooshak de DAA é substancialmente mais lenta que o meu portátil (mas as restrições dos problemas e os tempos limite têm isso em conta, sendo que todos os problemas são resolúveis nas 3 linguagens permitidas).

Se quiser saber mais sobre a parte de input/output pode pesquisar no google, falar com o regente ou espreitar por exemplo as seguintes ligações:

• Fast I/O for Competitive Programming (GeeksforGeeks)
• Fast I/O in Java in Competitive Programming (GeeksforGeeks)
• Significance of ios_base::sync_with_stdio(false); cin.tie(NULL); (StackOverflow)

Pedro Ribeiro (DCC/FCUP) / Última actualização: