Posts from 2010

Prosty menedżer zasobów?…

2010-06-28 18:09

Silnikologia (przynajmniej ta warsztatowa) ma swoje dziwnostki. Za jedną z nich uważam przykładanie zbyt dużego znaczenia do tych podsystemów engine‘u gry, które są zdecydowanie mniej ważne niż silnik graficzny czy fizyczny. Podpadają pod to (między innymi): mechanizmy logowania, VFS-y (wirtualne systemy plików), kod odpowiedzialny za wczytywanie i zapisywanie opcji konfiguracyjnych, itp. Blisko szczytu tej listy znajduje się też podsystem, o którym chcę napisać dzisiaj kilka słów. Chodzi mianowicie o menedżer zasobów (resource manager).

Pod tą nazwą kryję się obiekt, którego zadaniem jest – jak nazwa zresztą wskazuje – zarządzanie różnego rodzaju zasobami gry, gdzie pod pojęciem ‘zasobu’ kryje się zwykle jakiś element jej contentu: model, tekstura, próbka dźwiękowa, czcionka, shader… Menedżer ma za zadanie udostępniać odwołania do tych zasobów elementom silnika/gry, które ich potrzebują. To jest jego główny, nadrzędny cel.
Tu jednak dochodzimy do małego paradoksu. Jeśli bowiem jest to jedyne przeznaczenie modułu od zarządzania zasobami, to tak naprawdę mogłoby go w ogóle nie być!… W praktyce jego istnienie usprawiedliwia przynajmniej jeden z poniższych powodów:

  • jednoczesne załadowanie wszystkich zasobów gry czy nawet pojedynczego etapu/krainy/lokacji/itp. nie jest możliwe z uwagi na ograniczony rozmiar pamięci
  • ładowanie zasobów trwa na tyle długo, że rozsądne jest wydzielenie tego procesu do osobnego wątku
  • kompatybilność z DirectX w wersjach poniżej 9Ex wymaga obsługi zjawiska utraty urządzenia, a więc ponownego wczytania zasobów umieszczonych w pamięci karty graficznej
  • między poszczególnymi zasobami występują zależności, które nie pozwalają na łatwe określenie prawidłowej kolejności ich zwalniania

Tego rodzaju wymagania rzeczywiście można rozsądnie zrealizować dopiero wówczas, gdy w logiczny sposób wydzielimy z kodu część, która za kontrolę zasobów będzie odpowiadać. Jeśli jednak żadna z powyższych sytuacji nie aplikuje się do nas, nie ma żadnego powodu, by zabierać się za tworzenie modułu zarządzania zasobami tylko dlatego, że “przecież zasoby gdzieś muszą być”. Coś takiego jak ‘prosty menedżer zasobów’ to oksymoron: jeśli faktycznie może być prosty, to najpewniej znaczy, iż jest zbędny. No, chyba że pod tym pojęciem rozumiemy też coś, co w praktyce da się zredukować do:

  1. Texture* sprites[SPRITES_COUNT];
  2. Sound* sounds[SOUNDS_COUNT];

W takim przypadku powinniśmy zadbać przede wszystkich o to, by nasz Menedżer Zasobów (caps intended) dobrze współpracował z Modułem Wyświetlania Życia Gracza, że o Silniku Od PauzyTM nie wspomnę ;P

Dokładny czas na wielu platformach

2010-06-26 23:54

Gry i inne podobne aplikacje wymagają precyzyjnego pomiaru czasu, aby realizować obliczenia związane z fizyką, animacją, itp. Jak niemal wszystko, API potrzebne do tego celu jest różne w zależności od platformy, czyli (głównie) systemu operacyjnego. Dzisiaj chciałbym pokazać, jak wygląda to na dwóch najpopularniejszych systemach: Windows i POSIX (a więc między innymi na wszelkiego typu Linuksach).

Interfejs programistyczny systemu spod znaku okienek udostępnia dwie funkcje od dokładnego mierzenia czasu. Są to QueryPerformanceFrequency i QueryPerformanceCounter. Tę pierwszą wywołuje się tylko raz, a jej wynikiem jest częstotliwość wewnętrznego systemowego zegara, który służy do precyzyjnego pomiaru upływającego czasu. Wyrażana jest ona w liczbie “tyknięć” na sekundę i na dzisiejszym sprzęcie może być bardzo duża, bo liczona w (kilku(nastu/dziesięciu)) milionach.
Druga funkcja jest używana nieporównywalnie częściej, gdyż to ona zwraca aktualną wartość zegara, czyli liczbę jego “tyknięć”. Stąd wynika, że obliczenie tej wartości w sekundach wymaga podzielenia rezultatu QPC przez uzyskaną wcześniej częstotliwość:

  1. LARGE_INTEGER freq, counter;
  2. QueryPerformanceFrequency (&freq);
  3. // ...
  4. QueryPerformanceCounter (&counter);
  5. double secs = counter.QuadPart / (double)freq.QuadPart;

