Posts tagged ‘strings’

Formatowanie tekstu

2010-12-12 19:03

Tematem budowania łańcuchów znaków zajmowałem się już kiedyś, badając efektywność tej operacji w C++ dla trzech różnych sposobów. Tym razem przyjrzę się sprawie z perspektywy bardziej niezależnej od języka. Ostatnio poczyniłem bowiem pewną obserwację. Zauważyłem mianowicie, że “tradycyjne” podejście do składania stringów – przez konkatenację kolejnych podciągów – staje się… hmm… niemodne, jeśli można tu użyć takiego określenia.

Ci, którzy kodują nieco dłużej niż ja pewnie zwrócą mi zaraz uwagę, że takie naprawdę tradycyjne podejście do problemu to to, które implementują funkcje z języka C podobne do printf:

  1. fprintf (stderr, "[%s] Error (errno=%d)\n", tag, errno);

Polega ono na uprzednim zdefiniowaniu wzorca tekstu (tzw. formatu, tutaj jest to drugi argument fprintf), zawierającego symbole zastępcze takie jak %s czy %d. Są one następnie zastępowane podanymi wartościami (tutaj: tag oraz errno) w celu wyprodukowania finalnego ciągu. Nie ma tu jawnej operacji łączenia dwóch napisów. Zamiast tego mały parser przegląda podany wzorzec i w miejscu symboli zastępczych wstawia do wyniku podane wartości, przepisując bez zmian resztę znaków.
Wkrótce jednak nadszedł C++ z klasami string i ostream, oferującymi podobne możliwości bez użycia wzorców. Zamiast tego posługiwały się operatorami + i << w celu wyprodukowania tekstowego wyjścia:
cerr << "[" << tag << "] Error (errno=" << errno << ")" << endl;[/cpp] To działa, ale - jak można zobaczyć w porównaniu - wygląda często znacznie mniej przejrzyście. Nie dziwi więc, że w tym względzie historia zdaje się zatoczyć koło. Obecnie bowiem operacja formatowania napisów (w sensie powyższej funkcji fprintf, a nie określania czcionki czy stylu tekstu) jest wbudowana w wiele nowoczesnych, popularnych języków programowania, jak choćby C#, Pythona czy Javę. Najczęściej też, co ciekawe, trzyma się ona z grubsza oryginalnej składni wzorców pochodzącej jeszcze z C, dodając oczywiście jakieś własne, bardziej zaawansowane rozszerzenia:

  1. exc_type, exc, _ = sys.exc_info()
  2. logging.error("[%s] %s" , exc_type.__name__, exc)
  1. Console.WriteLine("[{0}] {1}", e.GetType().Name, e.Message);

Czasami jednak – jak widać wyżej – tak nie jest :) Na obecność mechanizmu formatowania łańcuchów znaków możemy aczkolwiek liczyć w każdym szanującym się języku. I to łącznie z C++, gdzie wszystko prawie wszystko, czego w nim pierwotnie nie ma, zawiera się w jakiejś bibliotece boost – w tym przypadku jest to boost::format.

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

Split

2010-07-02 17:44

Tytuł dzisiejszej notki nie ma nic wspólnego z miejscowością wypoczynkową na południu Chorwacji, chociaż pewnie obecne temperatury nasuwają takie skojarzenia :) Zamiast tego chodzi o split łańcucha znaków, czyli bardzo często potrzebną w praktyce operację na stringach.
Danymi dla niej są najczęściej dwa napisy, zaś wynikiem jest tablica podciągów pierwszego z nich, powstała poprzez podzielenie go względem wystąpień drugiego (tzw. separatora). Ponieważ jak zwykle przykład będzie mówił najwięcej, niniejszym podaję nawet kilka:

  1. Split("Ala ma kota", " ") == { "Ala", "ma", "kota" };
  2. Split("1, 2, 3, 4", ",") == { "1", " 2", " 3", "4" };
  3. Split("<point x='23' y='14' z='-3' />", " ")
  4.     == { "<point", "x='23'", "y='14'", "z='-3'", "/>" }

