FAST I/O

---

W pewnych sytuacjach potrzebujemy szybszych funkcji wczytujących i wypisujących dane ze standardowego wejścia/wyjścia (klawiatura, monitor). Rozwiązując zadania, które są sprawdzane automatycznie przez serwer, przy dużej ilości danych wejściowych lub wyjściowych, możemy bardzo mocno podkręcić czas rozwiązania algorytmu. Do takich sprawdzarek zalicza się między innymi pl.spoj.com z bankiem kilkuset zadań tworzonych przez społeczeństwo tego serwisu a także serwis sprawdzający rozwiązania Olimpiady Informatycznej czy szkopul.edu.pl. Niekiedy dzięki FAST I/O udaje się oszukać sprawdzarkę i rozwiązać zadanie nieoptymalnym algorytmem (oznacza to, że testy są nieprawidłowo dobrane lub nie da się fizycznie tak ich dobrać, aby szybkie wczytywanie/wypisywanie nie przechodziło).

Kluczem są szybkie funkcje wczytujące pojedynczy znak:

char c;
//wczytanie jednego znaku i zapisanie go w zmiennej c
c = getc_unlocked(stdin);

//lub
c = getchar_unlocked();

oraz wypisujące pojedynczy znak:

char c;
//wypisanie znaku przechowywanego w zmiennej c
putc_unlocked(c, stdout);

//lub
putchar_unlocked(c);

Powyższe funkcje zadeklarowane są w bibliotece $$cstdio$$ ale mogą być niezdefiniowane w niektórych kompilatorach, np. działających w środowisku Dev C++.

register char c

Dodatkowo zmienną znakową można zadeklarować jako register co oznacza, że będzie ona wrzucona bezpośrednio do rejestru procesora (jeśli jest on wolny), co dodatkowo przyspieszy operacje na tej zmiennej (rejestry procesora są najszybszymi komórkami pamięci komputera).

register char c;

Funkcje typu inline

Pamiętajmy także, aby użyć funkcji typu inline, która jest opisana w tym miejscu.

Prześledźmy kilka przykładów:

Szybkie wypisywanie liczb całkowitych nieujemnych

Metoda tradycyjna:

#include<cstdio>
 
inline void putUI(unsigned int n) {
 
     if(n==0) //ten przypadek rozpatrujemy oddzielnie
     {
     	putc_unlocked(48,stdout); //wypisz 0
     	return; //zakończ wypisywanie
     }
 
	 char tab[12];//tablica będzie przechowywać cyfry
     int p = 0;
     while(n != 0) { //wyłuskanie kolejnych cyfr z liczby n
        tab[p++] = (n % 10) + 48;
         n /= 10;
     }
     while(p--) 
         putc_unlocked(tab[p], stdout); //wypisanie liczby
}
 
int main()
{
	//wypisanie 344
	putUI(344);
 
	return 0;
}

Lub rekurencyjnie (ta funkcja działa poprawnie tylko dla liczb całkowitych dodatnich):

inline void putUI(unsigned int n) {
  
	 if(n>0) { //wyłuskanie kolejnych cyfr z liczby n
         putUI(n/10);
         putc_unlocked(n%10+48,stdout);
     }
}

Szybkie wypisywanie liczb zmiennoprzecinkowych

inline void putDB(long double n)
{
	const int eps = 3; //ustalamy precyzjé
	long long k = (long long )(n*1000); //n*10^eps
	 char arr[16],i;
     int p = 0;
    for(i=0;i<eps;i++) {
        arr[p++] = (k % 10) + 48;
        k /= 10;
    }
    arr[p++]='.';
    do{
    	arr[p++]=(k%10)+48;
    	k/=10;
    }while(k!=0); 
     
     while(p--) 
         putc_unlocked(arr[p], stdout);
}

Szybkie wczytywanie liczb nieujemnych

#include<cstdio>

inline void readUI(int *n) //tylko dodatnie
{
    register char c = 0;
    while (c < 33) c=getc_unlocked(stdin);
    (*n) = 0;
    while (c>32) {(*n)=(*n)*10LL + (c-48); c=getc_unlocked(stdin);}
}

int main()
{
	int a;
	readUI(&a);
	
	printf("%d",a);
	
	return 0;
}

Linię

Szybkie wczytywanie liczb całkowitych

inline void readINT(int *n) //ujemne i dodatnie
{
    register char c = 0, 
	znak_liczby=1;  //1 - liczba dodatnia, -1 - liczba ujemna
    while (c < 33) c=getc_unlocked(stdin);
    
    if(c==45) {znak_liczby=-1;  c=getc_unlocked(stdin);}//jesli napotkamy minus
    (*n) = 0;
    
	while (c>32) {(*n)=(*n)*10 + c-48; c=getc_unlocked(stdin);} 
  
    (*n)*=znak_liczby;
} 

Szybkie wczytywanie ciągów znaków

 inline int readS(char *a)//funkcja zwraca liczbę znaków
{
	int dl=0;
    register char c = 0;
    while (c < 33) c=getchar_unlocked(); 
   	dl = 0; //zmienna będzie przechowywać liczbę znaków
    while (c>32) {
		a[dl++] = c; 
		c=getchar_unlocked();
	}
	a[dl]=0; //ustawienie końca ciągu znaków
	return dl; //zwrócenie liczby znaków
}

Nieokreślona liczba zestawów danych

Czasami dane wejściowe składają się z nieokreślonej liczby zestawów danych (np. w tym zadaniu). Zestaw tych danych kończy się specjalnym znakiem końca pliki EOF, który ma wartość -1. W odpowiednim miejscu sprawdzamy warunek:

char c = getchar_unlocked();

if(c==-1)
{
	//zrób cos, bo nie ma juz co wczytywać
}

Jako ćwiczenie spróbuj zaimplementować:

• wczytywanie nieokreślonej liczby zestawów danych
• wczytywanie liczb zmienno-przecinkowych

Przydatne iformacje:
Kod ASCII znaku '0' = 48, znaku '-' = 45.

Białe znaki takie jak spacja, czy enter mają ASCII < 33.