Używana tu unia LARGE_INTERGER to nic innego, jak zwykła liczba 64-bitowa.

W systemach POSIX-owych rzecz jest odrobinę prostsza, jako że tutaj dokładność zegara jest ściśle ustalona. Funkcja gettimeofday (z nagłówka sys/time.h) zwraca rezultat z precyzją mikrosekundową w postaci struktury timeval:

  1. struct timeval tv;
  2. gettimeofday (&tv, 0);
  3. double sec = tv.tv_sec + tv.tv_usec / 1000000.0;

Część odpowiadającą niepełnym sekundom (pole tv_usec) trzeba więc podzielić przez milion.

Chcąc mieć bardziej uniwersalne rozwiązanie, możemy napisać klasę opakowującą zegar z implementacją kontrolowaną docelową platformą, na którą kompilujemy:

  1. class Clock
  2. {
  3.     #ifdef _WINDOWS
  4.         LARGE_INTEGER freq;
  5.         public: Clock() { QueryPerformanceFrequence (&freq); }
  6.     #endif
  7.  
  8.     double GetTicks() const
  9.     {
  10.         #ifdef _WINDOWS
  11.             LARGE_INTEGER counter;
  12.             QueryPerformanceCounter (&counter);
  13.             return counter.QuadPart / (double)freq.QuadPart;
  14.         #else
  15.             struct timeval tv; gettimeofday (&tv, 0);
  16.             return tv.tv_sec + tv.tv_usec / 1000000.0;
  17.         #endif
  18.     }
  19. };

Można by na koniec zapytać jeszcze, co tak naprawdę znaczy zwracana wartość zegara. Kiedy wynosi ona zero?… Otóż wbrew pozorom odpowiedź na to pytanie nie jest istotna, bo w praktyce interesuje nas tylko interwał czasowy, tj. różnica między dwoma wskazaniami timera. To na jej podstawie liczymy zmianę w prędkościach obiektów, klatkach animacji czy w końcu niezbędnie konieczną do wyświetlenia wartość FPS :)

Tags: , , , ,
Author: Xion, posted under Programming » 4 comments

Stare pliki INI

2010-06-24 15:47

Jest coś takiego jak aplikacje typu portable. Charakteryzują się tym, że nie wymagają instalacji i nie zostawiają żadnych “śladów” w systemie poza swoim własnym folderem. Takie programy są praktyczne, jeśli musimy korzystać z wielu różnych, nieswoich komputerów – wtedy można je przenieść na nośniku typu pendrive i uruchamiać bezpośrednio z niego.

Oczywiście nasze własne aplikacje nie muszą należeć do tej kategorii. Inaczej musielibyśmy na przykład zrezygnować z możliwości zapisywania ustawień programu w Rejestrze… Hmm, ale czy akurat tutaj jest czego żałować? :)
Ano niekoniecznie. Dawno, dawno temu popularnym sposobem przechowywania konfiguracji były pliki o rozszerzeniu .ini. Są to bardzo proste pliki tekstowe, zawierające pary klucz-wartość pogrupowane w sekcje. Składnia takiego pliku wygląda następująco:

  1. [Sekcja1]
  2. Klucz1=42
  3. Klucz2="wartość"
  4.  
  5. [Sekcja2]
  6. Klucz="Ala ma kota"

W Windows API wciąż istnieje interfejs pozwalający na odczytywanie i zapisywanie danych z takich plików, chociaż jest on trzymany podobno tylko dla kompatybilności. Obejmuje on funkcje specjalizujące się w obsłudze konkretnego pliku – mianowicie win.ini z głównego katalogu Windows – ale także dowolnego pliku .ini o podanej przez nas nazwie. Tymi bardziej elastycznymi funkcjami są:

  • do odczytywania wartości różnych typów: GetPrivateProfileInt, GetPrivateProfileString, GetPrivateProfileStruct
  • do zapisywania wartości: WritePrivateProfileString, WritePrivateProfileStruct
  • do pobierania listy sekcji w pliku .ini (GetPrivateProfileSectionNames) oraz listy kluczy w sekcji (GetPrivateProfileSection)