Zwłaszcza ostatni pokazuje, że split jest rzeczywiście użyteczną funkcją, mogącą ułatwiać parsowanie formatów tekstowych (zwłaszcza, jeśli daje się ją zastosować wielokrotnie). Warto więc mieć takową w swoim języku/bibliotece. Jak więc przedstawia się jej dostępność na różnych platformach?

Tradycyjnie w .NET i Javie jest dobrze, a nawet lepiej. W obu przypadkach funkcja (a właściwie metoda) Split/split klasy String dodaje nawet trochę więcej możliwości niż to opisałem wyżej. I tak w .NET można podać więcej niż jeden oddzielacz, natomiast w Javie domyślnie może być nim również wyrażenie regularne.
Niektóre języki skryptowe i skryptopodobne też mają się w tym względnie całkiem dobrze. W Pythonie jest metoda split w klasie napisu, natomiast PHP ma funkcję explode, która mimo innej nazwy działa bardzo podobnie.

Ale nie wszędzie funkcja typu split jest od razu dostępna; niekiedy trzeba ją sobie samemu napisać. Przykładem języka, gdzie może być to koniecznie, jest Lua oraz – jakżeby inaczej – C++ :) Ze względu na użyteczność splita często znajdowałem się w sytuacji, gdzie konieczne/wygodne było jego napisanie. Po kilku(nastu?) takich przypadkach doszedłem wreszcie do czegoś podobnego do poniższego kodu:
typedef std::vector StringArray;
StringArray Split(const std::string& text, const std::string& delim)
{
StringArray res;
if (delim.empty()) { res.push_back(text); return res; }

std::string::size_type i = 0, j;
while (i < text.length() && (j = text.find(delim, i)) != std::string::npos) { res.push_back (text.substr(i, j - i)); i = j + delim.length(); } res.push_back (text.substr(i)); return res; }[/cpp] Na koniec zwrócę jeszcze uwagę na to, że czasami trzeba ostrożnie postępować z rezultatem splitu. Zdecydowana większość wersji tej operacji dopuszcza, by w wynikowej tablicy występowały puste ciągi. Odpowiadają one kilku kolejnym wystąpieniom separatora lub jego obecnością na początku bądź końcu ciągu. Jeśli nie są one nam potrzebne (a rzadko są), to należy je zignorować lub usunąć.

Tags: , , , , ,
Author: Xion, posted under Programming » 5 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

Argumenty w linii komend

2010-05-03 13:29

Parametry przekazywane programom podczas uruchomienia mają najczęściej formę kilku przełączników (switches), po których opcjonalnie występują właściwe dla nich argumenty. Zwyczajowo rzeczone przełączniki są poprzedzone myślnikiem (styl uniksowy) lub slashem (styl MS-DOS), jak w przykładzie poniżej:

gcc -c main.c -o main.o -pedantic

Tak skonstruowany wiersz poleceń jest przekazywany przez runtime do aplikacji C/C++ jako tablica ciągów znaków, powstałych już po podzieleniu go na części według spacji i ew. cudzysłowów. Tradycyjnie pierwszy parametr (argc) funkcji main określa liczbę tych części, zaś drugi (argv) jest wspomnianą tablicą je zawierającą. Warto pamiętać, że – jeśli interesują nas tylko argumenty wywołania – jest to tablica indeksowana od jedynki, gdyż argv[0] zawiera zawsze samo polecenie uruchamiające program (w powyższym przykładzie byłby to ciąg "gcc"). Ostatnim elementem jest z kolei argv[argc - 1], zatem w sumie tablica zawiera argc - 1 znaczących parametrów programu. Wreszcie, gwarantowane jest, iż argv[argc] jest zawsze pustym wskaźnikiem, jeśli do czegokolwiek mogłoby się to przydać.

