Tag: algorithms

Entries for tag "algorithms", ordered from most recent. Entry count: 68.

Uwaga! Informacje na tej stronie mają ponad 6 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Pages: 1 ... 3 4 5 6 7 ... 9

# Sortowanie naturalne

Thu
12
Feb 2009

Ciekawym algorytmem jest sortowanie łańcuchów w porządku naturalnym. Chodzi o to, żeby liczby traktowane były jako liczby i sortowały się według wartości. Na przykład nazwy plików posortowane normalnie alfabetycznie (leksykonograficznie) będą w takiej kolejności:

Plik.txt
Plik1.txt
Plik10.txt
Plik2.txt
Plik24.txt
Plik3.txt

Natomiast posortowane w porządku naturalnym będą w kolejności bardziej przez użytkownika pożądanej:

Plik.txt
Plik1.txt
Plik2.txt
Plik3.txt
Plik10.txt
Plik24.txt

Oczywiście każdy informatyk wie, że należałoby raczej po prostu dopełniać te liczby zerami (np. Plik01.txt), ale mimo wszystko ten algorytm jest dobry do sortowania nazw plików, serwerów itp.

Jak to działa? Całkiem prosto. Mówiąc ogólnie, trzeba porównywać kolejne znaki dwóch łańcuchów, ale kiedy napotka się cyfry, wtedy trzeba rozpatrzyć je jako całe liczby i porównać ich wartości. Implementację w C++ można znaleźć w mojej bibliotece CommonLib (zobacz pliki Base.hpp i Base.cpp, klasa StringNaturalCompare). W PHP jest standardowo taka funkcja - nazwa się strnatcmp. Opis algorytmu w Internecie można znaleźć m.in. tu: Natural Order String Comparison.

Comments | #algorithms Share

# Co wynalazł Hilbert i Morton

Mon
12
Jan 2009

Tablicę jednowymiarową można posortować, żeby przyspieszyć jej przeszukiwanie. W programowaniu gier, do przestrzeni 2D i 3D używamy technik podziału przestrzeni (jak BSP, Octree, k-d tree), bo nie sposób uporządkować punktów czy obiektów w kolejności. Jednak czy napewno?

Otóż wynaleziono funkcje, które przeliczają pozycję punktu w przestrzeni (podzielonej wprawdzie na dyskretną siatkę) na pojedynczą liczbę taką, że dwa punkty leżące blisko siebie dostają często zbliżoną wartość. Te funkcje to numer komórki wzdłuż pewnej krzywej (Space-filling curve).

Przykładem może być Morton value:

Źródło: Wikipedia

lub lepsza, ale bardziej kosztowna obliczeniowo Hilbert value:

Źródło: Wikipedia

Comments | #math #algorithms #rendering Share

# Programowanie równoległe #2

Sun
21
Dec 2008

Kontynuując temat Programowanie równoległe #1... Czego można się uczyć dalej? Ostatnio czytałem sobie o funkcjach typu InterlockedIncrement czy InterlockedCompareExhange. Wygląda na to, że na niższym poziomie synchronizacja sprowadza się do dwóch problemów - do zapewnienia, że dana operacja jest atomowa oraz do wymuszenia pożądanej kolejności operacji na pamięci (plus synchronizacja cache).

Atomowy w programie 32-bitowym jest zapis i odczyt wyrównanej wartości 32-bitowej. Atomowe są operacje wykonywane przez funkcje WinAPI Interlocked* czy też funkcje Compiler Intrinsics - _Interlocked*. Atomowość zapewniamy też stosując muteksy (sekcje krytyczne).

