Czas na kolejne zmiany, tym razem nieco bardziej radykalne niż zwykle.
Jako że chcę aby treści tutaj zamieszczane były dobrane zdecydowanie lepiej niż dotychczas co narzuca konieczność odpowiedniego przedstawienia tekstu w formie jak najbardziej czytelnej – niestety żaden ze znajdowanych przeze mnie szablonów nie był odpowiednio… minimalistyczny. A więc, jak widać, utworzyłem własny szablon (bazując na Default WordPressowym) dzięki czemu stworzyłem maksymalnie minimalistyczny, ciemny szablon z jasnym tekstem dzięki czemu powinno się na dłuższą metę lepiej go czytać. Zmianie ulegnie także layout mojej strony domowej która jakiś czas już leży nietknięta a nie mogę na to pozwolić 
Oprócz tego wpisy będą pojawiać się albo tylko po angielsku albo i po angielsku i po polsku (w zależności od sytuacji). Będą one dotyczyć najprawdopodobniej bardziej studiów i doświadczeń programistycznych [devlog] (subdomena ulegnie zmianie z blog.hun7er.pl na devlog.hun7er.pl), tak żeby pomóc innym obecnym i przyszłym studentom aby inni nie powielali moich błędów A zdaję sobie sprawę że o niektórych sprawach często ciężko jest znaleźć polskojęzyczne (albo i anglojęzyczne) źródła.
Szablon nie jest jeszcze skończony co nietrudno zauważyć, jednak myślę że w przyszłym tygodniu (pod koniec) powinienem trochę nad tym posiedzieć i pokończyć wszystko. Obecnie pracuję nad projektem na przedmiot „Programowanie Niskopoziomowe” tj. nad grą platformową stworzoną z wykorzystaniem Allegro 5 w związku z czym postaram się też coś na ten temat naskrobać Do tego przepisuję obiektowo FractalX i mam zamiar zająć się na poważniej raytracingiem i kontynuowaniem Frag::Engine oraz – być może – pewną grą której mam zamiar być współautorem, jednak póki co nie chcę za dużo na ten temat ujawniać. Szkoda tylko że czasu tak mało :/
Mam nadzieję że nie zanudziłem nikogo tym wpisem – kolejne wpisy powinny być już ciekawsze i pisane nieco innym (oby przyjemniejszym do czytania ) stylem. Nie pozostaje mi nic innego niż zachęcić do czytania poprzednich wpisów i komentowania. Do usłyszenia niedługo,
hun7er
Posted in O blogu on Kwiecień 12th, 2012
No comments »
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
Posted in O blogu on Listopad 5th, 2011
No comments »
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.
Read the whole entry »
Posted in Artykuły, Różne on Sierpień 27th, 2011
No comments »
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
Read the whole entry »
Posted in Artykuły, Matematyka on Czerwiec 18th, 2011
No comments »
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 
w dzisiejszym zestawieniu. Jego zasada działania jest stosunkowo prosta: przesuwając się w stronę początku (dla kolejności rosnącej) lub końca (dla malejącej) znajdujemy w podzbiorze ograniczonym tym co już przerobiliśmy minimum/maksimum i przesuwany na koniec/początek podzbioru.
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 
W przeciwieństwie do wersji iteracyjnych które opisywałem wcześniej, sortowanie szybkie jest najczęściej realizowane w swojej naturalnej, rekurencyjnej formie. Sortowanie tym algorytmem polega na wybraniu elementu osiowego (najczęściej w środku zbioru lub losowo), następnie przeniesieniu na prawą stronę wszystkich elementów większych od niego (dla kolejności rosnącej, dla malejącej odwrotnie) i rekurencyjnym wywołaniu funkcji dla zbiorów z lewej i prawej strony elementu osiowego. Pozwala to uzyskać niesamowite wyniki w porównaniu z poprzednimi algorytmami (dla danych z testu algorytm ten uzyskał w konfiguracji I wynik 0 sekund).
Statystyki
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ą 
Posted in Artykuły, C++, Informatyka, Matura, Różne on Maj 15th, 2011
No comments »