Bezpośrednia interpretacja wiersza poleceń, który używa wspomnianych na początku przełączników, może być jednak nieco kłopotliwa. Wydaje mi się, że lepiej jest przetworzyć ją do bardziej znośnej postaci słownika (mapy), pozwalającego odwoływać się do switchy i ich argumentów po nazwie. Można to zrobić choćby w poniższy sposób:
#include
#include
#include
typedef std::map > CommandLine;

const char SWITCH_CHAR = ‘-‘; // lub ‘/’
const CommandLine ParseCommandLine(int argc, const char* argv[])
{
CommandLine cl;
for (int i = 1; i < argc; ) if (*(argv[i]) == SWITCH_CHAR) { std::vector p;
p.reserve (argc – i);

int j;
for (j = i + 1;
j < argc && (*(argv[j]) != SWITCH_CHAR || strstr(argv[j], " ")); ++j) p.push_back (argv[j]); cl.insert (std::make_pair(argv[i] + 1, p)); i = j; } else ++i; return cl; }[/cpp] W rezultacie otrzymamy mapę, w której wyszukiwanie (std::map::find) pozwoli nam określić, czy dany przełącznik był podany, zaś indeksowanie (operator []) da nam dostęp do jego parametrów w postaci wektora.

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

Unikalne łańcuchy znaków

2009-12-19 12:25

Okazjonalnie zachodzi potrzeba, aby do jakiegoś celu wygenerować niepowtarzalny ciąg znaków. Jednym z zastosowań może być tutaj nadanie plikowi nazwy gwarantującej brak kolizji z jakąkolwiek inną nazwą pliku w systemie albo chociaż w aktualnym katalogu. W przypadku gdy ów plik ma istnieć tylko przez chwilę – a więc być plikiem tymczasowym (tempfile), sprawa jest prosta i sprowadza się do wywołania GetTempFileName jako funkcji WinAPI lub metody klasy System.IO.Path z .NET.

Stworzona w ten sposób nazwa jest z definicji “krótko żyjąca”. Na drugim biegunie w zakresie unikalności znajdują się tzw. UUID-y, czyli specjalnie ustandaryzowane 128-bitowe identyfikatory konstruowane tak, by zapewnić, że prawdopodobieństwo wygenerowania duplikatów jest mikroskopijnie małe. Każdy, kto grzebał trochę w Rejestrze Windows lub miał do czynienia z technologią COM, zna na pewno ich kuzynów, czyli GUID-y, opartych w gruncie rzeczy na podobnych zasadach.
Ponieważ tworzenie nowych GUID-ów/UUID-ów jest proste, można je wykorzystać w celu uzyskania niepowtarzalnych ciągów znaków. W czystym Windows API unikalny string oparty na UUID-zie można otrzymać np. tak:

  1. #include <rpc.h>
  2. #pragma comment(lib, "rpcrt4.lib")
  3. string RandomStringViaUUID()
  4. {
  5.     UUID uuid;
  6.     if (UuidCreate(&uuid) != RPC_S_OK) return string();
  7.  
  8.     char* uuidStr;
  9.     if (UuidToStringA(&uuid, (unsigned char**)&uuidStr) != RPC_S_OK)
  10.         return string();
  11.     string res(uuidStr);
  12.     RpcStringFree (&uuidStr);
  13.     return res;
  14. }

Z kolei w .NET istnieje wyspecjalizowana klasa System.Guid, którą można wykorzystać w podobnym celu. W wyniku otrzymamy oczywiście teksty w stylu:

0DF44EAA-FF21-4412-828E-260A8728E7F1

co w wielu zastosowaniach może być strzelaniem z armaty do komara. Nie zawsze potrzebujemy przecież aż tak wielkiej unikalności, a UUID-y w formie tekstowej są długie i nieporęczne.

