Tag: algorithms

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

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 ... 6 7 8 9 >

# Nigdy nie ufaj optymalizacji kompilatora

Sat
30
Jun 2007

Xion widząc kod mojej biblioteki CommonLib zarzucił mi dzisiaj, że niepotrzebnie przesyłam wszelkie zwracane przez funkcje obiekty większe niż pojedyncza liczba (jak wektor, macierz czy string) przez parametr wskaźnikowy nie ufając optymalizacji kompilatora (nazwał to RVO - Return Value Optimization). Zrobiłem więc na szybko prosty test na przykładzie stringów i wyniki potwierdziły mój pogląd, żeby nigdy nie ufać optymalizacjom kompilatora. Zobacz kod i wyniki: TestNieoptymalizacjiKompilatora.cpp.

Może dożyję czasów, kiedy kompilatory C++ (albo lepiej - jakiegoś nowocześniejszego języka) pozwolą napisać po prostu return wektor * macierz1 * macierz2 albo return string1 + string2, a to zostanie zamienione na taki kod maszynowy, jaki napisałby dobry programista posługujący się bezpośrednio liczbami float albo łańcuchami char*. Przykład kompilatorów HLSL i Cg pokazuje, że da się...

Comments | #c++ #algorithms Share

# Napisałem FreeList

Thu
31
May 2007

Napisałem na podstawie artykułów z "Game Programming Gems" (oraz swoich pomysłów) własne alokatory pamięci do obiektów konkretnego typu, czyli tzw. FreeList. Powinny działać szybciej niż standardowe, podobno wolne operatory new i delete. Znajdą się oczywiście w nowej wersji mojej biblioteki CommonLib. Testy (przeprowadzone dla 10240 operacji alokacji lub zwalniania) są bardzo optymistyczne:

DEBUG:
Element typu int:
  FreeList : 68.0636 ms
  DynamicFreeList : 184.441 ms
  new i delete : 78.8142 ms
Element typu zajmujacego 1024 bajty:
  FreeList : 69.3896 ms
  DynamicFreeList : 203.506 ms
  new i delete : 93.2942 ms
RELEASE:
Element typu int:
  FreeList : 7.87224 ms
  DynamicFreeList : 11.4786 ms
  new i delete : 17.0348 ms
Element typu zajmujacego 1024 bajty:
  FreeList : 9.18059 ms
  DynamicFreeList : 18.0729 ms
  new i delete : 24.0537 ms

Comments | #c++ #algorithms Share

# Policy-Based Design

Wed
30
May 2007

class DeletePolicy {
public:
  template <typename T>
  static void Destroy(T *p) { delete p; }
};
class ReleasePolicy {
public:
  template <typename T>
  static void Destroy(T *p) { if (p) p->Release(); }
};

class scoped_ptr<typename T, typename PolicyT = DeletePolicy>
{
public:
  explicit scoped_ptr(T *p = NULL) : m_Ptr(p) { }
  ~scoped_ptr() { PolicyT::template Destroy<T>(m_Ptr); }
  // ...
};

scoped_ptr<int, DeletePolicy> p1;
scoped_ptr<IDirect3DTexture9, ReleasePolicy> t1;

To przykład techniki zwanej Policy-Based Design, którą wynalazł Andrei Alexandrescu. Wszystkich zainteresowanych zabawami z językiem C++ zachęcam do zgłębiania tematu. Szablony to nie jest lekarstwo na wszystkie (jakże liczne) problemy rodzące się podczas programowania w tym języku, ale to jedna z potężnych i zaawansowanych technik. Znałem ją już wcześniej, ale teraz doceniłem i użyłem. Jak to się mówi w komentarzach na Allegro: Polecam! :)

Comments | #c++ #algorithms Share

# Pytanie o inteligentne wskaźniki

Mon
28
May 2007

Chcę sobie napisać tzw. inteligentne wskaźniki (po to żeby, przyznaję, uwolnić się od biblioteki Boost :) W związku z tym będę wdzięczny każdemu kto potrafi i znajdzie chwilę żeby odpowiedzieć na moje pytanie z tym związane w odpowiednim wątku forum.

Comments | #c++ #algorithms Share

# IntToStr, StrToInt

Fri
25
May 2007

