Wszystko czego potrzebują studenci

TO JEST KOMENTARZ DO ZADANIA 'PROJEKT 1′ (teraz zwanego Zadanie 5) – http://skalski.at/2013/01/27/pjwstk-asd-projekt-1-rozwiazanie/

W tym kodzie zmieniłem nazwy zmiennych na 'opisowe’ i dodałem dużo komentarzy przy if’ach i pętlach. Samo działanie/algorytm bez zmian.

Do zrozumienia algorytmu trzeba wiedzieć co to są grafy (tutaj zaimplementowane jako tablice i listy).

Co do dużej ilości klas:

ListElementTown, ListTowns, ListElementThief, ListThiefs – to moje własne implementacje 'list’, równie dobrze do testów możecie użyć normalnej C++’owej listy http://www.cplusplus.com/reference/vector/vector/ (ma ona więcej funkcjonalości i jest znacznie wolniejsza, więc walcząc o sekundy i tak warto pomyśleć o własnym 'list’ i 'map’ [dla 'optymalizacja hardcore’owa])

Opis ogólny założeń programu:
kandydat – obiekt ktory liczy koszt kampani A/B i zajmuje miasta [tworzy sztaby wyborcze]
miasto – wierzcholek grafu, zawierajacego informacje o sasiedztwie z innymi miastami
sztab wyborczy – przypisanie danego miasta do kandydata, przypisanego miasta nie moze przejac inny kandydat
prawybory – jezeli w miescie nie ma jeszcze 'sztabu wyborczego’, a w ktoryms z miast sasiadujacych jest, to w danym miescie nalezy przeprowadzic prawybory zgodnie z podanym algorytmem (wygrywa ten kandydat ktorego sztaby sa w najwiekszej ilosci miast sasiednich)
tura – jeden obrot petli w ktorym kazde miasto w ktorym jest sztab proboje zalozyc sztab (doprowadza do prawyborow wpisujac swojego kandydata na liste) w sasiednich miastach

KANDYDACI JAKO WIRUSY:
Program mozna latwiej zrozumiec, patrzac na problem jak na komorki organizmu (miasta) i wirusy (kandydatow):
Wirusy znalazly sie w kilku komorkach, kazda komorka zarazona w danej 'turze’ zaraza wszystkie z ktorymi ma kontakt [miasta sasiedzkie] w nastepnej turze
Tak wiec mozna podzielic komorki na 3 grupy:
– nie zarazone
– zarażone
– zarażające
1. Kazda komorka w chwili zarazenia staje sie zarazajaca [w nastepnej turze!]
2. Kazda komorka po turze w ktorej zarazala staje sie 'zarazona’ [sama juz wiecej nie zaraza, nie ma po co, bo wszystkich sasiadow juz zarazila, a sasiadow nie przybywa]

Dana nie zarazona komorka, moze byc w danej turze zarazana przez wiecej, niz jedna sasiednia komorke, wygrywa ten wirus ktory ma najwiecej sasiadujacyh zarazonych komorek [przy remisie porownujemy ID wirusa wedlug polecenia w wersji A i B].
W zalozeniu kazda komorka ma jakiegos sasiada, wiec algorytm mieli dane do czasu, az ilosc zarazonych komorek jest rowna liczbie wszystkich komorek.

UWAGA! Opisany powyżej algorytm to teoretycznie najwydajniejsza wersja kodu, a nie ta jaka jest przedstawiona w C++ [zarażone ciągle zarażają.., dużo rzeczy jest zapisywane do tymczasowych list mimo, że mogło by działać bez nich itd.].

Kod C++ był pisany na ostatnią chwilę, a przed publikacją przeszedł jeszcze obróbkę po której zgodność z oryginałem według 'plagiatora’ wynosiła poniżej 5% [poprzez dodanie mniej wydajnych pętli, 'get’ w listach, deklaracje zmiennych w złych miejscach itd.]

ROZWIĄZANIE KTÓRE OPUBLIKOWAŁEM W C++ JEST DALEKIE OD TEORETYCZNIE NAJSZYBSZEGO. W DODATKU NIE JEST WYDAJNE (CO ZMIENIĆ OPISZĘ NA KOŃCU POSTA). Nie można wprost powiedzieć jakie rozwiązanie będzie najlepsze, bo na każdy algorytm duży wpływ ma ilość miast, kandydatów i połączeń między miastami, a jakie są ilości w danych testowych to nie wiem 🙁

