Clasa a 7-a Lecția 15: Citire / scriere rapidă

From Algopedia
Jump to navigationJump to search

Înregistrare video curs

Load video
YouTube


Citire/scriere rapidă cu fgetc() / fputc()

Știm că atunci când avem de citit numere la intrare fscanf() este foarte lentă. Știm că putem citi mai rapid folosind fgetc() și calculând numerele. Am prezentat, în trecut, o funcție de citire a întregilor bazată pe fgetc(). Am spus că, printre elevi, circulă denumirea de parsing. Vom folosi și noi această denumire, deși ea nu este tocmai corectă, parsingul fiind un capitol al informaticii care se ocupă cu mult mai mult decât citirea întregilor.

Nu am prezentat niciodată o funcție de scriere eficientă a întregilor, care să nu folosească fprintf().


Citire/scriere rapidă cu fgetc() / fputc()

Iată, mai jos, atât funcția de citire cu care suntem obișnuiți, cât și o funcție de scriere, ambele bazate pe fgetc() și fputc(): 

// citire intreg cu semn
int readInt() {
  int ch, res = 0, semn = 1;

  while ( isspace( ch = fgetc( fin ) ) );
  if ( ch == '-' ) {
    semn = -1;
    ch = fgetc( fin );
  }
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = fgetc( fin ) ) );

  return semn * res;
}

// scriere intreg cu semn
void writeInt( int x ) {
  int i;
  char cifre[10];

  if ( x < 0 ) {
    fputc( '-', fout );
    x = -x;
  }

  i = 0;
  do {
    cifre[i++] = '0' + x % 10;
    x /= 10;
  } while ( x > 0 );

  while ( i > 0 )
    fputc( cifre[--i], fout );

  fputc( '\n', fout ); // separatorul, poate sa difere (' '?)
}


Cum procedează funcția de scriere rapidă? Ea folosește împărțiri la constanta 10, împărțiri mult studiate în literatura de specialitate. Ele nu sunt traduse în cod mașină ca împărțiri. Compilatorul folosește matematică în clasă de resturi modulo, folosind înmulțiri cu inversul modular și operații shift. Împărțirea la 10 va fi mai rapidă decât o împărțire oarecare, dar mai lentă decât o adunare.

Se poate mai bine?


Citire/scriere rapidă cu fread() / fwrite()

Funcțiile fread() și fwrite() se află la baza funcțiilor fscanf() / fprintf() și fgetc() / fputc(). Ele sunt cele mai de jos funcții de citire / scriere care folosesc bufferele sistemului de operare.

Cum le vom folosi? Citirea de pe disc, sau alt mediu extern, este foarte lentă. Ceea ce ia cel mai mult este citirea primului octet. Octeții care urmează se citesc mult mai rapid. De aceea este foarte ineficient să citim câte un octet o dată folosind fread().

Vom citi, în schimb, câte un bloc de date mai mare în memorie, din care vom returna câte un octet (caractere) la cerere. Acest bloc se numește buffer și este folosit și în funcțiile sistem, fgetc() și fscanf().

Iată cum arată un parsing scris cu fread() și fwrite(): 

#include <stdio.h>
#include <ctype.h>

#define BUFSIZE (128 * 1024)

FILE *fin, *fout;
int rpos = BUFSIZE - 1; char rbuf[BUFSIZE];
int wpos = 0; char wbuf[BUFSIZE];

int v[2000000];

// citire caracter
static inline char readChar() {
  if ( !(rpos = (rpos + 1) & (BUFSIZE - 1)) )
    fread( rbuf, 1, BUFSIZE, fin );
  return rbuf[rpos];
}
 
// citire intreg cu semn
int readInt() { // citeste un intreg
  int ch, res = 0, semn = 1;

  while ( isspace( ch = readChar() ) );
  if ( ch == '-' ) {
    semn = -1;
    ch = readChar();
  }
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = readChar() ) );

  return semn * res;
}

// scriere caracter
static inline void writeChar( char ch ) {
  wbuf[wpos] = ch;
  if ( !(wpos = (wpos + 1) & (BUFSIZE - 1)) )
    fwrite( wbuf, 1, BUFSIZE, fout );
}
 
// scriere intreg cu semn
void writeInt( int x ) {
  int i;
  char cifre[10];

  if ( x < 0 ) {
    writeChar( '-' );
    x = -x;
  }

  i = 0;
  do {
    cifre[i++] = '0' + x % 10;
    x /= 10;
  } while ( x > 0 );

  while ( i > 0 )
    writeChar( cifre[--i] );

  writeChar( '\n' ); // separatorul, poate sa difere (' '?)
}

// scrie caracterele ramase in buffer
static inline void flushBuf() {
  fwrite( wbuf, 1, wpos, fout );
}


Cum folosim aceste funcții? Astfel: 

  fin = fopen( "input.in", "r" );
  n = readInt();
  // ... alte citiri
  fclose( fin );

  fout = fopen( "input.out", "w" );
  writeInt( n );
  // ... alte scrieri
  flushBuf(); // ne asiguram ca bufferul este complet scris
  fclose( fout );


Comparații moduri de citire / scriere

Ce funcții ar trebui să folosim atunci când facem parsing? Care este diferența de viteză între ele?

Comparația între diverse funcții nu este ușoară, deoarece sistemul de operare va încărca în memorie fișierele des folosite, așa numitul caching. Aceasta face ca citirile să se efectueze din memorie, și nu de pe disc, ceea ce le va face să apară în mod artificial mai rapide decât sunt în realitate. Pentru o testare reală ar trebui să ne asigurăm că fișierele nu se află în cache.

Iată o comparație între diversele tipuri de citire/scriere. Ea măsoară două milioane de citiri și două milioane de scrieri de întregi folosind cele trei metode: fscanf() / fprintf(), fgetc() / fputc() și fread() / fwrite(). Ca metodologie folosită, am executat fiecare metodă de zece ori și am luat cel mai mic timp obținut. Aceasta înseamnă, probabil, că fișierul de intrare se află în cache. Pe de altă parte același lucru este foarte probabil să se întâmple și pe evaluatorul de la olimpiadă.


Timpi Pentium 4 2.40GHz / HDD (NerdArena) 2 milioane citiri 2 milioane scrieri
fscanf() / fprintf() 994ms 895ms
fgetc() / fputc() 348ms (2.9x) 598ms (1.5x)
fread() / fwrite() 166ms (6x) 419ms (2.1x)


Timpi core i7-7700HQ 2.8GHz / SSD PCIe (laptop tipic) 2 milioane citiri 2 milioane scrieri
fscanf() / fprintf() 234ms 135ms
fgetc() / fputc() 72ms (3.25x) 95ms (1.4x)
fread() / fwrite() 45ms (5.2x) 62ms (2.2x)


Desigur că lucrurile pot sta diferit între Windows și Linux.


Temă 15

Să se rezolve următoarele probleme (program C trimis la NerdArena):


Accesează rezolvarea temei 15

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_7-a_Lecția_15:_Citire_/_scriere_rapidă&oldid=18445"