Tag: algorithms

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

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

Pages: > 1 2 3 4 5 6 ... 9 >

# KD-Tree

Thu
09
Jul 2009

People at forums are usually advised to learn BSP, quadtree or octree as space partitioning data structure, but there are many more interesting structures than these three. This time my choice for home project is KD-tree. It's actually something between BSP and octree. Just like BSP it's a binary tree (each non-leaf node has two child nodes) and optimal splitting plane is estimated each time by special algorithm, but splitting planes are always aligned to one of three main axes and thus each node can be described by an AABB (axis-aligned bounding box), just like in octree.

As my tree is designed to manage objects and not geometry, nothing can be split and some of objects may intersect splitting planes. How to deal with them? I simply assign them to the parent node, so not only leaves are allowed to contain list of objects. To avoid too many small objects intersecting splitting planes to degrade performance by falling into top level nodes (it's called "sticky planes" or something like that :) I adopted "loose octree" idea to my KD-tree. It simply means I extend each node’s bounding box so that each node's children slightly overlap each other and small objects intersecting splitting plane fall into one of the children.

My KD-tree is also dynamic, which means it reorganizes itself as objects get added, removed and moved in the tree. It's actually quite simple. Each time an object is added to a node, that node can be split into two children if it's object number exceeds constant limit. Similarly node can be merged by deleting it's children each time an object is removed from one of its children, if the number of objects in that node and its children drops under constant minimum.

For additional performance, I allocate tree nodes from my own "Free List" memory pool and I keep objects connected to each node as doubly-linked list.

I also came up with an idea how to easily visualize quality of my space partitioning technique. I keep track of the number of tree nodes and objects on each depth level. This way I can tell from these several numbers whether tree is more "tall" or "wide" and whether most of objects stay in leaves instead of some top-level nodes.

Here are some screenshots and a video from my recent code:

KD-tree KD-tree KD-tree

Comments | #rendering #video #gallery #algorithms #math Share

# Manager zasobów #2 - Wczytywanie w tle

Sat
23
May 2009

Sam manager zasobów napisałem wg podobnych założeń, jakie miałem w TFQ7. Jest jeden globalny manager zasobów g_ResMngr przechowujący kolekcję wszystkich zasobów. Zasób jest obiektem klasy pochodnej od Resource implementującej odpowiednie metody wirtualne. Zasób może mieć nazwę i można wyszukiwać zasoby wg nazwy, ale może też mieć nazwę pustą. Zasoby można swobodnie tworzyć i usuwać. Obiekt klasy Resource istnieje przez cały czas życia zasobu, a wewnątrz pamięta stan - niezaładowany, w tracie ładowania, załadowany itd.

class Resource
{
public:
  enum STATE {
    STATE_UNLOADED, STATE_LOADING, STATE_LOADED, STATE_LOADED_ERROR,
  };
  Resource(const string &Name);
  virtual ~Resource();
  STATE GetState() { return m_State; }
  bool IsLoaded() { return m_State == STATE_LOADED; }

  void Load(); // Żąda załadowania już teraz
  void BeginLoading(); // Rozpoczyna ładowanie w tle
  void Unload(); // Odładowuje
  //...

protected:
  virtual void OnLoad() = 0;
  virtual void GetLoadType(bool *OutUseBkg, BkgJob::TYPE *OutBkgJobType) = 0;
  virtual void OnLoadBkg() { } // Wykonywana na osobnym wątku
  virtual void OnLoadAfterBkg() { }
  virtual void OnUnload() = 0;

private:
  string m_Name;
  STATE m_State;
  //...
};

class ResourceManager
{
public:
  //...
  Resource * Find(const tstring &Name);
  Resource * MustFind(const tstring &Name);
  template <typename T> T * FindEx(const tstring &Name) { /*...*/ }
  template <typename T> T * MustFindEx(const tstring &Name) { /*...*/ }
};

extern ResourceManager * g_ResMngr;

Read full entry > | Comments | #algorithms #c++ #engine Share

# Manager zasobów #1 - BkgJobManager

Thu
21
May 2009

Tajemniczy "Ciekawski" prosił, żebym opisał mój asynchroniczy manager zasobów. Zanim go opiszę, muszę napisać słowo o tym, na czym się on opiera - o module do wykonywania zadań w tle.

Ogólnie chodzi o to, aby osobny wątek pracujący w tle wykonał jakieś określone zadanie. Problem w tym, że tworzenie za każdym razem nowego wątku jest powolne. Poza tym przydałoby się, żeby takie zadania były wykonywane po kolei, a nie wszystkie na raz. Dlatego napisałem globalny BkgJobManager, który ma na stałe utworzone wątki, a zadania do wykonania dodaje się do jego kolejki jako obiekty specjalnej klasy BkgJob.

class BkgJobManager {
public:
  BkgJobManager();
  ~BkgJobManager();
  void Init();
  void Frame();
  void AddJob(BkgJob *Job);
  //...
};
extern BkgJobManager *g_BkgJobManager;

Żeby zdefiniować swoje zadanie, trzeba odziedziczyć po klasie BkgJob i zaimplementować metody: OnWork (wywoływaną na osobnym wątku) i opcjonalnie OnWorkDone (wywoływaną po zakończeniu, już na głównym wątku, w ramach wywołania BkgJobManager::Frame).

class BkgJob {
  //...
protected:
  BkgJob(TYPE Type, MODE Mode);
  virtual void OnWork() = 0;
  virtual void OnWorkDone() { }
};

Dodatkowo, klasa pochodna określa typ zadania jako obliczeniowe (mocno angażujące procesor) lub wejścia-wyjścia (wczytujące coś z dysku). To mój oryginalny pomysł oparty na przemyśleniu, że najoptymalniej będzie, jeśli na raz będzie się mogło wykonywać tylko tyle zadań obliczniowych, ile jest rdzeni w procesorze (więcej obniżyłoby wydajność przez częste przełączanie się procesora między wątkami) i tylko jedno zadanie wejścia-wyjścia (więcej obniżyłoby wydajność przez przeskakiwanie głowicy dysku między wieloma czytanymi na raz plikami).

enum TYPE { TYPE_COMPUTATION, TYPE_IO, TYPE_COUNT };

BkgJobManager przechowuje kolejkę zadań do wykonania. Żeby to napisać porządnie, to pewnie powinna być jakaś struktura "lockless", ale ja póki co załatwiłem synchronizację zwykłym muteksem.

Ponadto zadanie ma swój priorytet. Na zadanie można też poczekać, np. wywołując na wątku głównym BkgJob::Join. To wywołanie zwróci sterowanie dopiero, kiedy dane zadanie się zakończy. Jeśli to zadanie czeka gdzieśtam w kolejce, to jego priorytet zostaje podbity, żeby trafiło na przód kolejki.

Ciekawym rozwiązaniem jest, że na wątku głównym należy wołać w każdej klatce (lub inaczej, ale możliwie często) BkgJobManager::Frame. Daje to okazję managerowi, aby "zebrać" wykonane w tle i zakończone zadania, wywołać im BkgJob::OnWorkDone i zwolnić je z pamięci.

Trzeba też pomyśleć, jak z wykonywanej na innym wątku funkcji BkgJob::OnWork przekazywać informację o niepowodzeniu. Ponieważ w swoim kodzie używam wyjątków, łapię wyjątek zgłoszony w BkgJob::OnWork i zachowuję jego obiekt, żeby na wątku głównym móc go potem odczytać.

Podsumowując: Oryginalnie wątek służy do tego, żeby natychmiast rozpocząć wykonywanie jakiejś pracy w tle albo żeby działać cały czas w pętli czekając na jakieś komunikaty. Mechanizm taki jak tutaj przedstawiłem pozwala zmienić koncepcję na taką, w której użytkownik może tworzyć zadania i dodawać je do kolejki, a one będą po kolei wykonywane w tle. Podobny kod - JobSwarm - umieścił na swoim blogu John Ratcliff. Mój można pobrać stąd: BackgroundJob.hpp, BackgroundJob.cpp.

Tego mojego modułu mogę teraz używać do różnych rzeczy, ale podstawowym (i póki co jedynym :) zastosowaniem jest wczytywanie w tle zasobów Direct3D. O samym managerze zasobów napiszę następnym razem...

Comments | #algorithms #c++ #engine Share

# Znajdowanie podobnych stringów

Sun
22
Feb 2009

Kiedy wpisujemy w Google jakieś słowo, które jest ewidentną pomyłką, wyszukiwarka sugeruje jego poprawną wersję (np. Programmowanie). Jak zrobić coś takiego i ogólnie jak wyszukiwać w bazie danych podobne łańcuchy, by uodpornić pisaną stronę WWW na drobne pomyłki we wprowadzonym zapytaniu albo wyświetlać sugestię poprawnej pisowni? Niedawno kolega, którego poznałem przy piwie, zdradził mi kilka ciekawych pomysłów.

Po pierwsze, łańcuch trzeba przeliczyć na Hash - inny łańcuch, który dopiero jest wyszukiwany w bazie danych. Algorytm na ten Hash może wyglądać różnie, np.:

Taki Hash wyszukiwany jest w bazie danych, przy czym z bazy pobierany jest nie jeden pasujący rekord, ale też kilka sąsiednich rekordów (poprzednich i następnych wg kolejności alfabetycznej).

Następnie każdy z wyników zwróconych z bazy danych jest porównywany z hashem słowa wejściowego algorytmem Levenshtein Distance (który zwraca podobieństwo dwóch łańcuchów, tak jakby odległość między nimi). Jego wynik mnożony jest przez częstość występowania danego słowa wyszukanego w bazie (czyli np. po prostu ilość wystąpień w skatalogowanym tekście). Np. Punkty = Częstość_słowa / Levenshtein_distance.

Na koniec wybierane jest to słowo lub słowa spośród wyszukanych z bazy danych, które mają największy ten współczynnik Punkty.

Comments | #webdev #algorithms Share

# Algorytm na defragmentację dużego pliku

Sun
15
Feb 2009

SceNtriC na swoim blogu często pisze długie notki, w których opisuje swoje algorytmy, więc ja nie będę gorszy i dzisiaj też tak zrobię :) Problem, który rozwiązywałem niedawno, wyglądał tak: Mamy duży plik - tak duży, że nie chcemy wczytywać go całego do pamięci. W pliku są bloki z danymi, a między nimi dziury (na rysunku zakreskowane). Zadaniem jest tak "zsunąć" te dane, żeby dziur nie było.

Defragmentacja bloków danych

Read full entry > | Comments | #algorithms Share

# 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:

Morton value
Źródło: Wikipedia

lub lepsza, ale bardziej kosztowna obliczeniowo Hilbert value:

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

Pages: > 1 2 3 4 5 6 ... 9 >

STAT NO AD
[Stat] [STAT NO AD] [Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2019