Z kolei co do pamięci, tutaj pojawiają się takie problemy: zarówno kompilator podczas generowania kodu maszynowego, jak i procesor podczas jego wykonywania może przestawiać kolejność operacji używających dostępu do pamięci. Żeby temu zapobiec, trzeba używać tzw. barier (Memory Barrier). Są trzy rodzaje - o semantice Acquire, Release lub obydwie jednocześnie. Można je wykonywać funkcjami Intrinsic - _ReadBarrier, _WriteBarrier, _ReadWriteBarrier. Systemowe obiekty synchronizujące oraz funkcje Interlocked automatycznie wykonują barierę (choć na innych platformach wcale tak być nie musi).

Ciekawie w tej sytuacji wygląda kwestia słowa kluczowego volatile. Ogólnie pisząc, jego użycie nie zapewnia bezpieczeństwa. Ono powoduje tylko, że kompilator za każdym razem sięga po wartość w pamięci zamiast buforować ją w rejestrach, a począwszy od Visual C++ 2005 dodatkowo wstawia barierę pamięciową (odpowiednio, przy odczycie taką o semantyce Acquire, a przy zapisie taką o semantyce Release).

Tych "niskopoziomowych" mechanizmów używa się do realizacji algorytmów tzw. lock-free (lockless, Non-blocking synchronization czy jak tam to jeszcze inaczej nazwać). Z tych z kolei można budować różne struktury danych. Ten temat, jak również temat tworzenia jednych obiektów synchronizujących za pomocą innych, postaram się opisać wkrótce...

Comments | #algorithms Share

# Programowanie równoległe #1

Sun
07
Dec 2008

Programowanie równoległe to w czasach wielordzeniowych procesorów ważna sprawa i warto zainwestować w naukę tej dziedziny. Jakich konkretnie rzeczy można użyć, żeby coś mogło się wykonywać równolegle do głównego kodu programu? Opcji jest bardzo wiele. Postanowiłem zebrać je do kupy.

Zacząć można od czegoś prostego, co nie wymaga od nas tworzenia nowych wątków. Równolegle pracują niektóre biblioteki, np. DirectX wykonując polecenia na karcie graficznej w swoim tempie albo FMOD odtwarzając muzykę w tle. Ponadto w sposób asynchroniczny (nieblokujący) mogą działać gniazda sieciowe (Socket) oraz systemowe wejście/wyjście, np. odczytywanie i zapisywanie plików (Overlapped I/O).

Wykonywać jakąś pracę równolegle mogą osobne procesy (Process). W WinAPI nie ma wprawdzie funkcji fork, ale można odpalić nowy proces funkcją CreateProcess. Procesy mogą komunikować się na różne sposoby, np. przez przechwytywanie swojego konsolowego wejścia-wyjścia, przez sockety, Named Pipe, RPC, Shared Memory albo przez specjalne biblioteki, jak MPI.

Najczęściej najlepszy sposób na zrównoleglenie programu to tworzenie nowych wątków (ang. Thread) w ramach jednego procesu. Wątki współdzielą pamięć programu i inne jego zasoby. Pozostaje problem synchronizacji, który rozwiązuje się za pomocą dostępnych w systemie obiektów synchronizujących. W Windows są to m.in.: sekcje krytyczne (Critical Section), muteksy (Mutex), semafory (Semaphore) i zdarzenia (Event).

Windows Vista dodaje nowe przydatne obiekty, jak zmienna warunkowa (Condition Variable), jednokrotna inicjalizacja (One-Time Initialization) czy Reader/Writer Lock (SRW) - ale kto ograniczałby dla nich swój program tylko do porażkowego Windowsa Vista? :)

Linuksowy interfejs pthreads ma inne obiekty synchronizujące - muteksy, zmienne warunkowe, semafory. Swoją drogą, nie wiem jak linuksowcy radzą sobie bez czekania na wiele obiektów na raz, tak jak w WinAPI robi się to funkcją WaitForMultipleObjects.