#include<stdio.h>
 
class Miasto;
class Kandydat;
 
class ListElementTown
{
    public:
        Miasto* miasto;
        ListElementTown* nastepnyElementListy;
 
        ListElementTown(Miasto* m)
        {
            this->miasto = m;
            this->nastepnyElementListy = NULL;
        }
 
        ListElementTown(Miasto* m, ListElementTown* nastepnyElementListy)
        {
            this->miasto = m;
            this->nastepnyElementListy = nastepnyElementListy;
        }
};
 
class ListTowns
{
    public:
        ListElementTown* pierwszyElementListy;
        int iloscElementow;
 
        ListTowns()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
 
        Miasto* get(int elementIterator)
        {
            ListElementTown* tmp = pierwszyElementListy;
            for(int i = 0; i < elementIterator; i++)
                tmp = tmp->nastepnyElementListy;
 
            return tmp->miasto;
        }
 
        void add(Miasto* m)
        {
            if(this->pierwszyElementListy == NULL)
                this->pierwszyElementListy = new ListElementTown(m);
            else
                pierwszyElementListy = new ListElementTown(m, pierwszyElementListy);
 
            iloscElementow++;
        }
 
        bool contains(Miasto* m)
        {
            ListElementTown* tmp = pierwszyElementListy;
            while(tmp)
            {
                if(m == tmp->miasto)
                    return true;
 
                tmp = tmp->nastepnyElementListy;
            }
            return false;
        }
 
        void clear()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
};
 
class ListElementThief
{
    public:
        Kandydat* kandydat;
        ListElementThief* nastepnyElementListy;
 
        ListElementThief(Kandydat* t)
        {
            this->kandydat = t;
            this->nastepnyElementListy = NULL;
        }
 
        ListElementThief(Kandydat* t, ListElementThief* nastepnyElementListy)
        {
            this->kandydat = t;
            this->nastepnyElementListy = nastepnyElementListy;
        }
};
 
class ListThiefs
{
    public:
        ListElementThief* pierwszyElementListy;
        int iloscElementow;
 
        ListThiefs()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
 
        Kandydat* get(int elementIterator)
        {
            ListElementThief* tmp = pierwszyElementListy;
            for(int i = 0; i < elementIterator; i++)
                tmp = tmp->nastepnyElementListy;
 
            return tmp->kandydat;
        }
 
        void add(Kandydat* t)
        {
            if(this->pierwszyElementListy == NULL)
                this->pierwszyElementListy = new ListElementThief(t);
            else
            {
                pierwszyElementListy = new ListElementThief(t, pierwszyElementListy);
            }
            iloscElementow++;
        }
 
        bool contains(Kandydat* t)
        {
            ListElementThief* tmp = pierwszyElementListy;
            while(tmp)
            {
                if(t == tmp->kandydat)
                    return true;
 
                tmp = tmp->nastepnyElementListy;
            }
            return false;
        }
 
        void clear()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
};
class Miasto
{
    public:
        int id;
        Kandydat* kandydatKtoryZalozylSztabWyborczyA;
        Kandydat* kandydatKtoryZalozylSztabWyborczyB;
        Kandydat* zwyciezcaA;
        Kandydat* zwyciezcaB;
        ListThiefs* kandydaciA;
        ListThiefs* kandydaciB;
        ListTowns* miastaSasiedzkie;
 
        Miasto(int i)
        {
            id = i;
            kandydatKtoryZalozylSztabWyborczyA = NULL;
            kandydatKtoryZalozylSztabWyborczyB = NULL;
            zwyciezcaA = NULL;
            zwyciezcaB = NULL;
            kandydaciA = new ListThiefs();
            kandydaciB = new ListThiefs();
            miastaSasiedzkie = new ListTowns();
        }
};
 
class Kandydat
{
    public:
        int id;
        int tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA;
        int tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB;
        int kosztKampaniA;
        int kosztKampaniB;
 