Na dobry koniec dnia wyniki pomiaru wydajności moich nowych funkcji do konwersji między liczbą a łańcuchem - porównane z funkcjami systemowymi (plus konwersje do std::string, bo takich łańcuchów wszędzie używam i takich używają te moje funkcje). Wyniki w mikrosekundach na pojedyncze wywołanie, już podzielone przez liczbę wykonanych iteracji.

- DEBUG
  - int > string
    itoa : 0.244895 us
    IntToStr (stary) : 3.20974 us
    IntToStr (nowy) : 0.659205 us
  - string > int
    atoi : 0.270027 us
    StrToInt : 0.391424 us
- RELEASE
  - int > string
    itoa : 0.137373 us
    IntToStr (stary) : 0.225465 us
    IntToStr (nowy) : 0.134297 us
  - string > int
    atoi : 0.0785857 us
    StrToInt : 0.0589072 us

Comments | #c++ #algorithms Share

# Signed czy unsigned

Fri
25
May 2007

Czy do zapisywania rozmiaru danych, liczby bajtów, liczby elementów albo indeksu lepiej stosować liczbę całkowitą ze znakiem, czy bez znaku? Liczby ze znakiem są standardem w Delphi i mają wielu zwolenników dzięki swoim zaletom: Indeksy ujemne, jako niepoprawne, można stosować do oznaczenia wartości specjalnej (np. -1). Nie ma też obawy o "przekręcenie" przy zliczaniu w dół.

Ja jestem jednak zwolennikiem podejścia obowiązującego w C++, czyli stosowania typu bez znaku tam gdzie to możliwe (np. pod nazwą: unsigned, size_t, DWORD czy mój własny uint4). Zaleta tego podejścia to m.in. dwa razy większy dostępny zakres. Nie trzeba też sprawdzać poprawności liczby od dołu - wystarczy od góry. Jako wartości specjalnej można używać 0xFFFFFFFF (taką wartość ma na przykład stała std::string::npos zwracana przez std::string::find kiedy nic nie znaleziono).

Co wtedy z przechodzeniem tablicy w dół? Sposobem na to jest tzw. Pętla Tarlandila (tak sobie ją nazywam, bo nauczył mnie jej Tarlandil):

for (size_t i = RozmiarTablicy; i--; )
{
  Tablica[i] = 0;
}

Jak chcesz to przeanalizuj dokładnie jak działa ta sprytna pętla, a jeśli nie, to uwierz na słowo że ona naprawdę przechodzi tablicę w dół od elementu ostatniego do pierwszego i nie straszne jej przekręcenie się liczby bez znaku poniżej zera :)

Comments | #c++ #philosophy #algorithms Share

# Poisson Disc Generator

Mon
23
Apr 2007

Poisson Disc

Poisson Disc is one of the best methods for determining places from which to sample some data, next to Grid, Random or Jittered methods. It prevents aliasing thanks to random distribution while preserving minimum distance between sample positions not to focus too many samples in a particular region. Unfortunately, an algorithm for generating such samples is slow and we don't know how many points we will manage to generate with specified minimum distance.

That's why I thought it would be useful to have an array of many numbers, each defining new Poisson Disc sample in the way that the more first samples you take, you still have a correct Poisson Disc samples but with more points and smaller minimum distance. I've coded a small console application for generating such arrays of 1D, 2D or 3D points in 0..1 range. I've also generated ready 1000-element arrays. Here you can find the details: PoissonDiscGenerator.

I've called it "Progressive Poisson Disc", described it in my master thesis [PDF, pl], used in my The Final Quest engine [pl] and also integrated into Math module of my CommonLib library.

Comments | #algorithms #math #productions Share

# Szybkie, heurystyczne przeszukiwanie dysku

Thu
01
Mar 2007

Na stronie portalu CodeGuru.pl poświęconemu programowaniu w technologii .NET ukazał się mój nowy, drobny artykuł zatytułowany Szybkie, heurystyczne przeszukiwanie dysku. Opisałem w nim algorytm, który przeszukując katalogi dysku twardego użytkownika pozwala odnaleźć potrzebny plik w czasie wielokrotnie krótszym, niż podczas tradycyjnego, rekurencyjnego przeszukiwania dysków dzięki zastosowaniu prostej heurystyki i wiedzy o konkretnym problemie.

Comments | #productions #teaching #.net #algorithms Share

Pages: > 1 ... 6 7 8 9 >

[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2021