Tag: algorithms

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

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

Pages: > 1 ... 6 7 8

23:20
Fri
25
May 2007

IntToStr, StrToInt

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 (0) | Tags: c++ algorithms | Author: Adam Sawicki | Share

14:40
Fri
25
May 2007

Signed czy unsigned

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 (0) | Tags: c++ philosophy algorithms | Author: Adam Sawicki | Share

23:43
Mon
23
Apr 2007

Poisson Disc Generator

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 (2) | Tags: algorithms math productions | Author: Adam Sawicki | Share

11:51
Thu
01
Mar 2007

Szybkie, heurystyczne przeszukiwanie dysku

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 (0) | Tags: productions teaching .net algorithms | Author: Adam Sawicki | Share

19:10
Mon
05
Feb 2007

XDS - eXtensible Data Stream

Nie tylko ja podejmuję próby zastąpienia języka XML czymś lepszym, pozbawionym choć części z jego licznych wad. W moim XNL2 zrezygnowałem ze znaczników i związanego z nimi samoopisu na rzecz prostoty i zwięzłości. XNL2 w moich własnych zastosowaniach sprawdza się doskonale, ale po latach jego używania dochodzę do wniosku, że jeszcze lepiej zastąpiłby go zwykły tokenizer C/C++, być może razem z preprocesorem. Kiedyś sobie taki napiszę.

Podobnego zadania, ale od trochę innej strony, podjął się niejaki Mark T. Price. Zaprojektował on format XDS - eXtensible Data Stream, który jest binarny (tym samym szybki i zwięzły), a zarazem elastyczny. Czy użyteczny? - to zależy od zastosowania, ale warto chyba przejrzeć jego specyfikację.

Comments (0) | Tags: algorithms | Author: Adam Sawicki | Share

21:02
Sun
19
Nov 2006

Kademlia

Myślę, że nie tylko pasjonatów algorytmiki czy programowania równoległego i rozproszonego, ale i zwykłych użytkowników może zainteresować - jako ciekawostka - czym jest Kademlia. Ten sprytny wynalazek to rozproszona tablica haszująca, która wykorzystywana jest m.in. w sieciach P2P do całkowicie zdecentralizowanego wyszukiwania źródeł i można ją spotkać pod postacią sieci Kad w eMule czy mechanizmu DHT w klientach BitTorrenta.

Comments (0) | Tags: algorithms | Author: Adam Sawicki | Share

Pages: > 1 ... 6 7 8

STAT NO AD [Stat] [Admin] [STAT NO AD] [pub] [Mirror] Copyright © 2004-2016 Adam Sawicki
Copyright © 2004-2016 Adam Sawicki