W jakiej bibliotece jest getchar_unlocked() ?

0

Pomimo przepisania mojego programu na printf-y wchodzi on na 99 punktów. Postanowiłem więc skorzystać z funkcji getchar_unlocked(), która rzekomo znajduje się w bibliotece stdio.h
Kompilator wyświetla błąd, że jest ona niezdefiniowana.

0

getchar_unlocked() nie jest funkcją standardową, więc może jej nie być w ogóle w Twoim środowisku. Jeśli to istotny problem, to napisz prostego ifdefa, który zamieni wywołanie getchar na getchar_unlocked na spoju.

0
Roman Kwaśniewski napisał(a):

Pomimo przepisania mojego programu na printf-y wchodzi on na 99 punktów.

Zakładam, że wpadłeś w "urban legend" na temat słabej szybkości strumieni C++.
To jest fikcja. Kiedyś ktoś pokazywał testy, że dobrze użyte strumienie C++ są szybsze od printf.

Jak korzystasz ze strumieni na SPOJ to jest kilka prostych zasad: https://4programmers.net/C/Wy[...]kiej_wydajno%C5%9Bci_iostream

Daj linka do zadania, żebyśmy wiedzieli, że faktycznie wąskim gardłem są operacje IO.

0

To wszystko oczywiście zawsze dodaję. Mało zadań wchodzi na 100 "gołymi" strumieniami, ale co mam zrobić jeśli mimo wszystko program wchodzi na 99. Tylko raz w życiu miałem taki problem ( wtedy była uszkodzona paczka ) Tym razem raczej tak nie jest sądząc po tym, że sporo osób wbiło to na 100.

0

@Roman Kwaśniewski: ja zrobiłem dużo zadań ze spoja, ale cin/cout prawie nigdy nie robiły mi problemów - tylko w przypadku gdy masz b. dużo danych wejściowych, a takich zadań jest dość mało.
Zawsze dodawaj ios_base::sync_with_stdio(false); na początku maina. Ale jeszcze nie miałem zadania żeby mi scanf/print nie wystarczył.

Daj przykładowe zadanie z Twoim rozwiązaniem to damy Ci wskazówki co zmienić żeby przeszło (zakładając że masz poprawne optymalne rozwiązanie - jeśli nie to możemy Cię nakierować żeby nie psuć Ci zabawy)

0

Zadanie jest rozwiązane liniowo. Ponieważ danych też jest liniowo dużo to rozwiązanie jest optymalne. Poza tym program dostaje 99 czyli prawie maksa. Właściwie to w żadnym teście nie ma przekroczenia limitu czasu. Mam tylko odjęte punkty za czas nie-wzorcowy.

0
kq napisał(a):

getchar_unlocked() nie jest funkcją standardową, więc może jej nie być w ogóle w Twoim środowisku. Jeśli to istotny problem, to napisz prostego ifdefa, który zamieni wywołanie getchar na getchar_unlocked na spoju.

POSIX je definiuje. Jednak może być potrzebne zdefiniowanie feature test macros dla nich (jak to się po polsku nazywa?) - te są w Twojej gestii i / lub odp flagi kompilatora - tymi zarządza oczywiście sędzia.

Dokumentacja, która o tym mówi (dla Linuxa): https://linux.die.net/man/3/getchar_unlocked

Na SPOJ próbowałem (w C, nie w C++, ale chyba powinno być tak samo) i działało jeśli przed #include <stdio.h> dałem #define _POSIX_SOURCE. Czyli:

#define _POSIX_SOURCE
#include <stdio.h>

// dalej kod

(jeśli u Cb to nie SPOJ to oczywiście nie gwarantuję, że zadziała, ale warto spróbować IMO)

MarekR22 napisał(a):
Roman Kwaśniewski napisał(a):

Pomimo przepisania mojego programu na printf-y wchodzi on na 99 punktów.

Zakładam, że wpadłeś w "urban legend" na temat słabej szybkości strumieni C++.
To jest fikcja. Kiedyś ktoś pokazywał testy, że dobrze użyte strumienie C++ są szybsze od printf.

Jak korzystasz ze strumieni na SPOJ to jest kilka prostych zasad: https://4programmers.net/C/Wy[...]kiej_wydajno%C5%9Bci_iostream

Zgadza się niemniej getchar_unlocked jest szybszy (chociaż bardziej upierdliwy w obsłudze) zarówno od stdio jak i od strumieni. Są zadania, przy których ich użycie jest jedynym mi znanym sposobem na zdobycie najszybszego możliwego czasu, aczkolwiek nie znam zadania, w których byłoby to warunkiem zdobycia maks punktów (co nie znaczy, że takie nie istnieje - w sumie sumarycznie mało zadań znam).

Roman Kwaśniewski napisał(a):

sporo osób wbiło to na 100.

Może to świadczyć, że jednak da się wbić na 100 bez getchar_unlocked.

Roman Kwaśniewski napisał(a):

Zadanie jest rozwiązane liniowo. Ponieważ danych też jest liniowo dużo to rozwiązanie jest optymalne.

Niekoniecznie. Stała się liczy w takich zadaniach. Złożoność asymptotyczna zresztą w ogóle ma niekiedy znaczenie teoretyczne, bywa tak że teoretycznie lepszy asymptotycznie algorytm ma tak ogromną stałą, że w praktyce jest wolniejszy, niż algorytm o teoretycznie gorszej złożoności. Nie sądzę, by u Cb miało to miejsce, ALE! to pokazuje tylko, jakie czasami znaczenie ma walka o stałą. Zresztą zamiana strumieni czy scanf na getchar_unlocked też ma znaczenie w kwestii stałej tylko. Bottom line: Twój kod może i jest liniowy, niemniej może być nieefektywny. EDIT: Co można zweryfikować, jeśli doczekamy się linka do zadania i Twojego kodu :)

0

Już nie musicie mi pomagać przekroczyłem limit zgłoszeń :)

0

Nie chce mi się wierzyć, że czytanie znak po znaku za pomocą getchar_unlocked będzie szybsze niż czytanie blokami danych (tak zrobi to STL).
Nie uwierzę jeśli ktoś nie zrobi jakiś testów.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0