        Kandydat(int indeks)
        {
            this->id = indeks;
            this->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA = 0;
            this->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB = 0;
            this->kosztKampaniA = 0;
            this->kosztKampaniB = 0;
        }
};

int main()
{ 
    int iloscDzialajacychSztabowWyborczychA = 0;
    int iloscDzialajacychSztabowWyborczychB = 0;
    int iloscMiast = 0;
    int iloscKandydatow = 0;
	// wczytujemy ilosc miast
    fscanf(stdin, "%d", &iloscMiast);
	// tworzymy tablice z miastami
    Miasto* miasta[iloscMiast];
    for(int i = 0; i < iloscMiast; i++)
    {
		// uzupelniamy ja pustymi miastami 
        miasta[i] = new Miasto(i);
    }
    int miasto_1;
    int miasto_2;
	// wczytujemy po kolei po 2 id miast ktore sa sasiadami
    fscanf(stdin, "%d", &miasto_1);
    fscanf(stdin, "%d", &miasto_2);
	// lista tych miast konczy sie dwoma id miast -1
    while(miasto_1 != -1 && miasto_2 != -1)
    {
		// graf ma byc nie skierowany, czyli jak sasiad X wie o sasiedzie Y to Y tez musi wiedziec o X
		// dlatego dodajemy informacje o sasiedze do obu miast
        miasta[miasto_1]->miastaSasiedzkie->add(miasta[miasto_2]);
        miasta[miasto_2]->miastaSasiedzkie->add(miasta[miasto_1]);
        fscanf(stdin, "%d", &miasto_1);
        fscanf(stdin, "%d", &miasto_2);
    }
	// wczytujemy ilosc kandydatow
    fscanf(stdin, "%d", &iloscKandydatow);
	// tworzymy tablice z kandydatkami
    Kandydat* kandydaci[iloscKandydatow];
    for(int i = 0; i < iloscKandydatow; i++)
    {
		// uzupelniamy ja kandydatami ktorzy znaja swoje id
        kandydaci[i] = new Kandydat(i);
    }
	// wczytujemy sztaby poczatkowe kandydatow
    int idSztabuStartowegoKandydata;
    for(int i = 0; i < iloscKandydatow; i++)
    {
		// zalozenie jest takie, ze kazdy kandydat ma wlasne miasto,
		// wiec nie trzeba sprawdzac czy aby 2 nie jest naraz w tym samym miescie startowym
        fscanf(stdin, "%d", &idSztabuStartowegoKandydata);
		// dla algorytmu z zasada A i zasada B przypisujemy, ze ten kandydat juz wygral w tym miescie wybory
        miasta[idSztabuStartowegoKandydata]->kandydatKtoryZalozylSztabWyborczyA = kandydaci[i];
		// naliczany koszt kampani wyborczej
        kandydaci[i]->kosztKampaniA++;
		// dodajemy +1 do ilosci dzialajacych sztabow wyborczych
        iloscDzialajacychSztabowWyborczychA++;
		
		// tutaj to samo co wyzej tylko dla algorytmu 'B'
        miasta[idSztabuStartowegoKandydata]->kandydatKtoryZalozylSztabWyborczyB = kandydaci[i];
        kandydaci[i]->kosztKampaniB++;
        iloscDzialajacychSztabowWyborczychB++;
    }
	/*
	teraz dochodzimy do samego mielenia danych:
	w celu szybszych obliczen zrobimy sobie liste pomocnicza 'miastaWktorychTrzebaPrzeprowadzicPrawybory'
	zalozenia:
	mamy milion wierzcholkow grafu [miast]
	kazdy wierzcholek ma polaczenie z tysiacami innych wierzcholkow [innymi miastami]
	mamy kilkuset kandydatow ktorzy maja ustalone miasta startowe
	*/
    ListTowns* miastaWktorychTrzebaPrzeprowadzicPrawybory = new ListTowns();
	// [PĘTLA GŁÓWNA] do poki nie we wszystkich miastach sa sztaby wyborcze
    while(iloscDzialajacychSztabowWyborczychA != iloscMiast && iloscDzialajacychSztabowWyborczychB != iloscMiast)
    {
		// co obrot petli (ture) czyscimy liste pomocnicza
        miastaWktorychTrzebaPrzeprowadzicPrawybory->clear();
		// [PĘTLA 1]
        for(int i = 0; i < iloscMiast; i++)
        {
			// dla kazdego miasta ..
            if(miasta[i]->kandydatKtoryZalozylSztabWyborczyA != NULL && miasta[i]->kandydatKtoryZalozylSztabWyborczyB != NULL)
            {
				// .. w ktorym jest sztab wyborczy [X kandydata]
				// [PĘTLA 1.1]
                for(int i2 = 0; i2 < miasta[i]->miastaSasiedzkie->iloscElementow; i2++)
                {
					// dla kazdego miasta sasiedniego ..
                    if(miasta[i]->miastaSasiedzkie->get(i2)->kandydatKtoryZalozylSztabWyborczyA == NULL && miasta[i]->miastaSasiedzkie->get(i2)->kandydatKtoryZalozylSztabWyborczyB == NULL)
                    {
						// .. w ktorym nie ma sztabu wyborczego
						
						// wszystko jest w 'ifach', bo wiele innych miast moze byc sasiadem w ktorym jest juz sztab wyborczy,
						// a lista kandydatow i miast w ktorych maja byc wybor ma byc bez powtorzen
                        if(!(miasta[i]->miastaSasiedzkie->get(i2)->kandydaciA->contains(miasta[i]->kandydatKtoryZalozylSztabWyborczyA)))
                        {
							// dodaj do listy kandydatow A o ile jeszcze na niej nie jest
                            miasta[i]->miastaSasiedzkie->get(i2)->kandydaciA->add(miasta[i]->kandydatKtoryZalozylSztabWyborczyA);
                        }
                        if(!(miasta[i]->miastaSasiedzkie->get(i2)->kandydaciB->contains(miasta[i]->kandydatKtoryZalozylSztabWyborczyB)))
                        {
							// dodaj do listy kandydatow B o ile jeszcze na niej nie jest
                            miasta[i]->miastaSasiedzkie->get(i2)->kandydaciB->add(miasta[i]->kandydatKtoryZalozylSztabWyborczyB);
                        }
                        if(!(miastaWktorychTrzebaPrzeprowadzicPrawybory->contains(miasta[i]->miastaSasiedzkie->get(i2))))
                        {
							// dodaj miasto sasiedzkie do listy miast w ktorych trzeba przeprowadzic prawybory w tej turze
                            miastaWktorychTrzebaPrzeprowadzicPrawybory->add(miasta[i]->miastaSasiedzkie->get(i2));
                        }
                    }
                }
            }
        }
		// koniec 'for' ktory generowal liste miast w ktorych trzeba przeprowadzic prawybory i dodawal w tych miastach kandydatow
        ListElementTown* elementPoczatkowy = miastaWktorychTrzebaPrzeprowadzicPrawybory->pierwszyElementListy;
        int loopsCounter = miastaWktorychTrzebaPrzeprowadzicPrawybory->iloscElementow;
		// teraz trzeba przeprowadzic prawybory i ustalic ktory kandydat wygral w danym miescie
		// przy czym jego wygrana nie moze wplywac na obliczenia innych wygranych (na to moze wplywac dopiero w nastepnej 'turze' algorytmu)
		// dlatego wynik prawyborow zapisujemy do zmiennych 'zwyciezcaA' i 'zwyciezcaB'
		// [PĘTLA 2]
        for(int i = 0; i < loopsCounter; i++)
        {
            Miasto* aktualneMiasto = elementPoczatkowy->miasto;
            Kandydat* tmpKandydat = NULL;
			// z dziwnych powodow trzymamy ilosc 'sztabow wyborczych w miastach sasiednich' w kandydatach,
			// wiec trzeba to co obrot petli czyscic w kazdym kandydacie
            for(int x = 0; x < iloscKandydatow; x++)
            {
                kandydaci[x]->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA = 0;
                kandydaci[x]->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB = 0;
            }
            int loopsCounter_2 = aktualneMiasto->miastaSasiedzkie->iloscElementow;
            ListElementTown* petlaPoSasiadach = aktualneMiasto->miastaSasiedzkie->pierwszyElementListy;
			// teraz dodajemy w tych kandydatach liczbe przechowujaca w ilu miastach sasiedzkich [dla 'aktualneMiasto'] jest sztab danego kandydata
            for(int ii = 0; ii < loopsCounter_2; ii++)
            {
                Miasto* tmpMiasto = petlaPoSasiadach->miasto;
                if(tmpMiasto->kandydatKtoryZalozylSztabWyborczyA != NULL)
                {
                    tmpMiasto->kandydatKtoryZalozylSztabWyborczyA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA++;
                    tmpMiasto->kandydatKtoryZalozylSztabWyborczyB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB++;
                }
                petlaPoSasiadach = petlaPoSasiadach->nastepnyElementListy;
            }
			// teraz sprawdzamy ktory kandydat ma najwiecej sztabow wyborczych w sasiadujacych miastach
            Kandydat* zwyciezcaA = aktualneMiasto->kandydaciA->get(0);
            Kandydat* zwyciezcaB = aktualneMiasto->kandydaciB->get(0);
 
			// dla A
            loopsCounter_2 = aktualneMiasto->kandydaciA->iloscElementow;
            for(int i2 = 1; i2 < loopsCounter_2; i2++)
            {
                tmpKandydat = aktualneMiasto->kandydaciA->get(i2);
                if((zwyciezcaA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA > tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA) || (zwyciezcaA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA == tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA && zwyciezcaA->id < tmpKandydat->id))
                    zwyciezcaA = tmpKandydat;
            }
            aktualneMiasto->zwyciezcaA = zwyciezcaA;
            aktualneMiasto->kandydaciA->clear();
			// dla B
            loopsCounter_2 = aktualneMiasto->kandydaciB->iloscElementow;
            for(int i2 = 1; i2 < loopsCounter_2; i2++)
            {
                tmpKandydat = aktualneMiasto->kandydaciB->get(i2);
                if((zwyciezcaB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB < tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB) || (zwyciezcaB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB == tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB && zwyciezcaB->id > tmpKandydat->id))
                    zwyciezcaB = tmpKandydat;
            }
            aktualneMiasto->zwyciezcaB = zwyciezcaB;
            aktualneMiasto->kandydaciB->clear();
            elementPoczatkowy = elementPoczatkowy->nastepnyElementListy;
        }
        elementPoczatkowy = miastaWktorychTrzebaPrzeprowadzicPrawybory->pierwszyElementListy;
        loopsCounter = miastaWktorychTrzebaPrzeprowadzicPrawybory->iloscElementow;
		// znamy juz zwyciezcow, teraz trzeba ich zwycieztwa w prawyborach przepisac na zalozone sztaby, aby w kolejnej 'turze' mogli zakladac kolejne sztaby
		// [PĘTLA 3]
        for(int i = 0; i < loopsCounter; i++)
        {
            Miasto* tmpMiasto = elementPoczatkowy->miasto;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyA = tmpMiasto->zwyciezcaA;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyB = tmpMiasto->zwyciezcaB;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyA->kosztKampaniA++;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyB->kosztKampaniB++;
            iloscDzialajacychSztabowWyborczychA++;
            iloscDzialajacychSztabowWyborczychB++;
            elementPoczatkowy = elementPoczatkowy->nastepnyElementListy;
        }
    }
    for(int i = 0; i < iloscKandydatow; i++)
    {
        fprintf(stdout, "%d %d\n",kandydaci[i]->kosztKampaniA, kandydaci[i]->kosztKampaniB);
    }
    return 0;
}

