Chciałbyś poznać kilka sztuczek, którymi możesz zaskoczyć swoich znajomych? Bierzesz udział w konkursach programistycznych, w których wymagane jest szybkie rozwiązanie problemu, a następnie szybkie zakodowanie rozwiązania? Język C++ kryje wiele ciekawych i intrygujących ciekawostek, o których wiedzą tylko doświadczeni programiści. Sztuczki te polegają na wykorzystaniu mało znanych cech języka. Optymalizacyjne natomiast – cech procesora. Chcesz je poznać? Przeczytaj ten wpis i poszerz swoje horyzonty wiedzy.
Iteracja przez ciąg znaków (C style array)
Na każdym punkcie podkreślam, aby do minimum ograniczyć używanie starych tablic w stylu języka C. O wiele lepsze są vectory. Programowanie z użyciem zwykłych tablic prędzej czy później może doprowadzić do pewnych problemów, (takich jak undefined behavior) których rozwiązanie z pewnością pochłonie pewną ilość cennego czasu. Niestety, zdarzają się sytuacje kiedy musisz ich użyć. Przypuśćmy, że tworzysz aplikację na urządzenie wbudowane (np.: na procesorek archirektury AVR). Ilość pamięci którą masz do dyspozycji jest bardzo ograniczona. Natomiast zadanie, które wykonuje twój układ wymaga od ciebie iteracji przez cały ciąg znaków i dla każdego znaku wykonania jakiejś operacji.
95% programistów rozwiązałoby ten problem w następujący sposób:
// wypełniamy tablicę array czymś
int length = strlen(array);
for(int i = 0;i<length;++i) {
// wykonujemy jakąś operację
}
Rozwiązanie jest dobre i działa. Ale zauważ, że marnujemy co nieco czasu na wywołanie funkcji strlen(). Czy to jest naprawdę konieczne? Wydaje się, że tak. Skąd w innym wypadku będziemy wiedzieli jak długo przeglądać tablicę oraz gdzie znajduje się jej koniec? Ten tok rozumowania nie jest do końca optymalny. Aby znaleźć najlepsze rozwiązanie, musimy najpierw przeanalizować jak ciągi znaków przechowywane są w pamięci komputera.
„Tablica” to po prostu wskaźnik na komórkę zawierającą pierwszy jej element. Ten wskaźnik nie wie nic o tym, jak dużą ilość danych przechowujemy. Ale nie wszystko stracone! Posiadamy informację o tym, gdzie dany ciąg znaków się kończy, gdyż każdy z nich w języku C/C++ jest zakończony specjalnym tzw. null termination: /0. Czym jest null termination? To po prostu komórka pamięci wypełniona zerami.
Czy musimy znać długość ciągu znaków jeśli i tak chcemy przejrzeć go całego, znak po znaku? NIE!. Co w takim wypadku musimy zrobić? Zamiast używać niewydajnej funkcji strlen(), wystarczy odpowiednio zmodyfikować warunek pętli for.
// wypełniamy tablicę array czymś;
for(int i = 0;array[i];++i) {
// wykonujemy jakąś operację
}
Warunkiem zakończenia pętli jest array[i]. Nie przyrównujemy tego do niczego, więc jak to właściwie działa? W C++ zero jest fałszem. Pozostałe wartości są prawdą. A więc warunek będzie spełniony i pętla będzie działała dopóty, dopóki array[i] będzie różne od zera. W momencie, gdy array[i] będzie równe zero (a więc wtedy gdy dojdziemy do null terminated) pętla zostanie przerwana.
Oszczędzamy czas – pisząc mniej kodu. Teoretycznie oszczędzamy moc obliczeniową – nie wywołując nadaremno funkcji strlen(). Wadą jest nieco większe zaciemnienie kodu – warunek który umieściliśmy w pętli nie musi być zrozumiały dla osobnika czytającego nasz kod na pierwszy rzut oka. Ale to nie wszystko, co kryje C++.
Krótszy zapis dla x!=-1
Następna sztuczka ma charakter typowo „zabawowy” i raczej nie powinna być używana w praktyce, gdyż nieco zaciemnia kod :).
Programując, tworząc jakąś większą aplikację na pewno korzystasz z funkcji API udostępnianych przez system operacyjny lub inne biblioteki. Niestety, C++ ma nieco „upośledzony” system obsługi sytuacji wyjątkowych. Większość funkcji API np.: systemu Linux nie korzysta z systemu wyjątków wbudowanego w język. Zamiast tego zwraca -1 w przypadku niepowodzenia. Zawsze powinniśmy obsłużyć takie sytuacje, nawet jeśli prawdopodobieństwo ich zaistnienia jest bardzo niskie. Przecież nigdy nie wiadomo, jakie informacje na wejście programu poda jego użytkownik 🙂
A jak obsłużyć je w najprostszy sposób? Oczywiście zapisać wynik zwracany przez funkcję i sprawdzić czy nie jest on równy -1.
Logika podpowiada, że najprostszy sposób wykonania tej operacji jest następujący:
if(x!=-1)
cout<<"Nowy proces został utworzony!!!. Yupi :)"<<endl;
Obecnie zapis instrukcji warunkowej sprawdzającej czy udało się utworzyć proces liczy aż 5 znaków! Możemy go skrócić aż o 3 znaki. W jaki sposób?
Przypomnij sobie, jak wygląda zapis liczby -1 w systemie liczbowym U2. Spokojnie, jeśli nie pamiętasz to ci przypomnę 🙂
-1 w systemie dziesiętnym to 11111111 w U2.
Co się stanie jeśli zastosujemy negację bitową? Wszystkie jedynki zamienią się na zero. A więc w systemie dziesiętnym zmienna także będzie miała wartość równą zero. Pamiętamy, że warunek w C/C++ jest niespełniony wtedy kiedy wartość zmiennej wynosi 0. W każdym innym wypadku jest spełniony.
Tym samym wiemy już, jak możemy skrócić zapis:
if(~x)
cout<<"Nowy proces został utworzony!!!. Yupi :)"<<endl;
Jeśli chcemy sprawdzić, czy coś jest równe -1, możemy skorzystać z takiego, tym razem trzy znakowego zapisu:
if(!~x)
cout<<"Utworzenie nowego procesu nie powiodło się"<<endl;
Szybkie sprawdzanie parzystości
Sprawdzenie parzystości liczby jest osią wielu algorytmów. Jest to zatem bardzo często wykonywana operacja. Skutki jej „powolności” odczuwamy tym bardziej, im większe są dane wejściowe napisanego programu. Co zatem możemy zrobić, jako dobrzy programiści aby rozwiązać ten niecierpiący zwłoki optymalizacyjny kłopot?
W szkole uczą nas aby sprawdzać parzystość liczby w następujący sposób:
if(toCheck%2) cout<<"Liczba nieparzysta"<<endl;
Powyższy sposób działa i to wyśmienicie. Problem w tym że jest niesamowicie wolny. Operator modulo opiera się na dzieleniu. A procesory strasznie nie lubią dzielić. Najlepiej i najszybciej im wychodzi dodawanie, odejmowanie liczb całkowitych oraz wykonywanie operacji logicznych …
I to właśnie jest klucz do sukcesu!
Zastanów się, czym różni się parzysta liczba od nieparzystej w systemie binarnym? Porównajmy kilka:
1100 = 6(dec)
11110 = 30(dec)
111 = 7(dec)
100001 = 33(dec)
Zauważyłeś jakąś ciekawą własność? Liczby parzyste na pozycji LSB (najmniej znaczącego bitu) mają wartość 0, a liczby nieparzyste 1. Oczywiście, porównanie kilku liczb ze sobą nie stanowi matematycznego dowodu, ale ten łatwo znajdziesz sobie w Internecie 🙂 Jak możemy to wykorzystać?
Po prostu sprawdzajmy za pomocą operatora sumy logicznej, czy na pozycji LSB jest 0 czy 1.
if(toCheck&1) cout<<"Liczba nieparzysta"<<endl;
O ile powyższy kod jest szybszy od „szkolnego”? Nie przeprowadzałem osobiście testów, ale wiarygodne źródła mówią że różnica duża – rzędu 50% (w języku C). Warto zastanowić się nad stosowaniem tej reguły. Różnica w czytelności kodu oraz w jego długości jest żadna. Nie jesteśmy natomiast zależni od jakości kompilatora, który może – ale nie musi – optymalizować operatora modulo.
Jednolinijkowy IF
Jest wiele styli formatowania kodu. Niektórzy umieszczają klamrę w tym samym wierszu w którym znajduje się sygnatura funkcji. Inni robią enter i umieszczają klamrę w kolejnym wierszu. Niektórzy krótkie ify piszą w jednej linijce (warunek+reakcja), inni rozbijają to na dwie linijki (w jednej warunek, w drugiej reakcja).
Osobiście jestem zwolennikiem jak najbardziej zwięzłego kodu. Uważam, że nie warto bez powodu „rozwijać kodu wzdłuż”. Rezultat zadziałania instrukcji warunkowej – jeśli jest on krótki – umieszczam w tej samej linijce w której znajduje się instrukcja warunkowa.
Wydaje się, że C++ stawia nam pewne ograniczenie. Spójrz na poniższy kod:
1 2 3 4 | int a = 5; int b = 0; int c = 0; if(a==6) b++; c++; |
Zwróć uwagę na linijkę czwartą, w której znajduje się nasza instrukcja warunkowa. Jeśli warunek będzie prawdziwy, obie instrukcje się wykonają: b++ oraz c++. W przypadku, gdy warunek nie będzie prawdziwy b++ się nie wykona. Niestety inkrementacja zmiennej c dojdzie do skutku, gdyż jest to „kolejna” instrukcja po instrukcji warunkowej i formalnie od niej nie zależy. Nie ma znaczenia, że umieszczona jest w tym samym wierszu co instrukcja warunkowa.
Najprostszym rozwiązaniem wydaje się użycie klamer. Ale założyliśmy, że nie chcemy ich używać. Jest inne rozwiązanie, o którym być może nie masz pojęcia. Instrukcje języka c++ możemy rozdzielać za pomocą przecinka.
1 2 | int a=5,b=0,c=0; if(a==6) b++,c++; |
Dzięki poznaniu tej, pozornie nic nieznaczącej, możliwości języka C/C++ udało nam się zmniejszyć objętość naszego kodu do dwóch linijek. Niebywale! Co najważniejsze, kod teraz działa prawidłowo.
Wadą tego sposobu jest następująca. W tak skonstruowanej instrukcji warunkowej nie możemy umieszczać słów kluczowych zmieniających przepływ sterowania programu, takich jak return, break czy continue. W takim wypadku niestety jesteśmy skazani na dodanie nawiasów klamrowych oraz średników.
(C) Niestandardowe wypełnienie tablicy za pomocą scanf
scanf(), podobnie jak wielu innych funkcji języka C nie powinniśmy używać gdy programujemy w C++. Możemy złamać tę zasadę tylko wtedy, gdy nastąpi taka konieczność, co zdarza się bardzo rzadko. Jednakże jeśli piszemy w języku C, nie mamy innej możliwości pobrania danych od użytkownika jak stary dobry scanf.
Jak w najprostszy sposób wypełnić tablicę?
for(int i = 0;i<100;++i) scanf("%d",&a[i]);
Takiego sposobu pewnie uczyli cię w szkole lub na studiach. Nie jest on zły – prosty i działa.W tym wypadku musimy użyć operacji „pobrania” adresu (symbol &). Ten sam kod możemy zapisać w nieco inny sposób, który zniweluje konieczność użycia tego operatora.
for(int i = 0;i<100;++i) scanf("%d",a+i);
Korzystamy tu z wielokrotnie wspominanej cechy tablic języka C/C++. Możemy przyjąć, że tablica jest tak naprawdę wskaźnikiem na jej pierwszy element. Jeśli do tego wskaźnika dodamy wartość indeksu, otrzymamy adres elementu znajdującego pod danym indeksem. Dzięki temu scanf może szybko i bezproblemowo zapisać tam wynik swoich operacji.
Dodatkowy sposób na określenie konkretnego elementu tablicy
Warto przy tej okazji wspomnieć o kolejnej mało znanej właściwości języka C/C++. W poprzednim rozdziale udowodniliśmy, że zapis a[i] możemy w niektórych wypadkach zamienić na a+i . Istnieje jeszcze jedna możliwość zapisu elementu tablicy.
Dodawanie i mnożenie, jak zapewne wiemy jeszcze ze szkoły podstawowej, są działaniami przemiennymi. Czy to oznacza, że np.: zapis a[5] możemy zamienić na 5[a] ? Oczywiście 🙂
Poniższy listing prezentuje wszystkie trzy możliwości zapisywania i odczytywania elementów znajdujących się pod konkretnymi indeksami.
scanf("%d",a); // element pod indeksem 0 w tablicy
scanf("%d",&a[1]);
scanf("%d",&2[a]);
scanf("%d",a+3);
for(int i = 0;i<4;i++) printf("%d ",*(a+i)); // korzystamy z dereferencji gdyż printf potrzebuje wartości elementu, a nie adresu
DLC: Zamiana wartości zmiennych bez zmiennej tymczasowej
Wiem, że miało być 5 sztuczek, więc potraktujmy ten ostatni punkt jako darmowy „DLC” 🙂
W wielu algorytmach, a szczególnie w algorytmach sortowania musimy zamienić ze sobą wartości dwóch zmiennych. Najprościej wykonać tę czynność za pomocą zmiennej tymczasowej:
int b = 48;
int temp = a;
a = b;
b = temp;
Zamieniając wartość zmiennych ze sobą, w pewnym momencie musimy nadpisać zawartość jednej z nich wartością drugiej. Abyśmy nie utracili informacji, nadpisywane dane musimy przechować w zmiennej tymczasowej.
Wydaje się, że nie ma żadnej możliwości ominięcia potrzeby użycia zmiennej tymczasowej. A może jednak? Kilka razy udowodniliśmy już, jak przydatne w informatyce są operacje bitowe. Okazuje się, że przy czynności takiej jak zamiana liczb one także mogą nam bardzo pomóc.
a = a ^ b;
b = a ^ b;
a = a ^ b;
Wykonujemy trzy razy operację XOR (alternatywy wykluczającej). Jak to działa?
Alternatywa wykluczająca, jak pamiętamy, daje wartość jeden tylko wtedy gdy jeden z argumentów jest równy jeden a drugi zero. Operacja ta daje na wyjściu wartość zero w każdym pozostałym wypadku. Przeanalizujmy więc algorytm:
| a | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 24 |
| b | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 |
| a=a^b | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 40 |
Taką wartość przyjmie zmienna a w drugiej linijce. Hmmm – jesteśmy nieco daleko od prawidłowego wyniku. Zobaczmy jednak co będzie się działo dalej!
| a | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 40 |
| b | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 |
| b=a^b | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 24 |
Wow! Otrzymaliśmy już prawidłowy wynik dla zmiennej b!.
| a | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 40 |
| b | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 24 |
| a=a^b | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 |
Do zmiennej a również trafiło to co powinno trafić.
Użycie operatora XOR jest nieco szybsze i bardziej oszczędne jeśli chodzi o pamięć od używania zmiennej tymczasowej. Dlatego polecam poeksperymentować 🙂
To by było na tyle 🙂
To wszystko, co chciałem wam przekazać w dzisiejszym artykule. Mam nadzieję, że nauczyliście się wielu ciekawych i interesujących życie, a wasze programowanie stanie się szybsze i przyjemniejsze 🙂
Jeśli chcesz być na bieżąco informowany o nowych wpisach, kliknij ikonkę „dzwoneczka” w lewym dolnym rogu. Dzięki temu dostaniesz powiadomienie natychmiast po tym, jak nowy artykuł zostanie tutaj opublikowany 🙂
Polub także mojego fanpage’a na którym często umieszczam różne ciekawostki 🙂
Dzięki za lekturę i powodzenia 🙂
Fajna rozrywka 🙂