[C++] Ignorowanie części danych na wejściu.

[Veal]

Mam w ch.. dużo lini danych na wejściu... W każdej z nich liczby x i y. Interesuje mnie tylko y. Da się jakoś pierwszą zignorować? Obecnie poprostu cały czas pierwszą liczbę przypisuje do zmiennej width ale to jest nieoptymalne.

for (unsigned int i=1; i<=n; i++) {
cin >> width >> height[i];
}

Zwłaszcza, że gdyby nie było pierwszej zmiennej mógłbym zrobić poprostu:

cin >> height;

Mogę zrezygnowac ze strumieni, byleby czytało ze standardowego wejścia. Jakieś pomysły?

[Maximus Marius]

A ta optymalizacja to jest sztuka dla sztuki czy też jest jakies racjonalne uzasadnienie ?

np. program za wolno przetwarza dane itp ...

Jak bys nie kombinowałe to i tak zawsze bedzie jakiś kod związany z odczytem albo nie odczytywaniem X

Ewentualnie zoptymalizuj coś innego:

Zamiast odczytywać zmienna po zmiennej odczytaj cały blok danych do bufora a dopiero potem rób przetwarzanie danych

[Veal]

Chodzi mi o zredukowanie czasu potrzebnego na przypisywanie wartości.

Mam 250 000 par liczb, które mogą mieć wartości do 1000000000.

Obecnie wczytuje dane zbyt wolno

[Maximus Marius]

strumień działa niczym plik, jezeli odczytujesz z niego małymi paczkami to dane są wolno odczytywane, jeżeli za jednym zamachem odczytasz paczkę powiedzmy 64kB (lub 1MB) to powinno być szybciej. Przynajmniej zazwyczaj tak było

Czas powinien być w milisekundach dla tak małych ilości danych

[Mion]

Zainteresuj się wskaźnikami, kontenerani np vector, list, map z STL i funkcja for_each znacznie wydajniejszą od pętli.

[kawa]

cin.read(char *buffer, int n)

Reads n bytes (or until the end of the file) from the stream into the buffer.

jeśli na wejściu są dane binarne wystarczy bufor z struktur z dwoma integer rzutować na char* i obliczyć długość n za pomocą sizeof, w przeciwnym wypadku trzeba przeprowadzić konwersję za pomocą atoi pomijając co drugi element.

Należy też uważać na to, że liczby będą poucinane, w tym wypadku trzeba przenieść to co zostało ucięte w poprzedniej operacji odczytu na początek bufora a wskaźnik użyty przy read o odpowiednią ilość bajtów do przodu (zmniejszając n), np.

... 1284|->koniec

^*buffer

przenosimy:

1284

^*bs^*buffer , n=rozmiar_poczatkowy-(buffer-bs)

prawidłowe dane rozpoczynają się od *bs.

STL działa tak wolno, że można się pociąć, podobnie foreach. Dużo wolniejsze od pętli.

jeżeli za jednym zamachem odczytasz paczkę powiedzmy 64kB (lub 1MB) to powinno być szybciej. Przynajmniej zazwyczaj tak było biggrin.gif

Będzie dużo szybciej. Każdy odczyt w języku niskiego poziomu to odwołanie do funkcji systemu operacyjnego.

[Mion]

STL działa tak wolno, że można się pociąć, podobnie foreach. Dużo wolniejsze od pętli.

To poczytaj sobie w książce "C++ dla programistów gier" na temat wydajności kontenerów z STL i o for_each strona 244, bo nie chce mi sie przepisywać...

[kawa]

Masz może linka albo dysponujesz skanem? Nie będę zamawiał z księgarni a zastanawiam się czy faktycznie takie głupoty tam piszą

Co do wydajności STL powiem tyle, że przepisywałem pewien projekt z klas MFC na kontenery STL. Program który wcześniej generował drzewo binarne pół minuty na STL wymagał ~5 minut na zrobienie tego samego. Chociaż może to być winą kompilatora microsoft w pierwszym wypadku, minGW w drugim.

[Mion]

Niestety skanu nie mogłem zrobić, ale zrobiłem zdjęcie {trochę słabe} fragmentu książki o wydajności STL.

Nie będę tu polemizował czy autor pisze głupoty, ale nie wydaje mi się żeby na na codzień zajmował się wypiekiem pączków

[Mion]

Zalety blokady edycji -> sory za post pod postem

Chociaż może to być winą kompilatora microsoft w pierwszym wypadku, minGW w drugim.

A tak poza tym to wydajność kodu nie zależy od kompilatora tylko platformy sprzętowej na jakiej program jest uruchamiany

To jeszcze jeden cytat z tej książki dla Ciebie

Co prawda STL oferuje użytkownikowi niezrównaną wydajność, ale jeśli źle zostanie zastosowana może to być przyczyną poważnych spowolnień

... Poczytaj sobie ...