Optymalizacja:

– zmiana wczytywania danych na szybkie wczytywanie ( http://skalski.at/2014/11/04/asd-spox-spoj-szybkie-wczytywanie-intow-w-c/ )

– przepisanie kodu tak, żeby nigdy nie korzystał z funkcji 'get’ [super nie wydajna!!] w listach (ZAWSZE algorytm iteruje po elementach listy w pętli od elementu zero do końca, więc zamiast 'for’ trzeba dać 'while’ który się zatrzyma jak 'next’ będzie NULLem)

– jeśli już nie przepisywać kodu na 'while’ to dodać w listach 'currentElement’ i 'currentIndex’, tak, aby po prośbie o element o 'id’ wyższym o jeden nie jechać pętlą od elementu zerowego do tego o 'id’ podanych tylko przejść do 'next’

– w pętlach wiele razy występują np. 'miasta[i]’ czy jeszcze gorsze 'miasta[i]->miastaSasiedzkie->get(i2)’, należało by przypisać wartość zmiennej do jakiejś zmiennej tymczasowej Miasto* tmpMiasto i z niej korzystać zamiast w jednej pętli po 8 razy odwoływać się do 2-3 skoków po pamięci RAM

– WSZYSTKIE zmienne tymczasowe powinny być zadeklarowane na początku 'main’, a nie w jakimkolwiek 'for’ czy 'while’, może to zaoszczędzić miliony wrzuceń i usunięć zmiennych z stosu co może dać te brakujące milisekundy do zaliczenia

