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
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!
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.
1) posix to nie standard ani C ani C++
2) tłumaczenie błędów ortograficznych przez to, że w google pokazywane jest w ten sposób – boskie. Oddzielanie apostrofem jest błędem ortograficznym.
haters gonna hate.
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…
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.
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.
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.