Strona domowa Kamila Korolkiewicza
Porównanie algorytmów sortowania
W okresie przygotowań do przedmiotu Algorytmy i Struktury Danych zaimplementowałem kilka znanych algorytmów sortowania, a następnie napisałem program, który porównuje ich szybkość działania w praktyce.
Myślę, że poniższa tabelka, zawierająca przykładowe wyniki, może okazać się interesująca. Wynika z niej, że ogólnie opłaca się korzystać z gotowego algorytmu sortowania z STL'a, ale jeśli sortujemy liczby całkowite, to najlepszym rozwiązaniem będzie jednak algorytm Radix sort, jeśli będziemy używać liczników ośmiobitowych (tak przynajmniej wynika z poniższej tabeli).
Dane dla n=100000, m=32 (procesor Core2Duo E4300 2.4GHz)
| Algorytm | Czas (s) | Złożoność |
| QSort | 0.0107548 | O(nlogn) |
| QSort (1rek) | 0.0109928 | O(nlogn) |
| QSort (+inssort) | 0.00885715 | O(nlogn) |
| Radix sort 1 | 0.0221621 | O(n*m) |
| Radix sort 4 | 0.00552693 | O(n*m) |
| Radix sort 8 | 0.00283919 | O(n*m) |
| Radix sort 10 | 0.00326935 | O(n*m) |
| XChange Radix sort | 0.0185953 | O(n*m) |
| Heap sort | 0.0134532 | O(nlogn) |
| Merge sort | 0.0209781 | O(nlogn) |
| STL sort | 0.00817416 | O(nlogn) |
| Insertion Sort | 2.10755 | O(n^2) |
Źródła dostępne są
tutaj.
Czytaj dalej...
03-02-2010
Wykład o OpenGL
Pod
tym adresem znajdują się materiały z wykładu jaki poprowadziłem na spotkaniu
Koła Naukowego Informatyków wydziału
Matematyki i Nauk Informacyjnych Politechniki Warszawskiej dnia
7 stycznia 2010.
Znajdują się tam slajdy wykładowe oraz przykładowy framework i przykładowy program (napisany pod system Windows). Streszczę główne rzeczy, o których powiedziałem.
Przede wszystkim zaczęcie pisania aplikacji z użyciem
OpenGL jst bardzo proste. W sieci jest masa gotowych szablonów, które zwalniają nas z zastanawiania się jak inicjować okno i bibliotekę i w dodatku jak to działa "wewnątrz". Z kolei, jeśli używamy np. CodeBlocks, to dostajemy gotowy szablon (File->New->Project...->OpenGL project), który zawiera standardowy kod, jaki jest używany w celu inicjacji okienek. Dalsza zabawa wymaga już głównie znajomości podstawowych funkcji biblioteki
OpenGL (choć oczywiście przyda się podstawowa wiedza na temat WinApi, bystry czytelnik jednak szybko zorientuje się w szablonowym kodzie). Trochę matmy też się przyda, ale jeśli robimy grę 2D, to jesteśmy praktycznie zwolnieni z myślenia :).
Ogólna idea jest prosta. Załóżmy, że chcemy wyświetlić jakieś trójkąty. Musimy zatem zdefiniować
3*liczba_trójkątów wierzchołków w tablicy. Każdy wierzchołek, to z kolei dwie lub trzy współrzędne: (x,y) bądz (x,y,z). Przykładowy kod:
float tablica_wierzcholkow[]=
{
... //tutaj definiujemy wierzcholki
};
//Wlaczamy obsluge wierzcholkow do wyswietlania
glEnableClientState(GL_VERTEX_ARRAY);
//Przekazujemy adres do tablicy wierzcholkow
glVertexPointer(LICZBA_WSPOLRZEDNYCH, GL_FLOAT, 0, (void*)tablica_wierzcholkow);
//Rysujemy trojkaty
glDrawArrays(GL_TRIANGLES, 0, sizeof(tablica_wierzcholkow)/sizeof(float)/LICZBA_WSPOLRZEDNYCH);
//Wylaczamy obsluge wierzcholkow do wyswietlania
glDisableClientState(GL_VERTEX_ARRAY);
...
//Wyswietl wszystko i oproznij bufory
SwapBuffers(hDC);
LICZBA_WSPOLRZEDNYCH to 2 lub 3
tablica_wierzcholkow to po prostu ciąg liczb, które układają się w ciągi wierzchołków (dwójki lub trójki) oraz ciągi trójkątów (analogicznie szóstki lub dziewiątki).
Więcej przykładów w paczce (link na początku).
Czytaj dalej...
09-01-2010
Nowy Rok = Nowe możliwości
Minął właśnie rok... zarówno ten kalendarzowy, jak i również od powstania tej strony, którą życzliwy czytelniku właśnie widzisz przed sobą. Pozwolę sobie na małe podsumowanie :).
Główną ideą założenia witryny było zamieszczenie niepublikowanych nigdy programów jakie zostały przeze mnie do tej pory stworzone. W między czasie powstało także sporo nowych aplikacji, które wymieniam niżej:
- Invaders - gra, w której sterujemy statkiem kosmicznym. W wersji gry na system Symbian 3rd Edition możemy sterować za pomocą ruchu telefonem (o ile posiada akcelerometr).
- freeTetris - w założeniu gra na komórki (z systemem Symbian). Prosta, niewymagająca, grywalna wersja popularnej gry Tetris. Moim zdaniem najgrywalniesza gra jaką napisałem w tym roku :).
- BinFView - prosty program do podglądu plików binarnych i tekstowych (także w wersji na Symbian 3rd Ed).
- StopWatch - prawdopodobnie jedyny darmowy stoper na system Symbian 3rd Ed. Zarówno prosty w obsłudze jak i funkcjonalny.
- VFunc - program który umożliwia rysowanie funkcji opisanych równaniami parametrycznymi w 3D (krzywe i płaszczyzny).
- Fractal applet - pierwszy aplet w Javie: rysowanie fraktali ze zbioru Mandelbrot'a, Julii oraz "Płonącego statku".
Oprócz tego w tegorocznym dorobku muszę uwzględnić programy jakie miałem okazję przygotować w celu zaliczenia zajęć na uczelni. Było to absolutnie fascynujące doświadczenie - nauczyłem się podchodzić do pracy w bardziej usystematyzowany sposób, jednocześnie poznając nowe dziedziny informatyki (m.in. C#, Linux, asembler 8051). Z niektórymi pracami można zapoznać się na
tej stronie.
Obecnie pracuje nad dwoma projektami. Jeden z nich ma szansę okazać się prawdziwą rewolucją, a przynajmniej będzie się cieszyć sporym zainteresowaniem. Drugi jest zdobywaniem nowego doświadczenia ponieważ polega na pracy w zespole... pracujemy nad (pod pewnymi względami) innowacyjną grą.
Mam nadzieję, że zaciekawienie wzrosło :)). Z czasem pojawi się więcej...
Życzę wszystkim zrealizowania wszystkich postawionych sobie celów w Nowym, 2010 roku!
01-01-2010
Kod niezarządzany w C#
Uff... trochę czasu minęło jak patrzę na to kiedy zamieściłem ostatni post. Ale studia rządzą się swoimi prawami - nie na wszystko jest czas. Dzisiaj napiszę krótko o kodzie niezarządzanym (nazywany też kodem nienadzorowanym, unsafe) w C#.
Będzie to trochę w kontekście łączenia C# z C++ (pisałem także o tym kilka postów wcześniej). Cała idea kodu w bloku
unsafe polega na tym, że możemy w nim korzystać swobodnie ze wskaźników w stylu C++. Dostajemy tym samym 3 nowe operatory znane z C++:
&,
* oraz
->. Podam teraz przykład wykorzystania kodu niezarządzanego. Załóżmy że jakaś funkcja z C++ zwraca nam tablicę typu
double. Niestety, gdy będziemy chcieli przekazać ją do kodu w C# przez zwykłe przypisanie, zostanie zgłoszony wyjątek. Kod:
[DllImport("plik.dll")]
static extern double[] Result();
...
double[] A=Result();
nie zadziała nam poprawnie (dla funkcji w C++
double *Result()).
Ale możemy zrobić na przykład tak:
[DllImport("plik.dll")]
unsafe static extern double* Result();
...
double[] A = new double[N];
unsafe
{
double* Atemp = Result();
for (int i = 0; i < N; i++) A[i] = Atemp[i];
}
Ogólnie jednak jeśli nie jest to konieczne, nie zaleca się używania kodu niezarządzanego w C# (od tego mamy C++).
19-12-2009
Operacje na bitach
Często chcemy przechowywać pewien zbiór wartości, które przyjmują tylko dwie wartości: 0 albo 1. W tym celu można po prostu stworzyć tablicę przechowującą stany. Jednak o wiele lepszym rozwiązaniem jest zastosowanie jednej lub kilku zmiennych typu
int. Na 32 bitach możemy przechować 32 różne stany.
Wbrew pozorom, jest to równie proste jak z wykorzystaniem tablicy:
//makra
#define SET_BIT(v,m) ((v)|(m))
#define UNSET_BIT(v,m) ((v)&~(m))
#define SWITCH_BIT(v,m) ((v)&(m)^(m)|(v)&~(m))
#define ISSET(v,m) (((v)&(m))!=0)
#define MASK(n) (1<<((n)-1))
//przyklad uzycia
int v=0x75; //1110101
v=SET_BIT(v,MASK(4)); //ustaw bit nr 4
v=SWITCH_BIT(v,MASK(6)); //zmien wartosc bitu nr 6; v=1011101
ISSET(v,MASK(6)) //false
Mam nadzieje, że przykład jest jasny. Oczywiście można to zrealizować unikając czasem kłopotliwych makr np. za pomocą funkcji inline. Poza tym jesteśmy ograniczeni do określonej liczby stanów (np. dla typu
long long mamy 64 bity).
08-11-2009
Porównanie kopców
Pozostanę jeszcze w temacie z poprzedniego postu. Jak wiadomo, używana struktura danych ma często kluczowe znaczenie dla szybkości działania algorytmu. Co więcej, od sposobu jej reprezentacji w pamięci zależy bardzo wiele.
Przedstawiam małe porównanie trzech programów. Pierwszy implementuje kolejkę priorytetową na tablicy (algorytm przedstawiony w poście niżej), drugi i trzeci za pomocą kopca lewoskrętnego. Pod tą tajemniczą nazwą ukrywa się drzewo binarne, w którym dla każdego węzła lewe poddrzewo jest większe lub równe (co do ilości węzłów) od prawego. Dodatkowy parametr npl (ang. null-path-length) określa najmniejszą długość ścieżki do pustego poddrzewa. W dodatku struktura nie narzuca na samym początku określonego rozmiaru - węzły alokowane są dynamicznie, łączone ze sobą za pomocą wskaźników. Podstawową operacją jest
Union, która łączy ona dwie dowolne kolejki. Dodanie elementu (Insert) to po prostu dodanie kopca jednoelementowego. Z kolei usunięcie elementu maksymalnego (DeleteMax) polega na usunięciu korzenia i zastosowaniu operacji Union dla lewego i prawego poddrzewa usuniętego korzenia. Złożoność -
O(log n). Mimo tych zalet, pojawia się niestety jedna poważna wada - wydajność:
HEAP
Insert: 0.0341863
DeleteMax: 0.190271
---
LHEAP
Insert: 0.353327
DeleteMax: 1.85155
---
LHEAP (struct)
Insert: 0.32966
DeleteMax: 1.59329
Drugi program implementuje kopiec lewoskrętny z wykorzystaniem klasy, trzeci - struktury. Nie zmienia to faktu, że implementacja na tablicy (program pierwszy) działa blisko 10 razy szybciej.
Paczka z plikami:
heap.zip07-11-2009
Kolejki priorytetowe
Kolejka priorytetowa to abstrakcyjny typ danych, w którym wyróżniamy dwie podstawowe operacje:
Insert (wstawianie elementu),
DeleteMax (zwracanie i zdejmowanie elementu maksymalnego). Operacją dodatkową jest
GetMax, która tylko zwraca wartość maksymalną.
Chyba najprostrzą implementacją kolejki priorytetowej jest zwykła lista. Wstawiamy element na jej koniec (koszt stały), zaś zdjęcie elementu maksymalnego w najgorszym przypadku ma złożoność liniową. Zdecydowanie efektywniejsza i tylko nieznacznie trudniejsza jest implementacja na zwykłej
tablicy za pomocą kopca.
Kopiec (ang.
heap) to drzewo binarne, w którym potomek danego węzła jest z nim w stałej relacji (w naszym przypadku w relacji <). W praktyce mamy tu doczynienia z kopcem zupełnym: liście są spójnie ułożone od lewej do prawej.
Implementacja na tablicy opiera się na spostrzeżeniu, że rodzic węzła o indeksie
n ma index
n/2, zaś dzieci mają indeksy
2*n i
2*n+1. Wstawienie elementu (operacja Insert) polega na dodaniu go na koniec tablicy, a następnie wykonaniu operacji
UpHeap, która polega na przywróceniu właściwości kopca, którą przed chwilą naruszyliśmy. Operacja DeleteMax polega zaś na pobraniu elementu pierwszego (wartość zwracana), skopiowaniu elementu ostatniego na początek, a następnie przywróceniu właściwości kopca za pomocą operacji
DownHeap. Operacje UpHeap i DownHeap mają złożoność
O(log n).
Przykładowa implementacja na szablonie klasy:
heap.h,
main.cpp
01-11-2009
C# się opłaca...
...nawet, gdy jesteśmy przyzwyczajeni do starych zasad. Nie uświadczymy tu bowiem żadnych wskaźników, czy niskopoziomowych "trików". Jednak jest coś, co mnie ostatnio przekonało do tego języka, czy w zasadzie do aplikacji napisanych na .NET.
Okazuje się bowiem, że praktycznie po kilku godzinach pracy z Visual Studio 2008 można zrobić więcej, niż to było możliwe dotychczas. Przez "dotychczas" rozumiem to, co pisałem do tej pory w C++. Teraz jednak otrzymuje wygodny edytor wizualny, dzięki któremu tworzenie programu ze wszystkimi widżetami (przyciski, pola edycji itd.) jest banalnie proste. Do czego zmierzam? Załóżmy, że mamy jakiś ciekawy program napisany w C++, np. jakąś animację w OpenGL. Dopóki mamy puste okno, w którym wyświetlamy całą grafikę, jest bezproblemowo - kilka prostych funkcji WinApi i gotowe: tworzymy okno, a w nim wyświetlamy naszą animację. Problemy zaczynają się, gdy chcemy dodać jakieś widżety. Wszystko co prawda można zrealizować za pomocą WinApi, ale w praktyce jest to bardzo niewygodne i ostatecznie szybko można się pogubić (chyba, że sami napiszemy własną bibliotekę, albo skorzystamy z tych gotowych dla C++ np. Qt, jednak wymaga to dołączania do programu sporych plików .dll). Z pomocą przychodzi platforma .NET i flagowy C#, w którym pisanie dzięki IntelliSense (system podpowiedzi) i licznej dokumentacji jest bardzo proste. Kluczem do zagadki jest możliwość łączenia kodu napisanego w C++ (kod niezarządzany), z kodem napisanym w C# (kod zarządzany). Idea jest następująca: tworzymy plik .dll z wyeksportowanymi funkcjami, a następnie za pomocą odpowiedniej deklaracji możemy wygodnie używać tych funkcji w kodzie C#. Nie ma też problemów ze zgodnością parametrów dla typów wbudowanych (szczerze mówiąc nie próbowałem tego dla bardziej złożonych danych niż tablice). Na koniec przykład wyeksportowanej funkcji w C++ i jej użycia w C#.
Kod C++:
extern "C"
{
...
__declspec (dllexport) void __stdcall ChangeState(double tx,double ty,double tz)
{
engine.Translate(tx,ty,tz);
}
...
}
Kod C#:
using System.Runtime.InteropServices;
...
[DllImport("my_engine.dll")]
static extern void ChangePos(double tx, double ty, double tz);
Wywołanie:
ChangePos(-dx / delta, dy / delta, 0);
Powstaje jeszcze pytanie jak przekazać uchwyt do widżetu w którym chcemy np. rysować? Wystarczy dostarczyć do funkcji w C++ wartość właściwości Handle danego obiektu (rzutowaną na int).
31-10-2009
Zmiany, zmiany...
Po blisko 10 miesiącach trochę zmian na stronie, głównie pod względem wizualnym, choć nadal kieruje się zasadą, że najważniejsza jest treść, a nie forma. Oczywiście strona jest na bieżąco aktualizowana o moje bieżące projekty. Jak to piszę, największą aktywność powinna wykazywać
strona z projektami z metod numerycznych. Przynajmniej do końca tego semestru :).
Teraz główna strona będzie w swojej formie bardziej przypominać blog. Można powiedzieć, że jest to pierwszy wpis. Dotychczasowa treść strony głównej znajduje się w poście poniżej.
28-10-2009
O stronie
Na podstronach zamieściłem większość moich programów, gier, projektów. Większość opatrzona jest krótkim opisem i kilkoma zrzutami ekranu:
Na stronie
PROGRAMY znajduje się większość moich aplikacji, tworzonych na przestrzeni lat.
Strona
SYMBIAN jest w szczególności poświęcona autorskim programom na system Symbian OS.
Strona zawierająca APLETY JAVA dostępna jest pod
tym adresem (w tej chwili tylko jeden aplet rysujący fraktale).
Strona
PROJEKTY poświęcona jest poważniejszym projektom programistycznym. Najważniejszą aplikacją jest
Expr. Jest to rozbudowany, interaktywny program obliczeniowy.
Jego możliwości to m.in.:
- Obliczanie wartości wyrażeń
- Definiowanie własnych funkcji
- Rysowanie funkcji typu: y=f(x); z=f(x,y); x=x(t), y=y(t) zarówno na płaszczyźnie 2D, jak i w przestrzeni 3D
- Synteza dźwięku opisanego danym wyrażeniem
- Tworzenie animowanych wykresów funkcji
- Generowanie opisywanych matematycznie obrazów (np. fraktale)
Szerszy opis, pliki do pobrania (
w tym źródła) oraz link do galerii znajduje się na
tej stronie.
Niżej zamieszczam kilka przykładowych screenów:
Czytaj dalej...
01-01-2009
Copyright © Kamil Korolkiewicz 2009, 2010