– w listach funkcja 'clear’ nie czyści listy, więc jest tutaj duży wyciek pamięci, bo 'pierwszyElement’ ustawia na NULL, ale ten element mógł wskazywać na listę miliona elementów które już z RAM nie są wywalane, jaki to ma wpływ na wydajność nie wiem [może mieć pozytywny! warto sprawdzić czy aktualna wersja bez czyszczenia nie jest szybsza]

Optymalizacja hardcore’owa:

– kod oznaczony jako PĘTLA 1 i PĘTLA 2 uprościć poprzez nie używanie listy 'kandydaciA’ (na podstawie której PĘTLA 2 oblicza kto wygrał), tylko użycie mapy ( http://www.cplusplus.com/reference/map/map/)  która by przechowywala danych kandydatow bez powtorzen i ile razy wystapili w miastach sasiedzkich [ pseudokod(!):  std::map<Kandydat* kandydat, int iloscWystapien> kandydaciA ]

W tym semestrze zadania z spox’a wymagają jeszcze szybszego wczytywanie danych, niż rok temu, więc wielu osobą może przydać się informacja jak szybko wczytać inty z wejścia.

Jak wczytać z wejścia int’y najszybciej? Wczytując po znaku z wejścia cyfry i zamieniając na int’y kiedy 'inny znak niż cyfra’.

