The wind of change
Ostatnio trochę zaniedbałem tego bloga, jednak tym krótkim wpisem postaram się zacząć trochę zmian.
Obecnie zajmuję się (poza oczywiście studiowaniem) rozpisywaniem w Javie mojego mało nowoczesnego ale dla niektórych być może przydatnego projektu jakim jest unigglib – uniwersalna biblioteka Gadu-Gadu. Na jej bazie postaram się stworzyć coś, czego prototyp jest pisany w Delphi (z konieczności – projekt na przedmiot „Podstawy Programowania”) a co docelowo ma stać się aplikacją Androidową – multikomunikator z obsługą kilku różnych protokołów w tym GG i XMPP.
Wkrótce (weekend/następny tydzień) postaram się dodać zmianę języka na blogu i wpisy będą pojawiać się w przynajmniej dwóch wersjach: angielskiej i polskiej. Szkoda byłoby marnować znajomość języka 
Oprócz tego przeanalizowałem to jak tutaj trafiacie – postaram się odpowiedzieć na część pytań które was tutaj sprowadzają, mam nadzieję że będzie to w jakiś sposób pomocne.
Być może piszę trochę bez ładu i składu ale akurat szykuję się do wyjazdu i usiłuję jak najszybciej to napisać (nie ma to jak odkładać coś na ostatnią chwilę). Jeśli o czymś zapomniałem, to poprawię to jak wrócę – tymczasem zachęcam do przeglądania wpisów i komentowania jeśli czegoś brakuje lub chcielibyście aby coś dodać.
z góry dzięki za feedback,
hun7er
Analiza pakietów protokołu Gadu-Gadu
Jakiś czas temu przy okazji tworzenia systemu powiadomień przez e-mail i wspomniany protokół GG postanowiłem stworzyć własną bibliotekę opartą o opis libgadu (http://toxygen.net/libgadu/protocol/). O ile odebranie informacji o serwerze nie sprawiało mi problemu o tyle z jakiegoś powodu (może zmęczenie?) trochę czasu spędziłem nad niektórymi pakietami i ustalaniu jak to właściwie działa. Jeżeli sami macie tego rodzaju problemy lub po prostu jesteście zainteresowani jak to działa to zapraszam do czytania – ostrzegam tylko, że przedmiotem analizy są pakiety wersji ~8.x gdzie nie było jeszcze stosowane wysyłanie via SSL.
Kwaterniony
Miło mi przedstawić wam drugą część artykułu dodanego wcześniej – w tej części zajmę się opisaniem działań na kwaternionach, więc jeśli nie przeczytaliście poprzedniej to radzę wam to zrobić – będę wielokrotnie się odwoływał do pojęć które starałem się tam opisać.
Jeśli jesteście już gotowi, to zapraszam – trochę będzie tego
Algorytmy sortowania – zestawienie
Jednym z najciekawszych problemów w informatyce jest sortowanie zbiorów danych – czynność na co dzień oczywista a jednak nie taka prosta do zrealizowania z punktu widzenia programisty. Z realizacją większych problemów nie ma, jednak problemem jest już uzyskanie satysfakcjonującej efektywności, tj. posortowania danych w jak najkrótszym czasie.
Postaram się w tym wpisie zestawić ze sobą kilka najpopularniejszych* algorytmów sortowania i ich efektywności. Aby testy były bardziej wiarygodne, przeprowadzone zostały w dwóch konfiguracjach, w trybie debug (dłuższy czas działania), z zakresem losowanych danych przekraczającym wielkość zbioru (aby zwiększyć prawdopodobieństwo uzyskania nieposortowanego zbioru o dużej różnorodności) oraz na komputerach nie obciążonych dodatkowymi zadaniami.
* wykorzystałem tylko algorytmy proste w implementacji ze względu na brak czasu i dlatego właśnie w zestawieniu nie pojawia się np. sortowanie przez kopcowanie
Na początek postaram się krótko opisać każdy algorytm.
Jeżeli jednak chcesz pominąć wstęp i przejść od razu do statystyk, kliknij tutaj.
Sortowanie bąbelkowe
Jest to jeden z najprostszych i jednocześnie najbardziej czasochłonnych algorytmów sortowania. Polega ono na porównywaniu ze sobą elementów i jeśli jeden jest mniejszy/większy od drugiego (zależnie od tego czy sortujemy rosnąco/malejąco) to zamianie ich miejscami. Jednym z najczęściej stosowanych „trików” optymalizacyjnych jest dodanie zmiennej pomocniczej pozwalającej sprawdzić czy została dokonana zamiana – jeśli po przejściu pętli przez cały zbiór nie zamieniono żadnego elementu to zbiór jest posortowany.
Sortowanie koktajlowe
Jest to odmiana sortowania bąbelkowego. Zasady działania są podobne, z tym że przy jednym przebiegu pętli sprawdzamy zbiór z dwóch stron stopniowo zbliżając się do środka. Pozwala to uzyskać wyniki podobne do sortowania przez wstawianie o którym będzie mowa za chwilę.
Sortowanie przez wybór
Algorytm sortowania przez wybór to najwydajniejszy z algorytmów o złożoności 
Sortowanie przez wstawianie
Algorytm sortowania przez wstawianie jest efektywny dla małych zbiorów lub większych i częściowo posortowanych. Jego działanie polega na stopniowym przenoszeniu ostatniego elementu podzbioru na jego właściwe miejsce – sprowadza się to do porównywania tego elementu z innymi i przenoszeniu na jego docelową pozycję.
Sortowanie szybkie
Jak sama nazwa mówi, jest to najszybszy (najefektywniejszy) algorytm sortowania który dziś opisuję, jego złożoność wynosi 
Pora na trochę danych statystycznych.
Wyniki, aby były czytelniejsze, przedstawiam w tabelce oraz na wykresie.
Konfiguracja I:
| System operacyjny | Windows 7 Ultimate x64 |
| Procesor | AMD Phenom II X4 @ 3.9 GHz |
| Pamięć | 8GB DDR3 |
Konfiguracja II:
| System operacyjny | Windows 7 Ultimate x64 |
| Procesor | Intel Celeron E1200 1.60GHz @ 2.32GHz |
| Pamięć | 2GB DDR2 |
Wyniki
Dla konfiguracji I:
| n | szybkie | wybór | wstawianie | koktajlowe | bąbelkowe |
|---|---|---|---|---|---|
| 5000 | 00:00:00 | 00:00:01 | 00:00:02 | 00:00:01 | 00:00:03 |
| 7500 | 00:00:00 | 00:00:02 | 00:00:04 | 00:00:03 | 00:00:06 |
| 10000 | 00:00:00 | 00:00:04 | 00:00:08 | 00:00:07 | 00:00:12 |
| 30000 | 00:00:00 | 00:00:36 | 00:01:12 | 00:01:03 | 00:01:50 |
| 50000 | 00:00:00 | 00:01:42 | 00:03:21 | 00:02:15 | 00:05:05 |
| 75000 | 00:00:00 | 00:03:51 | 00:07:33 | 00:06:35 | 00:11:32 |
| 100000 | 00:00:00 | 00:06:50 | 00:13:31 | 00:11:48 | 00:20:23 |
Zestawienie algorytmów sortowania w konfiguracji I
Dla konfiguracji II:
| n | szybkie | wybór | wstawianie | koktajlowe | bąbelkowe |
|---|---|---|---|---|---|
| 5000 | 00:00:00 | 00:00:04 | 00:00:07 | 00:00:06 | 00:00:12 |
| 7500 | 00:00:00 | 00:00:08 | 00:00:18 | 00:00:14 | 00:00:25 |
| 10000 | 00:00:00 | 00:00:17 | 00:00:31 | 00:00:27 | 00:00:46 |
| 30000 | 00:00:00 | 00:02:24 | 00:04:57 | 00:04:18 | 00:07:18 |
| 50000 | 00:00:01 | 00:07:01 | 00:13:35 | 00:12:18 | 00:21:21 |
| 75000 | 00:00:01 | 00:16:54 | 00:32:13 | 00:26:39 | 00:49:59 |
| 100000 | 00:00:01 | 00:28:36 | 00:57:00 | 00:51:45 | 01:34:09 |
Zestawienie algorytmów sortowania w konfiguracji II
Podsumowanie
Jak widać zdecydowanym liderem jest sortowanie szybkie, co do tego nie ma najmniejszych wątpliwości. Zaskoczył mnie jednak wynik sortowania koktajlowego, którego okazało się osiągać lepsze wyniki od sortowania przez wstawianie (minimalne ale jednak). Najlepszym z algorytmów sortowania poza sortowaniem szybkim okazało się być porządkowanie przez wybór – proste i, jak widać, wydajne.
Nie mogłem tego pokazać w teście, jednak w przypadku małych zbiorów lub częściowo uporządkowanych od sortowania szybkiego lepsze jest właśnie sortowanie przez wstawianie – jako jedno z ulepszeń sortowania szybkiego można zastosować sortowanie małych podzbiorów wstawianiem i/lub dodanie pętli kontrolnej jak w sortowaniu bąbelkowym i koktajlowym – co do ulepszeń do ogranicza nas tylko i wyłącznie nasza wyobraźnia; zachęcam więc do eksperymentowania
Swoją drogą – wielkie dzięki dla mug3tsu za udostępnienie maszyny do testów oznaczonej jako II, bez tego ciężko by było wiarygodnie porównać te algorytmy ze sobą 
Zadanie 5 – kalendarz
Treść zadania znajdziecie tu: link!
Największą trudnością były obliczenia ręczne z których dopiero wyłaniał się właściwy pomysł na kod – zadanie nie jest nadzwyczaj trudne choć takim się wydaje na pierwszy rzut oka Wymaga jednak pomyślenia i rozpisania na spokojnie pomysłu i dopiero zrealizowania go w kodzie.
Kod źródłowy pisany oczywiście w C++, mam nadzieję że jako-tako zrozumiały – jeśli gdziekolwiek jest błąd to piszcie śmiało w komentarzach
zad5.cpp :
#include <iostream> #include <string> using namespace std; int czyPrzestepny (int rok) { if (rok <= 1582) { return (rok % 4 == 0) ? true : false; } else { if (rok % 4 == 0) { if (rok % 100 == 0 && rok % 400 != 0) return false; else return true; } else return false; } } int jakiDzien (int start, int ile) { return (start + ile % 7) % 7; } int main() { string tydzien[7]; // dni tygodnia z odpowiadającymi im numerami id // kolejne dni tygodnia tydzien[0] = "poniedzialek"; tydzien[1] = "wtorek"; tydzien[2] = "sroda"; tydzien[3] = "czwartek"; tydzien[4] = "piatek"; tydzien[5] = "sobota"; tydzien[6] = "niedziela"; int start = 0, ile = 0; for (int i = 1500; i < 1582; i++) { // lata <1500, 1582) if (czyPrzestepny(i)) ile += 366; else ile += 365; } for (int i = 1; i < 10; i++) { // styczeń - październik 1582 if (i != 7 && i != 8) { if (i % 2 == 0) ile += 30; // nieparzyste lata mają 30 dni else ile += 31; // a parzyste 31 } else ile += 31; // ...poza lipcem i sierpniem } int od = ile; int rok = 0, dz = 0; string dzien(""); bool poprawny = false; do { cout << "podaj dz. tygodnia: "; cin >> dzien; cout << "podaj rok: "; cin >> rok; poprawny = true; if (dzien == "poniedzialek") dz = 0; else if (dzien == "wtorek") dz = 1; else if (dzien == "sroda") dz = 2; else if (dzien == "czwartek") dz = 3; else if (dzien == "piatek") dz = 4; else if (dzien == "sobota") dz = 5; else if (dzien == "niedziela") dz = 6; else { poprawny = false; cout << "BLAD! Niepoprawny dzien tygodnia" << endl; } if (rok < 1500 || rok > 2005) { poprawny = false; cout << "BLAD! Rok powinien zawierac sie w zakresie <1500, 2005>" << endl; } cout << endl; } while (!poprawny); if (rok > 1582) { ile = 119; // 27 (31-4 z października) + 30 (listopad) + 31 (grudzień) i + 31 (styczeń - od razu żeby nie zaśmiecać kodu) for (int i = 1583; i < rok; i++) { // lata <1500, 1582) if (czyPrzestepny(i)) ile += 366; else ile += 365; } cout << "Odp:" << endl; for (int i = 0; i < (czyPrzestepny(rok) ? 29 : 28); i++) { // od 1 lutego do ostatniego dnia miesiąca... if (jakiDzien(1, ile+i) == dz) { // ...jeśli aktualny dzień tygodnia to ten szukany... if (i+1 < 10) cout << "0"; cout << i+1 << ".02." << rok << endl; // ...to wypisz go na std::out } } //cout << "1 lutego " << rok << " byl " << tydzien[jakiDzien(1, ile)] << endl; } else { ile = 32; // 31 za styczeń + 1 bonusowy od papieża. for (int i = 1500; i < rok; i++) { // lata <1500, 1582) if (czyPrzestepny(i)) ile += 366; else ile += 365; } cout << "Odp:" << endl; for (int i = 0; i < (czyPrzestepny(rok) ? 29 : 28); i++) { // od 1 lutego do ostatniego dnia miesiąca... if (jakiDzien(1, ile+i) == dz) { // ...jeśli aktualny dzień tygodnia to ten szukany... if (i+1 < 10) cout << "0"; cout << i+1 << ".02." << rok << endl; // ...to wypisz go na std::out } } } //cout << "Od 1 stycznia 1500 roku do 1 pazdziernika 1582 minelo dni: " << ile << endl; //cout << "Dzien tygodnia ktory wowczas przypadl to: <<" << tydzien[jakiDzien(1, ile)] << ">>" << endl << endl; cout << endl; system("PAUSE"); return 0; }
