Programação Competitiva

Imagine um situação em que você precise mostrar um número muito grande de valores na saída.

Por exemplo, digamos que você precise mostrar 10 mil vezes um determinado valor. O código para isso não é nada complicado e é mostrado a seguir (nas linguagens C e Python 3.x), em que eu simplesmente solicito que seja escrito o caractere 1.

#include <stdio.h>

int main() {
  int i;

  for (i = 0; i < 10000; i++) {
    printf("1");
  }

  return 0;
}

for i in range(10000):
    print("1", end = '')  

No código em Python utilizei o end=” para que os números não ficassem separados por um espaço entre eles.

Veja que mesmo que nada precise ser calculado, a escrita dessa saída exige um tempo de processamento, sendo esse tempo de escrita um tempo relativamente longo. Essa questão ficará clara no restante da explicação.

Inicialmente começarei exemplificando a questão com a linguagem C, mas recomendo que, mesmo que o interesse seja a linguagem Python, a explicação seja acompanhada.

Fiz a execução do código na linguagem C diversas vezes e obtive um tempo de execução médio de 0,8 segundos. Parece um tempo pequeno, mas que pode comprometer o tempo limite da execução de um algoritmo e pode ser significativamente melhorado.

Para melhorar o tempo de execução com essas impressões é necessário utilizar menos o comando de impressão. Para isso é preciso armazenar os valores desejados e faço isso utilizando um vetor. No código a seguir eu crio um vetor de caracteres e adiciono os valores nesse vetor, imprimindo o vetor ao final do processo.

#include <stdio.h>

#define TAM 10000
int main() {
  int i;
  char vet[TAM+1];

  for (i = 0; i < TAM; i++) {
    vet[i] = '1';
  }
  vet[i] = '\0';
  printf("%s", vet);

  return 0;
}

Veja que na linha 11 eu adicionei um caractere ‘\0’ finalizar a string e é por causa dele que o tamanho do vetor ficou com TAM+1 (para comportar os 10 mil valores mais esse caractere).

O código aumentou de complexidade, mas pelo fato de escrever a saída apenas 1 vez, isso melhor a velocidade de execução, que passou a ser de 0,02 segundos, ou seja, 40 vezes mais rápido do que a solução anterior.

Mesmo que a execução seja mais rápida, veja que a solução ocupa mais memória e que o uso de memória pode exceder o limite disponível. Nesse caso, é preciso alterar o código ainda pensando em reduzir o uso dos printfs. No código abaixo eu aumento em 100 vezes a quantidade de valores a serem impressos, mas sem aumentar a quantidade de memória do código anterior. Eu precisei dar mais prints, mas mesmo assim o tempo médio para a execução do código ficou em 0,06 segundos.

#include <stdio.h>

#define TAM 10000
int main() {
  int i,j;
  char vet[TAM+1];

  for (i = 0; i < 100; i++) {
    for (j = 0; j < TAM; j++) {
      vet[j] = '1';
    }
    vet[i] = '\0';
    printf("%s", vet);
  }

  return 0;
}

Para a linguagem Python é ideia é a mesma, mas tenho algumas observações. Na linguagem Python existem algumas questões a serem vistas. Se eu executar o código a seguir, o resultado será mostrado no seguinte formato: [‘1’, ‘1’, ‘1’, …. ‘1’].

vet = []
for i in range(TAM):
    vet.append('1')
print(vet)

É possível fazer uma string conforme fiz no código em linguagem C. Mostro o código abaixo, mas já aviso que o desempenho dele é bastante ruim por causa das concatenações necessárias, sendo inclusive pior do que a primeira solução mostrada.

saida = ""
for i in range(TAM):
    saida = saida + '1'
print(saida)

A minha solução para essa questão em Python é utilizar um recurso do próprio print do Python. O asterisco na frente do nome da variável é para que sejam mostrados todos os valores do vetor de forma iterativa. o uso do sep=” é para que não seja adicionado um espaço entre os caracteres (é a configuração para o que separador entre caracteres seja nada).

vet = []
for i in range(TAM):
    vet.append('1')
print(*vet, sep='')

Se quiser comparar os tempos de execução de cada uma dessas soluções em Python, fiz um script com as soluções que está disponível em: https://py3.codeskulptor.org/#user306_fYvT7MH09t_0.py