Ich użycie jest dość proste. Jeśli na przykład chcielibyśmy pobrać wartość liczbową z powyższego pliku, to wystarczy poniższe wywołanie, o ile jest on zapisany w bieżącym katalogu jako plik.ini:

  1. int value = GetPrivateProfileInt("Sekcja1", "Klucz1", 0, "plik.ini");

Dość podobnie wygląda korzystanie z pozostałych funkcji operujących na pojedynczych wartościach.

Dzisiaj pliki .ini są już trochę reliktem przeszłości, ale wydaje mi się, że do niektórych prostych zastosowań nadają się całkiem dobrze. A jeśli zdarzy się ten niefortunny przypadek, iż w którejś z przyszłych wersji Windows support dla nich zostanie porzucony, to cóż… składniowo są one na tyle proste, że ich parsowanie nie powinno być problemem ;-)

Tags: ,
Author: Xion, posted under Applications, Programming » 8 comments

le ciste be fi lo’i namcu bei bau la lojban.

2010-06-22 11:47

System liczb w lojbanie.

Jako kolejny temat odnośnie lojbanu zdecydowałem się opisać jego system numeryczny, czyli sposób wyrażania liczb. W dużym stopniu zainspirował mnie do tego pewien komentarz stwierdzający, że w lojbanie – biorąc pod uwagę jego nietypowość – używa się pewnie liczb Churcha albo innej, równie pokręconej konstrukcji :) Pewnie byłoby to jakoś zgodne z jego ideą, ale na szczęście w rzeczywistości jest zupełnie inaczej ;P

Zacznijmy od prostych cyfr, które to przedstawia poniższa tabelka:

no pa re ci vo mu xa ze
0 1 2 3 4 5 6 7
bi so dau fei gai jau xei/rei vai
8 9 A (10) B (11) C (12) D (13) E (14) F (15)

Powinna ona od razu wzbudzić przyjazne uczucia, jako że wyraźnie pokazuje wielce interesujący fakt: lojban ma natywne wsparcie dla systemu szesnastkowego! I chociaż domyślnie używanym jest nadal ten dziesiętny, taka zapobiegliwość u twórców języka jest z pewnością godna uznania ;)

Nie bez powodu też ciągle używam pojęcia ‘cyfr’ zamiast ‘liczb’. Tak jak notacji matematycznej, liczby w lojbanie składa się bowiem z cyfr, i to dokładnie w ten sam, pozycyjny sposób. Powyższy zestaw słówek (są to oczywiście cmavo) jest wobec tego zupełnie wystarczający do wyrażenia każdej skończonej liczby naturalnej; nie ma żadnych osobnych form gramatycznych dla dziesiątek czy setek. Oto przykłady, które powinny ukazywać dokładną analogię między zapisem dziesiętnym a słownym w lojbanie:

paxa vore muno xaso parebi revoci repavono sononopa
16 42 50 69 128 243 2140 9001

Przy liczbach sięgających dziesiątek czy setek milionów pomocny jest separator ki’o, który jest oddziela tysiące (podobnie jak spacja w języku polskim lub przecinek w angielskim). Tak więc 4096 to vo ki’o nosoxa, a ilość bajtów w megabajcie (czyli 1048576) wyrazimy jako pa ki’o novobi ki’o muzexa. Przy okazji nadmienię, że spacje w zapisie tekstowym mogę wstawiać między cyframi w dowolny sposób (również nigdzie), co dotyczy zresztą każdego ciągu cmavo w lojbanie.

Co z większymi zbiorami liczb, jak całkowite czy wymierne? Mamy oczywiście znak minus, pozwalający tworzyć liczby ujemne: ni’u (dla spójności istnieje też znak plus: ma’u). Do ułamków niezbędny jest z kolei separator dziesiętny pi, którego nie należy mylić z liczbą π (ona sama ma zresztą swoje własne oznaczenie: pai). Wreszcie, jest też kreska ułamkowa, czyli fi’u. Przy pomocy tych słów możemy już wyrazić całkiem sporo różnych liczb:

ni’u mu re pi voxa ni’u pamu pi ze re fi’u mu
-5 2,46 -15,7 2/5

