Saturday, November 23, 2013

Fast Cin

On dit souvent que les lectures d’entrées sont lentes en C++ et qu’il est préférable d’utiliser scanf/printf à cin/cout. En particulier sur certains sites de problèmes, il serait impossible d’éviter le TIME_LIMIT en utilisant cin/cout. Voyons les faits et comment améliorer les input/output.

Je vais considérer le problème suivant: on doit lire une liste d’entiers (plus petit que 10^9) et tous les dix entiers lus afficher la somme globale modulo 10^9+7.

Voici le code avec cin/cout

#include<iostream>
using namespace std;

const int MOD=1000000007;

int main(){
  //ios::sync_with_stdio(false);
  //cin.tie(nullptr);
  int sum=0;
  int cmt=0;
  int tmp;
  while(cin >> tmp){
    sum+=tmp;
    sum%=MOD;
    ++cmt;
    if(cmt%10==0){
      cmt=0;
      cout << sum << '\n';
    }
  }
}

et avec printf/scanf

#include<cstdio>
using namespace std;

const int MOD=1000000007;

int main(){
  int sum=0;
  int cmt=0;
  int tmp;
  while(scanf("%d",&tmp) != EOF){
    sum+=tmp;
    sum%=MOD;
    ++cmt;
    if(cmt%10==0){
      cmt=0;
      printf("%d\n",sum);
    }
  }
}

J’ai effectué le test avec 50 millions d’entiers générés via ce code (ce qui donne un fichier d’input de 50Mo):

#!/usr/bin/env python
import random
for i in xrange(5000000):
    print random.randint(0,1000000000)

Les résultats montrent clairement que scanf/printf est bien plus rapide. Avec gcc4.8.2 on passe de 12 secondes à 1,5 secondes (dans tous les cas je compile avec -O2).

Une raison de la lenteur de cin/cout est que les flux standards sont synchronisés sur ceux de C. On peut stopper cette synchronisation avec io::sync_with_stdio(false) à placer juste en dessous du main. On passe alors à 2s. Le nouveau code est à peine plus lent que le code utilisant scanf/printf. Mais on peut encore améliorer les choses, ici l’entrée est synchronisée avec la sortie, c’est à dire que cout est flushé avant de pouvoir lire sur cin. Dans le cas d’un programme non interactif cette synchronisation est inutile. On peut la supprimer en ajoutant cin.tie(nullptr), ou sans utiliser nullptr de C++11, cin.tie(0). On obtient alors un code qui s’exécute en 0,8s. Notre code est devenu plus rapide que le code scanf/printf.

On peut tester sur d’autres types que les entiers, les résultats sont toujours les mêmes. Avec io::sync_with_stdio(false) et cin.tie(nullptr) il n’y a pas de perte de performance à utiliser cin/cout. Dans ce cas attention à ne pas mélanger cin/scanf vu qu’ils ne sont maintenant plus synchronisés. Notez bien que ceci n’est pas une méthode miracle, et n’a une chance de vous sauver du TIME_LIMIT que dans le cas d’un algo linéaire (à la limite O(n ln(n))). Sinon le temps de lecture d’entrées est de toute façon négligeable devant le temps d’exécution de votre algo.

méthode temps
cin/cout 12s
cin/cout + sync_with_stdio(false) 2s
cin/cout + sync_with_stdio(false) + cin.tie(nullptr) 0,8s
scanf/printf 1,5s

No comments:

Post a Comment