Трансформисање стрингова¶

Конверзија у низ и из низа¶

Када се током трансформисања стринга не мења његова дужина већ само неки или сви елементи, конверзија у низ може бити добар начин да се избегну многобројна преписивања података. Поступак трансформисања датог стринга s помоћу низа у општем случају тече овако:

char[] a = s.ToArray();

// obavimo potrebne izmene elemenata niza

s = new string(a);

Пошто конверзија подразумева копирање елемената колекције, у случају дугачких низова и стрингова ни конверзије не треба често изводити. У нашем примеру имамо само конверзију стринга у низ на почетку поступка и обрнуту конверзију на крају.

Такође треба водити рачуна о томе да за низ карактера a, метод a.ToString() враћа резултат „System.Char[]”, што је текстуални опис овог објекта, а не резултат конверзије објекта у стринг. Ако као вредност неког стринга добијете „System.Char[]”, вероватно сте омашком уместо наредбе облика new string(a) написали a.ToString().

Пример - формирање обрнутог стринга помоћу низа

У Приручнику је на страни 201 наведен метод Obrni, који за дати стринг s формира нови стринг са истим словима у обрнутом редоследу:

static string Obrni(string s) {
    char[] t = s.ToCharArray();
    int n = t.Length;
    for(int i = 0; i < n/2; i++) {
        char c = t[i];
        t[i] = t[n - 1 - i];
        t[n - 1 - i] = c;
    }
    return new string(t);
}

На сличан начин се од стринга може формирати и листа. Ово може да буде корисно ако је трансформација стринга таква да не знамо унапред дужину трансформисаног стринга.

List<char> a = new List<char>(s);

По обављеној трансформацији, обрнути процес прављења стринга на основу листе не може да се изведе директно, али може из два корака (што је довољно добро). Потребно је прво конвертовати листу у низ, а затим тај низ проследити као аргумент конструктору стринга:

string s = new string(a.ToArray());

Грађење стринга¶

Када неки стринг формирамо тако што почнемо од празног стринга који онда постепено допуњавамо, бољи начин да формирамо тај стринг је употреба објекта који се зове StringBuilder (градитељ стринга). Типична употреба градитеља стринга изгледа овако:

using System.Text; // imenski prostor u kome se nalazi StringBuilder
// ...

StringBuilder sb = new StringBuilder();

// ...
sb.Append(s); // pozivamo vise puta za razne stringove s

string rezultat = sb.ToString();

Однос између стринга и градитеља стринга је сличан као однос између низа и листе. Помоћу метода Append градитеља стринга се стринг који градимо продужава на врло сличан начин као што се листа продужава методом Add. Захваљујући томе се стринг може формирати са много мање реалоцирања (и преписивања) и зато је овакав приступ много ефикаснији од сличног, али наивног:

string rezultat = "";

// ...
rezultat += s; // pozivamo vise puta za razne stringove s

Пример - формирање обрнутог стринга помоћу градитеља стринга

Решимо задатак обртања стринга и употребом градитеља стринга. Потребно је само сваки карактер стринга s почев од краја ка почетку додати у градитељ стринга.

static string Obrni(string s)
{
    StringBuilder sb = new StringBuilder();
    for (int i = s.Length - 1; i >= 0; i--)
        sb.Append(s[i]);
    return sb.ToString();
}

Комбиновање метода из библиотеке¶

У неким случајевима, иако не постоји готов метод који би у једном кораку обавио потребну трансформацију, употребом више метода (или једног метода више пута) можемо да добијемо резултат који желимо.

Пример - формирање обрнутог стринга комбиновањем метода

Прегледањем списка метода класе string видимо да не постоји метод ове класе који креира обрнути стринг. Уз мало додатног трагања у именском простору System.Linq можемо наћи генерички поступак Reverse, који обрће било какву секвенцу. Резултат рада овог метода је секвенца, која се не може директно конвертовати у стринг, али може у низ карактера, који затим користимо за формирање стринга. Тако до циља стижемо у три корака:

• позивом метода Reverse добијамо секвенцу у обрнутом редоследу

• позивом метода ToArray конвертујемо ту секвенцу у низ карактера

• позивом конструктора стринга са низом као аргументом, формирамо тражени стринг

static string Obrni(string s)
{
    return new string(s.Reverse().ToArray());
}

Колико споро је споро¶

Подсетимо се искуства са листама и убацивања и избацивања појединачних елемената у, односно из листе. Видели смо да свака таква операција изазива велики број премештања других елемената, па при многоструком понављању таквих операција време рада поступка порасте до неприхватљиво спорог.

На основу тог искуства можемо очекивати да и вишеструке измене дугачког стринга могу довести до врло спорих програма. У наставку ћемо спровести експеримент попут оног са листама, у коме ћемо упоредити по перформансама различите начине обављања једне трансформације датог стринга.

Нека је потребно у датом стрингу сва слова и цифре заменити доњом цртом.

Програм који следи извршава ову трансформацију на 4 начина:

1. помоћу градитеља стринга;

2. конверзијом стринга у низ и обрнуто;

3. вишеструком применом метода Replace;

4. формирањем резултујућег стринга простим надовезивањем карактера (без употребе градитеља стринга);

У програму се мере времена рада ових поступака за стринг који се састоји од N = 10000 пута поновљене секвенце, састављене од свих енглеских слова и цифара (укупно \(N \cdot (26+26+10) = 10000 \cdot 62 = 620~000\) карактера).

Добијени су следећи резултати (ако будете извршавали овај програм, извесно ћете добити другачија времена, али ће међусобни односи тих времена бити приближно овакви):

StringBuilder:                      00:00:00.0094086
Konverzija u niz i iz niza:         00:00:00.0169987
Primena Replace slovo po slovo:     00:00:00.1088408
Nadovezivanje karaktera na string:  00:04:33.9270174

Дакле, време рада сваког од прва три поступка се изражава деловима секунде, док последњни поступак траје нешто више од четири и по минута. Видимо да је сваки од прва три поступка врло ефикасан, док је четврти екстремно неефикасан.

Поступак вишеструком применом метода Replace делује споро у односу на друга два брза поступка, а разлог томе су чак 62 извршавања овог метода и исто толико преписивања целог стринга. Да је требало заменити доњом цртом сва појављивања само једног карактера, метод Replace би био коришћен само једном и овај поступак би вероватно био најбржи.

Главни закључак је свакако да успорење због вишеструког додељивања вредности стринговима може бити врло значајно када су ти стрингови довољно велики. Због тог успорења, поновљено просто надовезивање стрингова није прихватљиво као начин трансформисања великих стрингова.

Да бисмо још боље разумели добијени резултат мерења и његове последице, приметимо да преписивање садржаја стринга s1 при сваком додавању једног карактера у поступку D чини да је време додавања једног карактера сразмерно тренутној дужини стринга, па је укупно време рада поступка D приближно сразмерно квадрату дужине стринга. У ову законитост се можемо уверити и експериментално, извршавањем програма за различите дужине стринга који трансформишемо. Због ове квадратне зависности би поступак D, на пример, за 100 пута дужи стринг трајао око 10000 пута дуже, што је око месец дана, док би се време рада осталих поступака и даље мерило секундама (тврђење за остале поступке можете лако проверити).