Na tym zestawie chwilowo zakończymy, mimo że lojban posiada gramatykę “obsługującą” nawet liczby zespolone (!). Ciekawsze będzie raczej pokazanie sposobu użycia liczb w wypowiedzi. W ‘normalnych’ językach liczby służą zazwyczaj do określania ilości czegoś, najczęściej w sztukach. Dość podobnie jest w lojbanie, gdzie możemy liczbą opatrzyć sumti, jak w poniższym przykładzie:

mi renro vo rokci
Rzucam czterema kamieniami.

Jako ciekawostkę mogę dodać, że powyższe bridi nie specyfikuje tego, czy były to cztery osobne rzuty czy też jeden rzut wszystkimi czterema kamieniami naraz. Możliwe jest aczkolwiek dokładniejsze określenie, ale oczywiście nie będę się tym zajmował :)


loi patlu

Drugi sposób użycia liczb to sytuacje, gdy stanowią one samodzielne sumti. Dzieje się to nieco częściej niż w innych językach, gdzie zdania typu “Dwa plus dwa równa się cztery.” są relatywnie niezbyt powszechne poza samą matematyką. Tutaj jest trochę inaczej między innymi z tego względu, że użycia wszelkich jednostek miar – takich jak metry czy kilogramy – odbywają się za pośrednictwem odpowiadających im predykatów (czyli selbri), na przykład takich jak ten:

grake :: x1 ma masę x2 gramów wg standardu x3

Miejsce (“argument”) x2 wymaga tutaj właśnie liczby jako samodzielnego sumti. Tworzymy go za pomocą rodzajnika li. Stąd mamy np. li revo – liczba 24, a także:

loi patlu poi mi te vecnu cu grake li cinono
Ziemniaki, które kupiłem, ważą 500 gramów.

Tym, jak mógłby wyglądać dialog w sklepie, który do tego zakupu doprowadził, być może zajmę się w przyszłości :)

Tags: , ,
Author: Xion, posted under Culture, Math » 4 comments

Własne kontrolki w Windows Forms

2010-06-18 22:06

Gdy tworzymy aplikacje okienkowe w .NET z użyciem Windows Forms, możemy korzystać z mnóstwa (co najmniej kilkudziesięciu) typów kontrolek dostępnych out-of-the-box. Nie wszystkie nawet mają rację bytu jako rzeczywiste kontrolki, ale w wielu przypadkach fakt, że nimi są, ułatwia korzystanie z API, które się kryje za taki komponentami. (Przykładem jest kontrolka BackgroundWorker).
Nie oznacza to jednak, że nie istnieje czasami potrzeba stworzenia własnego rodzaju kontrolki, specyficznej dla pisanego programu. Nawet jeśli miałaby ona być użyta tylko w jednym egzemplarzu, wyodrębnienie jej logiki poza zasadniczy kod aplikacji powinno wyjść im obu na dobre. W tym sensie jest ten rodzaj dodatkowej warstwy abstrakcji, który zazwyczaj opłaca się stworzyć.

Jak to się robi? Przede wszystkim należy wiedzieć, że w .NET kontrolki definiowane przez programistę mogą być jednego z trzech rodzajów. Stosunkowo najprostszym jest user control, które to stanowi po prostu pojemnik na kilka innych kontrolek zebranych w całość. Mogą to być na przykład dwa obiekty typu NumericUpDown opatrzone etykietami “Od” i “Do”, jeśli w naszym programie wielokrotnie i w różnych miejscach zachodzi potrzeba podawania przedziału liczbowego. Właściwości takiej customowej kontrolki są najczęściej bezpośrednio mapowane na właściwości kontrolek składowych, a zdarzenia są sygnalizowane w odpowiedzi na niektóre ze zdarzeń pochodzących z tychże kontrolek. W sumie więc można powiedzieć, że trochę tak jak funkcje i klasy pozwalają na wielokrotne wykorzystywanie kodu, tak user controls dają możliwość ponownego wykorzystania pewnych fragmentów UI.

