Olá!

scanf

A primeira linguagem de programação que eu aprendi foi C. Depois do clássico Hello, world!, exemplo obrigatório em qualquer livro de C, aprendi variáveis. E com elas veio o scanf.

O scanf é, usualmente, o primeiro comando que aprendemos para dar um valor para uma variável em tempo de execução:

1
2
3

  int x;
  scanf("%d", &x);
  printf("%d\n", x * x);

O programa acima lê um número inteiro da entrada padrão, usualmente uma janela de terminal (ou o programa cmd no windows, aquela janela preta "feia") e imprime o número ao quadrado.

Agora, deixe o scanf guardado na memória, já vamos brincar com ele.

cin

Depois, eu resolvi aprender C++, já que a biblioteca padrão tem muitas coisas úteis para fazer os problemas da maratona de programação.

Em C++, é usual usarmos outra maneira de ler o valor para uma variável, usando streams:

1
2
3

  int x;
  cin >> x;
  cout << x * x << endl;

Que faz exatamente a mesma coisa: lê um inteiro e imprime o dito cujo ao quadrado. Agora, além de pensar que é bem mais fácil o "jeito C++", também guarde essa nova mágica.

getchar

Um outro jeito de ler da tela é a função getchar. O único problema é que ela não lê nada além de caracteres.

1
2

  char x;
  x = getchar();

Essas duas linhas lêem na variável x um caracter. Ou seja, desde uma letra, como um sinal de pontuação, até um número (que não pode ser tratado como um número, já que ele é a "letra" que representa o número).

getchar_unlocked

Em uma aula, há quase um mês atrás, um aluno me contou da existência do getchar_unlocked, a versão do getchar que não se deve usar, já que ela não é thread safe, pois não contrói um input stream. Ou seja, nós não devemos usar o getchar_unlocked em aplicações reais.

A maratona não é real!

Já a maratona de programação (sendo a OBI o análogo para o colégio), não é real! É um ambiente controlado onde o usuário nunca é um usuário de verdade e só coloca os dados esperados, e os programas não têm várias threads. Logo, nós podemos usar as funções perigosas, como o getchar_unlocked!

Lendo inteiros com o getchar e o com o getchar_unlocked

Antes de continuar, vamos ver como fazemos para, só lendo caracteres, transformar os caracteres em um número.

Para isso, vamos fazer uma função chamada input, que só usa getchar (usar o getchar_unlocked é idêntico, só precisamos mudar o nome).

1
2
3
4
5
6
7
8
9
10
11
12

inline void inp(int &n) {
    n = 0;
    int ch = getchar();
    int sign = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        n = (n<<3) + (n<<1) + ch - '0', ch = getchar();
    n *= sign;
}

O que nós fazemos nessa função? Vejamos por partes:

Na linha 2, inicializamos nosso inteiro com 0, já que vamos somar os números convertidos de sua forma "letral" em n.

Depois, na linha 3, lemos o primeiro caracter. Esse caracter tem duas possibilidades, já que estamos na maratona e lá nunca lemos nada estranho:

Ser um sinal de menos, '-'; ou

Ser o primeiro dígito do número que estamos lendo. Podemos ler o sinal de menos, pois o número pode ser negativo. Nós vamos saber se ele é negativo com nossa variável sign: se ela for  − 1, o número é negativo.

As linhas 4-8 só servem para lermos o sinal do número. Chato, n~ao?

Depois, nas últimas 3 linhas, nós finalmente lemos o número! Mas como faremos isso só usando caracteres? É fácil! Primeiro, precisamos saber que todo caracter em C/C++ tem um valor associado a ele (que vem da tabela ASCII, se você estiver curioso). Nós não precisamos saber esse valor, o que precisamos saber é que, a partir do 0, eles vêm em sequência: 1, 2, 3, …, 9.

Logo, se nós sabemos que vamos ler um caracter que tem um número, o que sabemos, podemos fazer assim para converter o "número letra" para o "número número": apenas subtraímos do valor que o caracter que lemos tem o valor do caracter 0.

Por exemplo, se o caracter que lemos era um 0, nós vamos ter 0 − 0, o que dá 0. Se era um 1, e como o valor do caracter 1 é exatamente 1 maior que o do caracter 0, o resultado é 1, e assim por diante.

Agora, só falta juntar esse número com os próximos, o que faremos multiplicando o número que tínhamos até agora, que está guardado na variável n, por 10 e somando com o novo número, isso até o número acabar. * Para terminar, multiplicamos n pelo sign e pronto!

Comparando os 4 modos de entrada

Uma das coisas mais importantes nos problemas da maratona / OBI é que, além de os programas gerarem a saída correta, ou seja, estarem certos, eles têm que fazer isso em um tempo máximo. Logo, programas eficientes são fundamentais.

Uma pergunta natural é: qual é a ordem de velocidade do scanf, cin, getchar e getchar_unlocked?

Façamos um experimento, então. Já que sabemos ler inteiros com os 4 métodos, vejamos qual é mais rápido.

Eu gerei arquivos no meu computador com números aleatórios, com quantidades variando de 10 a 10000000, multiplicando cada vez por 10. O com 10 está aqui:

42002374
-1598203250
-1572806351
1875436888
689067305
-1027613511
-1507433692
11901533
-526499482
-1712410191

Depois eu rodei um programa que só lê esses números. A versão com cin é essa:

1
2
3
4
5
6
7
8
9

  #include <iostream>

  int main() {
      int x = 1;
      while (std::cin >> x) {
          x++;
      }
      return 0;
  }

Eu rodei cada programa 30 vezes com cada um dos arquivos para termos uma amostra justa e tirei a média. Os resultados estão no gráfico abaixo:

Para entradas pequenas, ou seja, com menos de 1000 números, todos são basicamente iguais. Mas quando aumentamos, o cin já se mostra o mais lento, enquanto o getchar e o scanf ficam mais ou menos iguais, com o printf começando a ficar mais lento.

O getchar_unlocked é o melhor, como podemos ver.

Claro, essa "análise" não é muito boa, já que eu estava fazendo outras coisas enquanto rodava os testes e os arquivos são razoavelmente pequenos. Mas acho que dá para ver que o getchar_unlocked é mais rápido que os outros.

Viva as funções "proibidas"!