Méthodes de lire un fichier d'entrée

Ce test est basé sur des articles sur internet. Le but de ce test est de trouver une façon de lire des entiers à partir d'un fichier le plus vite possible, c'est un travail qu'on doit fait au début de notre programme du concours. Nous avons fait des test et voilà leur résultat.

La premier réflexion qu'on a fait est de utiliser cin et cout dans std, nous savons cette façon n'est pas le plus vite mais nous ne savons pas sa vitesse. Nous avons fait un tes avec 10000000 entier, (et tous les autres test est sur ces 10000000 aussi )le code est très simple:


std::cin>>data[i]

Le résultat est très mauvais, oui très mauvais:

time ./t1
real 0m5.615s
user 0m5.544s
sys 0m0.068s

On a quand même utilisé 5-6 seconde pour lire un fichier, de plus dans notre programme cette partie est une partie ne peut pas être parallélisée, donc en cherchant des méthode sur internet, nous avons commencé un autre test.
La deuxième méthode est de utiliser scanf, on dit que c'est beaucoup plus vite que cin, nous avons juste changé une ligne de code:


for (i;i<MAXN;i++)
scanf("%d",&data[i]);


Le résultat est vraiment beaucoup mieux cette fois ci:

time ./t2
real 0m1.909s
user 0m1.844s
sys 0m0.060s

En fait, cin est super lente parce que chaque fois il fait des synchronisation avec stdin, une personne a dit sur internet qu'on peut aussi fermer cette synchronisation avec cette ligne de code là:

std::ios::sync_with_stdio(false).

Comme cela, cin peut avoir même vitesse que scanf.

Nous pensons qu'on peut encore mieux faire, les deux méthode est lente peut être à cause de la vérification du type, donc nous avons fait une méthode de fgetc qui va lire caractère par caractère d'un flux :


FILE *fd=freopen("input.txt","rb",stdin);
int i=0;
int j=0;
char p;
while(!feof(fd)){
p=fgetc(fd);
if (p == ' ') i++;
if(p=='\n') j++;
}


Ce méthode de là peut aussi indiquer le nombre du ligne et du colonne, et le résultat est mieux que les deux premiers:

time ./t3
real 0m1.412s
user 0m1.376s
sys 0m0.032s

Après nous avons trouvé une méthode sur internet qui a utilisé fread, cette méthode-là peut être encore plus vite:


FILE *fd=fopen("input.txt","r");
int len = fread(buf,1,MAXS,fd);
buf[len] = '';
int i;
numbers[i=0]=0;
for (char *p=buf;*p && p-buf<len;p++){
if (*p == ' '){
numbers[++i]=0;}
else{
numbers[i] = numbers[i] * 10 + *p - '0';}
}



Le principe est de lire tout fichier dans le mémoire et de travailler sur le mémoire après, et le résultat est beaucoup mieux qu'avant:

time ./t2
real 0m0.288s
user 0m0.184s
sys 0m0.108s

Cette méthode est 10 fois plus vite que celle de scanf et 5 fois plus vite que celle de fgetc, enfin nous avons utilisé celle-ci pour notre programme.
Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.