Do programowania wielowątkowego można też używać nie API systemowego, ale dodatkowych bibliotek. Wieloplatformową nakładką na interfejs wątków jest np. Boost.Thread. Programowanie równoległe na wyższym poziomie zapewnia darmowa biblioteka Intel Threading Building Blocks. Ciekawą opcją jest też OpenMP, którego stosowanie polega na wpisywaniu dykrektyw #pragma omp. Niestety, wspierają go tylko niektóre kompilatory, np. Visual C++ wyłącznie w wersji Professional i Team System.

Idąc dalej, ciekawe są też funkcje z grupy Interlocked, bariery pamięciowe (Memory Barrier) oraz algorytmy lock-free. Ale to już temat na osobną notkę... W komentarzach możecie wpisywać, czego jeszcze warto się uczyć w tej dziedzinie i skąd najlepiej się tego uczyć.

Comments | #algorithms Share

# Ciekawe struktury danych

Mon
01
Dec 2008

Ucząc się programowania gier każdy w pewnym momencie trafia na techniki podziału przestrzeni. Najczęściej opisywane są drzewa BSP, Octree itp. Tymczasem świat struktur danych - bardziej lub mniej związanych z programowaniem gier - jest bardzo bogaty, różnorodny i ciekawy.

Ot choćby Bloom filter - struktura, która wbrew nazwie nie ma nic wspólnego z popularnym efektem graficznym Bloom, ale służy do przechowywania zbioru elementów i testowania przynależności do zbioru (np. w słownikach sprawdzania pisowni). Ostatnio dowiedziałem się też o istnieniu drzew R-tree (pozdro Robert!), które opisują hierarchię boksów otaczających i działają podobnie do drzew B-tree (stosowanych np. w systemach plików i bazach danych).

Zaimplementować samemu taką strukturę danych na pewno nie jest łatwo, ale warto chociaż poczytać o nich na Wikipedii :)

Comments | #algorithms Share

# MMX i SSE

Sat
29
Nov 2008

Osobny temat w rozdziale MSDN Library "Compiler Intrinsics" stanowią funkcje i typy do obsługi SIMD, czyli rozszerzeń wektorowych procesora (MMX, 3DNow!, SSE).

MMX wprowadzono dawno temu, dziś każdy procesor go ma. Odpowiednim typem jest __m64. Reprezentuje wartość 64-bitową interpretowaną jako zestaw 1, 2, 4 lub 8 liczb całkowitych, ze znakiem lub bez znaku. Myk polega na operowaniu całym wektorem za pomocą jednej funkcji. Np. funkcja _mm_adds_pi8 dodaje komponenty dwóch wartości jako złożonych z ośmiu 8-bitowych liczb ze znakiem, wykonując dodatkowo saturację. To może się przydać np. do przetwarzania obrazów 2D.
3DNow! to rozszerzenie wymyślone przez AMD i obecne chyba tylko w procesorach tej firmy, jako że wg Valve Survey Summary Data mniej niż połowa użytkowników posiada procesor, który go wspiera. Dlatego chyba nie warto się nim zajmować.
SSE zostało wprowadzone z Pentium III. Obecnie prawie każdy ma procesor, który go wspiera. Odpowiada mu typ __m128, który reprezentuje 128-bitową wartość zbudowaną z 4 liczb typu float. Przykładowa funkcja _mm_rsqrt_ps liczy odwrotność pierwiastka kwadratowego każdego z komponentów. Te funkcje zdają się idealne do przyspieszenia operacji na wektorach, macierzach i wszystkim, co związane z grafiką 3D.
SSE2 jest wprowadzone od Pentium 4. Wg danych Valve, procesor który go wspiera posiada 89.41% użytkowników. Ten standard dodaje typy __m128d i __m128i, które rozszerzają interpretację tej 128-bitowej wartości na 2 liczby typu double lub 1-16 liczb całkowitych.
SSE3, SSE4 i SSE4a to jeszcze nowsze standardy i raczej duży procent użytkowników nie ma procesora, który by je obsługiwał.