[kawa]

Autor pisze o wydajności algorytmów a nie o wydajności kodu. Mało wydajny kod w połączeniu z dobrym algorytmem daje dobre wyniki. Zapomina dodać, że gdyby nie kontenery i STL to wyniki byłyby lepsze.

Pętle można zrealizować wykorzystując 2 instrukcje procesora a narzut na foreach to przynajmniej 20-50 instrukcji. Zastanawiałeś się może, dlaczego w szybkich językach niskiego poziomu zmienne implementuje się bezpośrednio w pamięci a nie np. jako objekty klas. A np. kopiując napis używa się pętli a nie foreach. Dlaczego języki w których wszystko jest objektem tak się ślimaczą? No właśnie.

cin to typowe podejście foreach: pobierz następny znak, przetwarzaj

podejście na pętli: weź 40kb do bufora i przetwórz każdy adres w pamięci.

A tak poza tym to wydajność kodu nie zależy od kompilatora tylko platformy sprzętowej na jakiej program jest uruchamiany

To po co optymalizacja w kompilatorach? Po co kompilatory intela których kod szybciej się wykonuje na ich procesorach?Wydajność kodu zależy tylko i wyłącznie od skali problemu (liniowa, logarytmiczna, wykładnicza, etc.) i w dość niewielkim stopniu od optymalizacji. Wydajność sprzętu jest nieistotna. Jeśli mamy problem liniowy wymaga on N operacji, dla problemu o złożoności wykładniczej będzie ich 2^N.

Algorytm opisujący problem 10000 elementowy o złożoności liniowej rozwiążesz na C=64 w kilka sekund. Taki sam problem o złożoności wykładniczej będzie nierozwiązywalny nawet na najnowszym sprzęcie.

Teraz do problemu podchodzą dwie grupy osób: programista piszący STL i zwykły user. Programista STL znajdzie liniowe rozwiązanie problemu, narzut samej biblioteki, szablonów, etc. dajmy na to 5-20%. "Zwykły człowiek" który nie zna odpowiedniego algorytmu napisze to "na chłopski rozum" - wykładniczo. STL będzie 5-20% wolniejszy niż zoptymalizowany kod, a podejście "na chłopski rozum" będzie wolniejsze 2^(N-1) razy.

Więc jedyne co z tego fragmentu książki wynika to fakt, że STL jest szybki bo ludzie którzy nie umieją pisać algorytmów nie napiszą lepszego algorytmu niż ktoś zaimplementował w STL. Np. normalnie większość osób przy szukaniu znaku napisałaby przeszukiwanie liniowe, ktoś kto się zna - połówkowe. I nie ważne jak bardzo to przeszukiwanie połówkowe będzie niewydajnie napisane - zawsze zadziała szybciej.

Poza tym skala problemu: odczyt danych. To jest jedno odwołanie do systemu operacyjnego które wypełnia danymi blok pamięci. Skala problemu O(1) - jedna operacja. Foreach - skala problemu O(n) - tyle operacji ile bajtów danych chcesz odczytać. Czyli podejście na pętli jest n-1 razy szybsze.

Co prawda STL oferuje użytkownikowi niezrównaną wydajność, ale jeśli źle zostanie zastosowana może to być przyczyną poważnych spowolnień

Świetny cytat... na przykład, kiedy zostanie użyte do czytania pliku bajt po bajcie za pomocą konstrukcji a'la foreach.

Poza tym: MFC ma struktury, które są odbiciem tych w STL więc o "złym zastosowaniu" nie może być w poprzednim przypadku mowy, skoro struktura z MFC została zastąpiona odpowiednikiem, nawet metody miały takie same nazwy.

[Maximus Marius]

To teraz czekam na wyniki autora wątku

Ile razy dało się przyśpieszyć.

[Mion]

@Kawa W kwestii for_each i odczycie zawartości kontenera.

Proponuję Ci przeczytaj przedmiotową książkę i jeśli uważasz, że autor się nie zna i pisze głupoty to napisz do niego...

A skoro uważasz, że jesteś taki dobry w tej kwestii zawsze możesz napisać nowe algorytny do STL z korzyscią dla wszystkich.

[Veal]

To teraz czekam na wyniki autora wątku

Ile razy dało się przyśpieszyć.

Trudno mi teraz powiedzieć ile razy zmalała prędkoć wczytywania danych, ale czas działania całego algo zmalał trzykrotnie. Dzięki wielkie.

[itb]

Zamiast odczytywać zmienna po zmiennej odczytaj cały blok danych do bufora a dopiero potem rób przetwarzanie danych

a w czasie czekania az OS dostarczy dane my bedziemy marnowali czas?

robiac: cat dane| naszprogram, w czasie gdy kolejne dane sa dostarczane my juz dostarczone przetwarzamy

zamiast c++'owych strumieni uzyj c'owego scanfa. bedzie duzo szybciej.