Drugim typem są kontrolki dziedziczone (inherited controls). Nazwa wskazuje, że powstają one przez odziedziczenie już istniejącego rodzaju (klasy) kontrolki i dodanie do niej lub zmianę funkcjonalności. Może to obejmować dodanie nowych właściwości, częściowego lub całkowitego obsłużenia niektórych zdarzeń i inne tego typu modyfikacje zachowania kontrolki. Ważne jest tutaj to, iż efekt, jaki chcemy osiągnąć, jest na tyle zbliżony do jednej z istniejących kontrolek, że można ją wykorzystać i nie zaczynać od zera.
No ale nie zawsze tak jest i czasem naprawdę trzeba zacząć od podstaw. Jeżeli bazujemy na zupełnie abstrakcyjnym typie z góry hierarchii interfejsu – jak Control czy Component – to mamy do czynienia z kontrolką typu owner-draw. Dla niej musimy ręcznie rysować całą zawartość przy pomocy instrukcji GDI+ (stąd nazwa), opierając się przy tym na prostych zdarzeniach w rodzaju kliknięć myszy. Nie jest to więc łatwe i szybkie do wykonania zadanie.

Bywa aczkolwiek i tak, że jest ono koniecznie. Zanim się do niego zabierzemy, lepiej jednak przejrzeć alternatywy w postaci kontrolek odziedziczonych lub user controls. Możliwe, że w ten sposób zaoszczędzimy sobie pracy.

Tags: , , ,
Author: Xion, posted under Programming » 4 comments

Triki z PowerShellem #14 – Moja własna mała konsolka

2010-06-16 17:49

Jak zdołałem (mam nadzieję) pokazać w kilkunastu notkach na temat PowerShella, narzędzie to pozwala na (pół)automatyczne wykonywanie wielu niekiedy skomplikowanych operacji, o ile tylko potrafimy je zakodować w postaci odpowiednich skryptów. Możemy więc ułatwić sobie życie szybkim uploadem na serwer FTP, wysyłaniem maili, a nawet (ło kurczę!) uaktualnianiem statusu na Twitterze :) Kiedyś możemy jednak chcieć takie pojedyncze rozwiązania złożyć w jakąś większą całość – na przykład w tytułową “małą własną konsolkę”.

O co chodzi? W skrócie: o coś w rodzaju własnego shella, przyjmującego ograniczony i ściśle określony zestaw poleceń, pozwalających na wykonywanie prostych czynności. Różnica względem normalnej powłoki jest taka, iż komendy te mają być w założeniu bardzo wysokopoziomowe – każda z opisywanych dotąd przeze mnie powershellowych “sztuczek” podpadałaby pod li tylko jedno polecenie, jeśli w ogóle. Najbliższym graficznym odpowiednikiem czegoś takiego jest pasek narzędzi lub skrótów do programów.
Aby nasz mały shell stał się faktem, potrzebujemy tylko kilku rzeczy, wśród których są:

  • Pobieranie poleceń od użytkownika. Od tego mamy w PSh instrukcję Read-Host, nad którą nie ma co się rozwodzić w jakiś specjalny sposób. Ot, po prostu daje nam w wyniku linijkę tekstu wpisaną do konsoli. Jeśli użyjemy parametru Prompt, nasz shell może mieć ładny znak zachęty :)
  • Wybór właściwej akcji w zależności od wpisanej komendy. Gdybyśmy pisali “normalny” program w “normalnym” języku programowania, wtedy pewnie dodalibyśmy bazowy interfejs dla komend, potem specyficzne klasy go implementujące, a potem jeszcze fabrykę tychże… No dobra, zdecydowanie przeginam ;-) W rzeczywistości zwykły switch jest tu niemal zbytkiem, zwłaszcza że w PowerShellu posiada on pożyteczny parametr -wildcard, pozwalający na dopasowanie ciągów znaków do wzorców zawierających symbole wieloznaczne (jak np. * lub ?). Dzięki temu można ograniczyć konieczność wpisywania całych nazw poleceń, jeśli jednoznaczna jest już sama pierwsza litera ("t*" zamiast "tweet", itp.).
  • Uruchamianie programów z parametrami. Odpalenie aplikacji w powłoce takiej jak PowerShell jest oczywiście bardzo proste. Nie zapominajmy jednak, ze mamy tutaj dostęp również do API .NET-owego, w tym chociażby do klasy System.Diagonistics.Process i jej metody Start – czegoś w rodzaju arcyprzydatnej kiedyś funkcji Windows API o nazwie ShellExecute. Jeśli zaś chodzi o przekazywanie parametrów, to nie zapominajmy o metodach do obsługi stringów – cała klasa System.String jest przecież dostępna.
  • Kontrola wejścia i wyjścia. Pod Windows nie jest to specjalnie powszechne, ale zdarzają się programy “w stylu uniksowym” – przyjmujące dane ze standardowego wejścia i wypisujące wyniki na standardowe wyjście. Pamiętajmy, ze przy pomocy potokowania (operator pionowej kreski |) możemy sobie z takimi aplikacjami radzić. PowerShell jest zresztą dobrym narzędziem do tworzenia używalnych front-endów do tego rodzaju programów.
  • Pobieranie kodu wyjścia programów. W starych plikach .bat można było (hmm… w sumie to nadal można) korzystać ze zmiennej %ERRORLEVEL%, zawierającej kod wyjścia ostatnio uruchomionego programu. W PSh. jej odpowiednik ma bardziej opisową nazwę: $LASTEXITCODE. Przypomnieć warto, że dla kodów wyjścia wartością oznaczającą poprawne wykonanie programu jest zero.