Na temat wsparcia procesorów dla tych instrukcji wektorowych założyłem dyskusję na forum. Koniec końców myślę jednak, że przyspieszenie obliczeń za ich pomocą (np. przez przerobienie wektorów i macierzy w bibliotece matematycznej na użycie SSE) nie jest takie proste. Przeszkodą jest np. wymagane dla typów __m64 i __m128 wyrównanie odpowiednio do 8 i 16 bajtów, które nie pozwala czytać sobie tych wektorów ot tak swobodnie, z dowolnych danych binarnych.

Comments | #algorithms #c++ #visual studio Share

# Elementarne algorytmy - pomysł na artykuł

Sun
26
Oct 2008

Dawno, dawno temu wymyśliłem pewien artykuł dla początkujących. Zauważyłem bowiem, że między tematami najczęściej podejmowanymi w nauce programowania - opanowaniem języka programowania i opanowaniem bardziej zaawansowanych tematów, jak biblioteka graficzna czy algorytmika - istnieje pewna luka i wielu adeptów ma z tym problem. Chodzi o 1. podstawowe struktury danych, 2. projektowanie i używanie własnych formatów plików oraz 3. elementarne algorytmy i sztuczki programistyczne.

Dwa pierwsze tematy opisałem w jakimśtam stopniu 4 lata temu w artykule Struktury danych i formaty plików. Trzeci chciałem opisać w ubiegłe wakacje, ale wyjaśnienie wszystkich zebranych zagadnień w dostatecznie dokładny i przystępny sposób kosztowałoby zbyt dużo pracy. Dlatego jedyne co zrobiłem to teraz spisałem wreszcie i opublikowałem sam "projekt" tego artykułu (co samo w sobie było niemałym zadaniem) - Elementarne algorytmy.txt.

Comments | #algorithms #ideas #teaching Share

# Przechodzenie tablicy - koncepcja Stride

Sun
28
Sep 2008

Jeśli piszemy funkcję, która ma przejść po kolejnych wektorach, to najprościej wydaje się przekazać po prostu tablicę wektorów:

void DoSth(const vec3 Arr[], size_t ArrLen)
{
  for (size_t i = 0; i < ArrLen; i++)
    DoSthWithVec(Arr[i]);
}

Istnieje pewien genialny pomysł, który uczyni tą funkcję bardziej elastyczną. Polega na przekazaniu jej Stride - kroku, mówiącego o ile bajtów trzeba przesuwać wskaźnik:

void DoSth(const void *Data, size_t ArrLen, int Stride)
{
  const char *Bytes = (const char*)Data;
  for (size_t i = 0; i < ArrLen; i++)
  {
    DoSthWithVec( *(const vec3*)Bytes );
    Bytes += Stride;
  }
}

To pozwala m.in.:

Przechodzić zwykłą tablicę jak wyżej - jako Data trzeba podać adres pierwszego elementu, jako Stride trzeba podać sizeof(vec3).
Przechodzić tablicę od końca - jako Data trzeba podać adres ostatniego elementu, jako Stride trzeba podać -sizeof(vec3).
Odwiedzić tylko co któryś element, na przykład wybraną kolumnę macierzy - jako Data trzeba podać adres pierwszego takiego elementu, jako Stride rozmiar całego wiersza w bajtach.
Przetworzyć tablicę, której elementy zamiast pojedynczego wektora zawierają też inne dane (np. są wierzchołkami posiadającymi pozycję, normalną, współrzędne tekstury) - jako Data trzeba podać adres pola z pozycją w pierwszym wierzchołku, jako Stride rozmiar całej struktury wierzchołka.

To jeden z tych drobnych algorytmów, których niestety nikt nigdzie nie naucza. Każdy musi je gdzieś wypatrzeć przy okazji (albo samemu wymyślić, jeśli ma do tego łeb :)

Comments | #c++ #algorithms Share

Pages: 1 ... 3 4 5 6 7 ... 9