Do wczytywania najlepiej użyć getchar_unlocked [do użycia tylko w aplikacjach jednowątkowych – czyli takich jak na spox, zwykłe getchar robi to samo tylko, że przy każdym wczytaniu znaku chce synchronizować wątki [jeden wątek?] i wykonuje się 4 razy dłużej!], funkcja ta istnieje na 'spox.spoj.pl’, jeśli na kompie jej nie macie to do testów możecie podmienić tą linijkę:

#define gc getchar_unlocked

na:

#define gc getchar

A to cała funkcja (TYLKO DLA DODATNICH!):

#define gc getchar_unlocked
void scan_integer( int* o )
{
    register int c = gc();
    int x = 0;
    for( ; ((c<48 || c>57)); c = gc() );

    for( ;c>47 && c<58; c = gc() ) {
        x = (x << 1) + (x << 3) + c - 48;
    }
    *o = x;
}

Wersja dla wszystkich int (ujemnych i dodatnich):

#define gc getchar_unlocked
void scan_integer( int* o )
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for( ; ((c<48 || c>57) && c != '-'); c = gc() );
    if( c=='-' ) {
        neg=1;
        c=gc();
    }
    for( ;c>47 && c<58; c = gc() ) {
        x = (x << 1) + (x << 3) + c - 48;
    }
    if( neg )
        x=-x;
    *o = x;
}

Przykład wczytania i wyświetlenia wszystkich int’ów z wejścia dla czystego C z podstawową biblioteką 'stdio.h’:

int main()
{
	int liczba;
	while(!feof(stdin))
	{
		scan_integer(&liczba);
		printf("%d ", liczba);
	}
	return 0;
}

Czas wykonania algorytmu na spox z wczytywaniem metoda:
cin >> x; = 0,7 sec
fscanf(stdin, „%d”, &x); = 0,27 sec
scan_integer(&x); // z 'getchar’ = 0,11 sec!
scan_integer(&x); // z 'getchar_unlocked’ = 0,03 sec!

Więcej informacje na temat: http://stackoverflow.com/a/25388170/4047081