Składając te elementy w całość, możemy utworzyć shella z wygodnym dla nas zestawem poleceń. Kto wie, może będzie on nam odpowiadał bardziej niż pełne ikonek, kolorowe paski narzędzi :)

Tags: , ,
Author: Xion, posted under Applications » 3 comments

Równoczesne zastępowanie kilku fraz w tekście

2010-06-12 23:22

Łańcuchy znaków w językach programowania udostępniają zwykle operację zamiany wszystkich wystąpień jednego podciągu na inny. Nawet jeśli tak nie jest (co dotyczy chociażby C++, jak zwykle), możliwe jest jej łatwe zaimplementowanie przy pomocy prostszych funkcji (jak choćby std::string::find).
Gorzej jest z nieco bardziej skomplikowaną procedurą zastępowania kilku fraz naraz. Zaznaczam od razu, że nie jest to wcale równoważne wywołaniu funkcji typu Replace parę razy dla różnych argumentów. Jeśli bowiem zastąpimy w tekście X1 przez Y1, a w wyniku X2 przez Y2, to możemy otrzymać inny rezultat niż przy dokonywaniu obu zamian równocześnie – wystarczy, że Y1 będzie w sobie zawierał ciąg X2. W celu uzyskania poprawnego wyniku należy wszystkie zamiany przeprowadzać jednocześnie.

Prosta implementacja takiej operacji może się sprowadzać do przeglądania tekstu w poszukiwaniu któregoś z podciągów do zastąpienia, a następnie dokonania faktycznej zamiany dla tego z nich, który został wykryty najwcześniej w stosunku do aktualnej pozycji w tekście. Należy następnie przesunąć się tuż za znalezioną frazę i działanie powtórzyć – i tak aż do końca tekstu. W C++ wygląda to wszystko mniej więcej tak:

  1. typedef map<string,string> StringMap;
  2. string ConcurrentReplace(const string& text, const StringMap& phrases)
  3. {
  4.     if (text.empty() || phrases.empty()) return text;
  5.  
  6.     stringstream ss;
  7.     for (size_t i = 0; i < text.length(); )
  8.     {
  9.         StringMap::const_iterator phraseIt = phrases.end();
  10.         size_t minPhrasePos = 0;
  11.         for (StringMap::const_iterator it = phrases.begin();
  12.             it != phrases.end(); ++it)
  13.         {
  14.             size_t phrasePos = text.find(it->first, i);
  15.             if (phrasePos == string::npos) continue;
  16.             if (phraseIt == phrases.end() || phrasePos < minPhrasePos)
  17.                 { phraseIt = it; minPhrasePos = phrasePos; }
  18.         }
  19.         if (phraseIt == phrases.end())   { ss << text.substr(i); break; }
  20.  
  21.         ss << text.substr(i, minPhrasePos - i);
  22.         ss << phraseIt->second;
  23.         i = minPhrasePos + phraseIt->first.length();
  24.     }
  25.     return ss.str();
  26. }

Jeśli tekst, na którym operujemy, ma długość n, a fraz do wyszukania i zastąpienia jest k, to w najgorszym przypadku całość może zabrać czas O(kn). Wymagałoby to jednak dość specyficznych danych, więc w praktyce nie musi być aż tak źle :) Dla lepszych rezultatów – zwłaszcza przy “obrabianiu” większej liczby tekstów tym samym słownikiem fraz – należałoby pewnie użyć specjalistycznych struktur danych, np. drzew prefiksowych (trie).

Tags: ,
Author: Xion, posted under Programming » 4 comments
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.