Są więc i inne rozwiązania, stosowalne jeśli nasz losowy ciąg musi być unikalny tylko przez stosunkowo niedługi czas, np. podczas jednego uruchomienia programu. W takim wypadku możemy użyć chociażby:

  • wartości zwracanych przez GetTickCount/QueryPerformanceCounter lub asemblerową instrukcję rdtsc. Jest to czas (lub liczba cykli procesora) od momentu rozruchu systemu, więc z definicji wartość taka nie powtórzy się w trakcie działania aplikacji. Warto wiedzieć aczkolwiek, że używanie rdtsc jest generalnie niezalecane.
  • aktualnego systemowego czasu – pobranego przez GetSystemTime z Windows API czy System.DateTime.Now z .NET – przekonwertowanego na string. Wadą jest tutaj wynikowa długość łańcucha i zbyt oczywisty format; prawdopodobnie więc należałoby jeszcze poddać go jakiemuś post-processingowi.
  • zwykłego ciągu losowych znaków. W zależności od jakości generatora liczb losowych oraz losowości początkowego ziarna seed, możemy otrzymać nawet całkiem dobre wyniki. Metoda jest dobra zwłaszcza wtedy, gdy generowanych identyfikatorów jest na tyle mało, że możemy je efektywnie przechowywać i po prostu sprawdzać, czy nowy string jeszcze nie wystąpił (przykładem mogą być uchwyty w menedżerze zasobów w silniku gry).

Najważniejsze jest to, aby właściwie dobrać metodę do sytuacji, w której potrzebujemy unikalnego łańcucha znaków. Często wystarczy coś w stylu:

  1. string s;
  2. while (rand() % MAX_LENGTH - s.length() > 0)
  3.     s += rand() % ('Z' - 'a') + 'a';

Nie myślmy nawet jednak, żeby tak stworzonego stringa używać do jakiejkolwiek formy komunikacji przez sieć. W takich przypadkach trzeba w zasadzie użyć UUID-ów.

Tags: , ,
Author: Xion, posted under Programming » 1 comment

O dwóch funkcjach do ścieżek

2007-07-31 14:53

Kolejnymi kawałkami kodu z poprzedniej wersji mojej biblioteki uniwersalnej, którym postanowiłem się przyjrzeć, były różnego rodzaju funkcje “systemowe”. Nazwa jest może trochę na wyrost, jako że dotyczyły one głównie pewnych operacji na plikach i ich nazwach. Wśród z nich znalazły więc procedury do pobierania nazw plików, ich rozszerzeń, sprawdzania istnienia plików, tworzenia całych ścieżek katalogów i tym podobne.

Ostały się też dwie najciekawsze funkcje o bardzo podobnych do siebie sygnaturach:

  1. String AbsoluteToRelativePath(const String& strBase, const String& strTarget);
  2. String RelativeToAbsolutePath(const String& strBase, const String& strTarget);

Wykonują one interesującą pracę: konwertują ścieżki względne na bezwzględne i odwrotnie. Jak wiadomo, ścieżka bezwzględna określa położenie w systemie plików w sposób jednoznaczny, np.:

  • C:\Program Files\Taphoo

oznacza podkatalog Taphoo w katalogu Program Files na dysku C – niezależnie od tego, gdzie się teraz znajdujemy. Natomiast ścieżka względna – taka jak ta:

  • ../images/logo.gif

mówi jedynie, że w celu dostania się do pliku logo.gif należy wyjść do nadrzędnego katalogu (..), a stamtąd przejść do katalogu images.

Do czego może przydać się konwersja między oboma typami ścieżek? Dobrym przykładem jest dyrektywa #include w C(++), która akceptuje ścieżki względne:

  1. #include "../Base/StrUtils.hpp"

Preprocesor musi jest rozwinąć, aby móc wstawić zawartość dołączanego pliku. Z użyciem wymienionej wyżej funkcji RelativeToAbsolutePath można łatwo dodać podobną dyrektywę do języka opisu lub skryptowego.

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


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