[ASD] Spox, Spoj, szybkie wczytywanie int’ów w C

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

Ten wpis został opublikowany w kategorii PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

8 odpowiedzi na „[ASD] Spox, Spoj, szybkie wczytywanie int’ów w C

  1. Kaczus pisze:

    1) funkcja ‚getchar_unlocked’ nie jest funkcją standardową, moim zdaniem użycie przy rozwiązywaniu zadań powinno dyskwalifikować rozwiązanie.
    2) naucz się stosować apostrof!!! Oczy bolą jak widzę intów (ewentualnie int-ów) z apostrofem!

    • Jerzy Skalski pisze:

      1) Nie jest standardową? To dlaczego jest w standardzie POSIX.1 [ http://www.unix.org/whitepapers/reentrant.html ] ? W ten sposób można by powiedzieć, że nie należy korzystać z żadnych bibliotek, bo ‚nie są w standardzie’.
      Standardy, czystość kodu, używany język (może być i assembler) się nie liczy, liczy się tylko czas wykonania.
      Jak jakiś kod może skrócić czas wykonywania programu o 10-50%, a zaliczenie przedmiotu może zależeć od kilku nadmiarowych tików zegara to chyba każdy skorzysta.
      Na stronie jest trochę kodów które korzystały z scanf i cin, zadania są ciągle podobne, ale ilość danych i czas na przetworzenie się co semestr zmienia, wiec innego wyjścia już nie ma jak ciąć czas każdym możliwym sposobem.

      2) szybkie wczytywanie int – drugie miejsce w google [tej strony]
      szybkie wczytywanie intów – pierwsze miejsce w google
      szybkie wczytywanie int’ów – pierwsze miejsce w google
      Jak działa google nie wiem, ale wole część ‚int’ oddzielać od reszty.

  2. pytanko pisze:

    mam pytanie, czy while(!feof(stdin)) tutaj zadziala? u mnie przy uzyciu void scan_integer( int* o ) petla zaczytujaca niestety wisi i nie przechodzi do dalszej czesci programu… po wprowadzeniu ctrl+z…

  3. Szukałem tego 2 tygodnie pisze:

    SPOX stoi na czymś pochodnym unixa więc najbardziej opłaci się użycie funkcji read() wczytującej dane do bufora.
    Przykład:

    #include stdint.h // do testowania na windowsie
    #include unistd.h // do typów fast
    #define BUFF_SIZE 10080000

    int main(){
    uint_fast64_t a=0;

    char buff[BUFF_SIZE];
    int re = read(0, &buff, BUFF_SIZE);

    //wczytanie jednej nieujemnej l. całkowitej:
    for(;buff[i]>=48;++i){
    a= 10*a + buff[i]-48;
    }
    }

    W ten sposób można np. w zadaniu 1 mieć 0.02 – taki wynik mam.
    Dla ambitnych: wypisywanie przez write() nic nie da.

    *ps. i tak to nic wam pewnie nie da bo na końcu jest rywalizacja na punkty nie na czas.

    • Jerzy Skalski pisze:

      Bez szybkiego wczytania danych można mieć zero punktów. Samo wczytywanie kilku MB danych ‚cin’ może doprowadzić do przekroczenia czasu mimo dobrej struktury danych i algorytmu.

      • Szukałem tego 2 tygodnie pisze:

        Ale z dobrym algorytmem i jedną linijką:
        cin.sync_with_stdio(false);
        można cin używać.

        Tak robię z dalszymi zadaniami bo lepiej się skupić na algorytmie a nie na tym jak dobrze wczytać dane w zadanym formacie.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *