Глава 19. Структури от данни – съпоставка и препоръки

В настоящата тема ще съпоставим една с друга структурите данни, които разгледахме до момента, по отношение на скоростта, с която извършват основните операции (добавяне, търсене, изтриване и т.н.). Ще дадем конкретни препоръки в какви ситуации какви структури от данни да ползваме. Ще обясним кога да предпочетем хеш-таблица, кога масив, кога динамичен масив, кога множество, реализирано чрез хеш-таблица и кога балансирано дърво. Почти всички тези структури имат вградена импле­ментация в .NET Framework. От нас се очаква единствено да можем да преценяваме кога коя структура да ползваме, за да пишем ефективен и надежден програмен код.

Съдържание

• Видео
• Презентация
• Мисловни карти
• Защо са толкова важни структурите данни?
• Сложност на алгоритъм
• Сравнение на основните структури от данни
• Кога да използваме дадена структура?
• Избор на структура от данни – примери
• Външни библиотеки с .NET колекции
• Упражнения
• Решения и упътвания
• Дискусионен форум

Видео

Презентация

Мисловни карти

Защо са толкова важни структурите данни?

Може би се чудите защо отделяме толкова голямо внимание на струк­турите данни и защо ги разглеждаме в такива големи детайли? Причината е, че сме си поставили за задача да ви направим мислещи софтуерни инженери. Без да познавате добре основните структури от данни в прог­рамирането и основните компютърни алгоритми, вие не можете да бъдете добри програмисти и рискувате да си останете обикновени "занаятчии". Който владее добре структурите от данни и алгоритми и успее да си развие мисленето в посока правилното им използване, има големи шан­сове да стане добър софтуерен инженер – който анализира проблемите в дълбочина и предлага ефективни решения.

По темата защо са важни структурите от данни и алгоритмите има изписани стотици книги. Особено впечатляващи са четирите тома на Доналд Кнут, озаглавени "The Art of Computer Programming", в които структурите от данни и алгоритмите са разгледани в над 2500 страници. Един автор дори е озаглавил книга с отговора на въпроса "защо структурите от данни са толкова важни". Това е книгата на Никлаус Вирт "Алгоритми + структури от данни = програми", в която се разглеждат отново структурите данни и фундаменталните алгоритми в програмира­нето.

Структурите от данни и алгоритмите стоят в основата на програмирането. За да станете добри програмисти, е необ­ходимо да познавате основните структури от данни и алгоритми и да се научите да ги прилагате по подходящ начин.

В много голяма степен и нашата книга е насочена именно към изучава­нето на основните структури от данни и алгоритми в програмирането, като сме се стремили да ги илюстрираме в контекста на съвременното софту­ерно инженерство с .NET платформата.

Сложност на алгоритъм

Не може да се говори за ефективност на алгоритми и структури от данни, без да се използва понятието "сложност на алгоритъм", с което вече се сблъскахме няколко пъти под една или друга форма. Няма да даваме математическа дефиниция, за да не натоварваме читателите, а ще дадем неформално обяснение.

Сложност на алгоритъм е мярка, която отразява порядъка на броя операции, необходими за изпълнение на дадена операция или алгоритъм като функция на обема на входните данни. Формулирано още по-просто, сложност е груба, приблизителна оценка на броя стъпки за изпълнение на даден алгоритъм. При оценяването на сложност говорим за порядъка на броя операции, а не за техния точен брой. Например ако имаме от порядъка на N² операции за обработката на N елемента, то N²/2 и 3* N² са брой операции от един и същ квадратичен порядък. Сложността на алго­ритмите се означава най-често с нотацията О(f), където f е функция на размера (обема) на входните данни.

Сложността може да бъде константна, логаритмична, линейна, n*log(n), квадратична, кубична, експоненциална и друга. Това означава, че се изпълняват съответно от порядъка на константен, логаритмичен, линеен и т.н. брой стъпки за решаването на даден проблем.

Сложност на алгоритъм е груба оценка на броя стъпки, които алгоритъмът ще направи в зависимост от размера на входните данни. Това е груба оценка, която се интересува от порядъка на броя стъпки, а не от точния им брой.

Типични сложности на алгоритмите

Ще обясним какво означават видовете сложност чрез следната таблица:

Сложност	Означение	Описание
константна	O(1)	За извършване на дадена операция са необходими константен брой стъпки (например 1, 5, 10 или друго число) и този брой не зависи от обема на входните данни.
логаритмична	O(log(N))	За извършване на дадена операция върху N елемента са необходими брой стъпки от порядъка на log(N), където основата на логаритъма е най-често 2. Например алгоритъм със сложност O(log(N)) за N = 1 000 000 ще направи около 20 стъпки (с точност до константа). Тъй като основата на логаритъма няма съществено значение за порядъка на броя операции, тя обикновено се изпуска.
линейна	O(N)	За извършване на дадена операция върху N елемента са необходими приблизително толкова стъпки, колкото са елементите. Например за 1 000 елемента са нужни около 1 000 стъпки. Линейната сложност означава, че броят елементи и броят операции са линейно зависими, например броят стъпки за N елемента е около N/2 или 3*N.
	O(n*log(n))	За извършване на дадена операция върху N елемента са необходими приблизително N*log(N) стъпки. Например при 1 000 елемента са нужни около 10 000 стъпки.
квадратична	O(n2)	За извършване на дадена операция са необходими от порядъка на N2 на брой стъпки, където N характеризира обема на входните данни. Например за дадена операция върху 100 елемента са необходими 10 000 стъпки. Реално квадратична сложност имаме, когато броят стъпки е в квадратна зависимост спрямо обема на входните данни, например за N елемента стъпките могат да са от порядъка на 3*N2/2.
кубична	O(n3)	За извършване на дадена операция са необходими от порядъка на N3 стъпки, където N характеризира обема на входните данни. Например при 100 елемента се изпълняват около 1 000 000 стъпки.
експоненциална	O(2n), O(N!), O(nk), …	За извършване на дадена операция или изчисление са необходими брой стъпки, който е в експоненциална зависимост спрямо размера на входните данни. Например при N=10 експоненциалната функция 2N има стойност 1024, при N=20 има стойност 1 048 576, а при N=100 функцията има стойност, която е число с около 30 цифри. Експоненциалната функция N! расте още по-бързо: за N=5 има стойност 120, за N=10 има стойност 3 628 800, а за N=20 – 2 432 902 008 176 640 000.

При оценката на сложност константите не се взимат предвид, тъй като не влияят съществено на броя операции. По тази причина алгоритъм, който извършва N стъпки и алгоритми, които извършват съответно N/2 и 3*N стъпки се считат за линейни и за приблизително еднакво ефективни, тъй като извършват брой операции, които са от един и същ порядък.

Сложност и време за изпълнение

Скоростта на изпълнение на програмата е в пряка зависимост от слож­ността на алгоритъма, който се изпълнява. Ако тази сложност е малка, програмата ще работи бързо, дори за голям брой елементи. Ако слож­ността е голяма, програмата ще работи бавно или въобще няма да работи (т.е. ще заспи) при голям брой елементи.

Ако вземем един средностатистически компютър от 2008 година, можем да приемем, че той изпълнява около 50 000 000 елементарни операции в секунда. Разбира се, това число трябва да ви служи единствено за груб ориентир. Различните процесори работят с различна скорост и различните елементарни операции се изпълняват с различна скорост, а и компютър­ната техника постоянно напредва. Все пак, ако приемем, че използваме средностатистически домашен компютър от 2008 г., можем да направим следните изводи за скоростта на изпълнение на дадена програма в зави­симост от сложността на алгоритъма и обема на входните данни:

алгоритъм	10	20	50	100	1 000	10 000	100 000
O(1)	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.
O(log(n))	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.
O(n)	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.
O(n*log(n))	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.
O(n2)	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	2 сек.	3-4 мин.
O(n3)	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	20 сек.	5.55 часа	231.5 дни
O(2n)	< 1 сек.	< 1 сек.	260 дни	зас­пива	зас­пива	зас­пива	зас­пива
O(n!)	< 1 сек.	зас­пива	зас­пива	зас­пива	зас­пива	зас­пива	зас­пива
O(nn)	3-4 мин.	зас­пива	зас­пива	зас­пива	зас­пива	зас­пива	зас­пива

От таблицата можем да направим много изводи:

-     Алгоритми с константна, логаритмична и линейна сложност са тол­кова бързи, че не можем да усетим забавяне, дори при относително голям размер на входните данни.

-     Сложността O(n*log(n)) е близка до линейната и също работи толкова, бързо, че трудно можем да усетим забавяне.

-     Квадратични алгоритми работят добре до няколко хиляди елемента.

-     Кубични алгоритми работят добре при под 1 000 елемента.

-     Като цяло т.нар. полиномиални алгоритми (тези, които не са експо­ненциални) се считат за бързи и работят добре за хиляди елементи.

-     Експоненциалните алгоритми като цяло не работят и трябва да ги избягваме (когато е възможно). Ако имаме експоненциално решение за дадена задача, може да се каже, че всъщност нямаме решение, защото то ще работи само ако елементите са под 10-20. Съвремен­ната криптография разчита точно на това – че не са известни бързи (неекспоненциални) алгоритми за откриване на тайните ключове, които се използват за шифриране на данните.

Ако решите една задача с експоненциална сложност, това означава, че сте я решили само за много малък размер на входните данни и в общия случай решението ви не работи.

Разбира се, данните в таблицата са само ориентировъчни. Понякога може да се случи линеен алгоритъм да работи по-бавно от квадратичен или квадратичен да работи по-добре от O(n*log(n)). Причините за това могат да са много:

-     Възможно е константите за алгоритъм с малка сложност да са големи и това да направи алгоритъма бавен като цяло. Например, ако имаме алгоритъм, който прави 50*n стъпки и друг, който прави 1/100*n*n стъпки, то за стойности до 5000 квадратичният алгоритъм е по-бърз от линейния.

-     Понеже оценката на сложността се прави за най-лошия случай, е възможно квадратичен алгоритъм да работи по-добре от алгоритъм O(n*log(n)) в 99% от случаите. Можем да дадем пример с алгори­тъма QuickSort (стандартния за .NET Framework сортиращ алгоритъм), който в средния случай работи малко по-добре от MergeSort (сортиране чрез сливане), но в най-лошия случай QuickSort прави от порядъка на n² стъпки, докато MergeSort прави винаги O(n*log(n)) стъпки.

-     Възможно е алгоритъм, който е оценен, че работи с линейна слож­ност, да не работи толкова бързо, колкото се очаква заради неточна оценка на сложността. Например, ако търсим дадена дума в масив от думи, сложността е линейна, но на всяка стъпка се извършва срав­нение на символни низове, което не е елементарна операция и може да отнеме много повече време, отколкото извършването на една елементарна операция (например сравнение на два символни низа).

Сложност по няколко променливи

Сложността може да зависи и от няколко входни променливи едновре­менно. Например, ако търсим елемент в правоъгълна матрица с размери M на N, то скоростта на търсенето зависи и от M и от N. Понеже в най-лошия случай трябва да обходим цялата матрица, то ще направим най-много M*N на брой стъпки. Така сложността се оценява като O(M*N).

Най-добър, най-лош и среден случай

Сложността на алгоритмите се оценява обикновено в най-лошия случай (при най-неблагоприятния сценарий). Това означава, че в средния случай те могат да работят и по-бързо, но в най-лошия случай работят с посоче­ната сложност и не по-бавно.

Да вземем един пример: търсене на елемент в масив по даден ключ. За да намерим търсения ключ, трябва да проверим в най-лошия случай всички елементи на масива. В най-добрия случай ще имаме късмет и ще намерим търсения ключ още в първия елемент. В средния случай можем да очак­ваме да проверим средно половината елементи на масива докато намерим търсения. Следователно в най-лошия случай сложността е O(N), т.е. ли­нейна. В средния случай сложността е O(N/2) = O(N), т.е. отново линейна, защото при оценяване на сложност константите се пренебрегват. В най-добрия случай имаме константна сложност O(1), защото изпълняваме само една стъпка и с нея директно откриваме търсения елемент.

Приблизително оценена сложност

Понякога е трудно да оценим точно сложността на даден алгоритъм, тъй като изпълняваме операции, за които не знаем точно колко време отнемат и колко стъпки изпълняват вътрешно. Да вземем за пример търсенето на дадена дума в масив от символни низове (текстове). Задачата е лесна: трябва да обходим масива и във всеки от текстовете да търсим със Substring() или с регулярен израз дадената дума. Можем да си зададем въпроса: ако имаме 10 000 текста, това бързо ли ще работи? А какво ще стане ако текстовете са 100 000? Ако помислим внимателно, ще устано­вим, че за да оценим адекватно скоростта на търсенето, трябва да знаем колко са обемни текстовете, защото има разлика между търсене в имена на хора (които са до около 100 символа) и търсене в научни статии (които  са съставени от средно 20 000 – 30 000 символа). Все пак можем да оценим сложността спрямо обема на текстовете, в които търсим: тя е най-малко O(L), където L е сумата от дължините на всички текстове. Това е доста груба оценка, но е много по-точна, отколкото да кажем, че сложността е O(N), където N е броят текстове, нали? Трябва да помислим дали взимаме предвид всички ситуации, които биха могли да възникнат. Има ли значение колко дълга дума търсим в масива от текстове? Вероятно търсенето на дълги думи работи по-бавно от търсенето на кратки думи. Всъщност нещата стоят малко по-различно. Ако търсим "aaaaaaa" в текста "aaaaaabaaaaacaaaaaabaaaaacaaaaab", това ще е по-бавно, отколкото ако търсим "xxx" в същия текст, защото в първия случай ще имаме много повече поредици съвпадения, отколкото във втория. Следователно при някои специални ситуации, търсенето зависи съществено и от дължината на търсената дума и оценката O(L) може да се окаже силно занижена.

Сложност по памет

Освен броя стъпки чрез функция на входните данни могат да се измерват и други ресурси, които алгоритъма използва, например памет, брой дис­кови операции и т.н. За някои алгоритми скоростта на изпълнение не е толкова важна, колкото обема на паметта, която ползват. Например, ако един алгоритъм е линеен, но използва оперативна памет от порядъка на N², той вероятно ще страда от недостиг на памет при N=100 000 (тогава ще му трябват от порядъка на 9 GB оперативна памет), въпреки, че би следвало да работи много бързо.

Оценяване на сложност – примери

Ще дадем няколко примера, с които ще ви покажем как можете да оценявате сложността на вашите алгоритми и да преценявате дали ще работи бързо написаният от вас програмен код:

Ако имаме единичен цикъл от 1 до N, сложността му е линейна – O(N):

int FindMaxElement(int[] array) {           int max = int.MinValue;           for (int i = 1; i < array.Length; i++)           {                    if (array[i] > max)                    {                              max = array[i];                    }           }           return max; }

Този код ще работи добре, дори при голям брой елементи.

Ако имаме два вложени цикъла от 1 до N, сложността им е квадратична – O(N²). Пример:

int FindInversions(int[] array) {       int inversions = 0;       for (int i = 0; i < array.Length - 1; i++)       {             for (int j = i + 1; j < array.Length; j++)             {                   if (array[i] > array[j])                              {                         inversions++;                              }                    }           }       return inversions; }

Този код ще работи добре, ако елементите не са повече от няколко хиляди или десетки хиляди.

Ако имаме три вложени цикъла от 1 до N, сложността им е кубична – O(N³). Пример:

long Sum3(int n) {       long sum = 0;       for (int a = 1; a < n; a++)       {             for (int b = 1; b < n; b++)             {                   for (int c = 1; c < n; c++)                   {                         sum += a * b * c;                   }             }       }       return sum; }

Този код ще работи добре, ако елементите в масива са под 1 000.

Ако имаме два вложени цикъла съответно от 1 до N и от 1 до M, сложността им е квадратична – O(N*М). Пример:

long SumMN(int n, int m) {       long sum = 0;       for (int x = 1; x <= n; x++)       {             for (int y = 1; y <= m; y++)             {                   sum += x * y;             }       }       return sum; }

Скоростта на този код зависи от две променливи. Кодът ще работи добре, ако M, N < 10 000 или ако поне едната променлива има достатъчно малка стойност.

Трябва да обърнем внимание на факта, че не винаги три вложени цикъла означават кубична сложност. Ето един пример, при който сложността е O(N*M):

long SumMN(int n, int m) {       long sum = 0;       for (int x = 1; x <= n; x++)       {             for (int y = 1; y <= m; y++)             {                   if (x == y)                   {                         for (int i = 1; i <= n; i++)                         {                               sum += i * x * y;                         }                   }             }       }       return sum; }

В този пример най-вътрешният цикъл се изпълнява точно min(M, N) пъти и не оказва съществено влияние върху скоростта на алгоритъма. Горният код изпълнява приблизително N*M + min(M,N)*N стъпки, т.е. сложността му е квадратична.

При използване на рекурсия сложността е по-трудно да се определи. Ето един пример:

long Factorial(int n) {       if (n == 0)       {             return 1;       }       else       {             return n * Factorial(n - 1);       } }

В този пример сложността е очевидно линейна – О(N), защото функцията factorial() се изпълнява точно веднъж за всяко от числата 1, 2, ..., n.

Ето една рекурсивна функция, за която е много по-трудно да се сметне сложността:

long Fibonacci(int n) {       if (n == 0)       {             return 1;       }       else if (n == 1)       {             return 1;       }       else       {             return Fibonacci(n - 1) + Fibonacci(n - 2);       } }

Ако разпишем какво се случва при изпълнението на горния код, ще установим, че функцията се извиква толкова пъти, колкото е числото на Фибоначи с номер n+1. Можем грубо да оценим сложността и по друг начин: понеже на всяка стъпка от изпълнението на функцията се извърш­ват средно по 2 рекурсивни извиквания, то броят рекурсивни извиквания би трябвало да е от порядъка на 2ⁿ, т.е. имаме експоненциална сложност. Това автоматично означава, че са стойности над 20-30 функцията "ще зависне".

Същата функция за изчисление на n-тото число на Фибоначи можем да напишем с линейна сложност по следния начин:

long Fibonacci(int n) {       long fn = 1;       long fn1 = 1;       long fn2 = 1;       for (int i = 2; i < n; i++)       {             fn = fn1 + fn2;             fn2 = fn1;             fn1 = fn;       }       return fn; }

Виждате, че оценката на сложността ни помага да предвидим, че даден код ще работи бавно, още преди да сме го изпълнили и ни подсказва, че трябва да търсим по-ефективно решение.

Сравнение на основните структури от данни

След като се запознахме с понятието сложност на алгоритъм, вече сме готови да направим съпоставка на основните структури от данни, които разгледахме до момента, и да оценим с каква сложност всяка от тях извършва основните операции като добавяне, търсене, изтриване и други. Така ще можем лесно да съобразяваме според операциите, които са ни необходими, коя структура от данни ще е най-подходяща. В таблицата по-долу са дадени сложностите на основните операции при основните струк­тури данни, които разгледахме в предходните глави:

структура	доба­вяне	търсене	изтри­ване	достъп по индекс
масив (Т[])	O(N)	O(N)	O(N)	О(1)
свързан списък (LinkedList<Т>)	О(1)	O(N)	O(N)	O(N)
динамичен масив (List<T>)	О(1)	O(N)	O(N)	O(1)
стек (Stack<Т>)	О(1)	-	О(1)	-
опашка (Queue<Т>)	О(1)	-	О(1)	-
речник реализиран с хеш-таблица (Dictionary<K, T>)	О(1)	О(1)	О(1)	-
речник реализиран с балансирано дърво (SortedDictionary<K, T>)	О(log(N))	О(log(N))	О(log(N))	-
множество реализирано с хеш-таблица (HashSet<T>)	О(1)	О(1)	О(1)	-
множество реализирано с балансирано дърво (SortedSet<T>)	О(log(N))	О(log(N))	О(log(N))	-

Оставяме на читателя да помисли как точно се получават тези сложности.

Кога да използваме дадена структура?

Нека разгледаме всяка от посочените в таблицата структури от данни поотделно и обясним в какви ситуации е подходящо да се ползва такава структура и как се получават сложностите, дадени в таблицата.

Масив (T[])

Масивите са наредени съвкупности от фиксиран брой елементи от даден тип (например числа), до които достъпът става по индекс. Масивите пред­ставляват област от паметта с определен, предварително зададен размер. Добавянето на нов елемент в масив е много бавна операция, защото реално трябва да се задели нов масив с размерност по-голяма с 1 от теку­щата и да се прехвърлят старите елементи в новия масив. Търсенето в масив изисква сравнение на всеки елемент с търсената стойност. В средния случай са необходими N/2 сравнения. Изтриването от масив е много бавна операция, защото е свързана със заделяне на масив с размер с 1 по-малък от текущия и преместване на всички елементи без изтрития в новия масив. Достъпът по индекс става директно и затова е много бърза операция.

Масивите трябва да се ползват само когато трябва да обработим фиксиран брой елементи, до които е необходим достъп по индекс. Например, ако сортираме числа, можем да запишем числата в масив и да приложим някой от добре известните алгоритми за сортиране. Когато по време на работа е необходимо да променяме броя елементи, с които работим, масивът не е подходяща структура от данни.

Използвайте масиви, когато трябва да обработите фикси­ран брой елементи, до които ви е необходим достъп по индекс.

Свързан / двусвързан списък (LinkedList<Т>)

Свързаният списък и неговият вариант двусвързан списък съхраняват наредена съвкупност от елементи. Добавянето е бърза операция, но е малко по-бавна от добавяне в List<T>, защото всяко добавяне заделя памет. Заделянето на памет работи със скорост, която трудно може да бъде предвидена. Търсенето в свързан списък е бавна операция, защото е свързано с обхождане на всички негови елементи. Достъпът до елемент по индекс е бавна операция, защото в свързания списък няма индексиране и се налага обхождане на списъка, започвайки от началния елемент и придвижвайки се напред елемент по елемент. Изтриването на елемент по индекс е бавна операция, защото достигането до елемента с посочения индекс е бавна операция. Изтриването по стойност на елемент също е бавно, защото включва в себе си търсене.

Свързаният списък може бързо (с константна сложност) да добавя и изтрива елементи от двата си края, поради което е удобен за имплемен­тация на стекове, опашки и други подобни структури.

Свързан списък в практиката се използва много рядко, защото дина­мично-разширяемият масив (List<Т>) изпълнява почти всички операции, които могат да бъдат изпълнени с LinkedList, но за повечето от тях работи по-бързо и по-удобно.

Ползвайте List<T>, когато ви трябва свързан списък – той работи не по-бавно, а ви дава по-голяма бързина и удобство. Ползвайте LinkedList, ако има нужда от добавяне и изтриване на елементи в двата края на структурата.

Използвайте свързан списък (LinkedList<T>), когато трябва да добавяте и изтри­вате елементи от двата края на списъка. В про­тивен случай ползвайте List<T>.

Динамичен масив (List<T>)

Динамичният масив (List<T>) е една от най-използваните в практиката структура от данни. Той няма фиксиран размер, както масивите, и позволява директен достъп по индекс, за разлика от свързания списък (LinkedList<T>). Динамичният масив е известен още с наименованията "списък реализиран с масив" и "динамично-разширяем масив".

List<T> вътрешно съхранява елементите си в масив, който има размер по-голям от броя съхранени елементи. При добавяне на елемент обикновено във вътрешния масив има свободно място и затова тази операция отнема константно време. Понякога масивът се препълва и се налага да се разшири. Това отнема линейно време, но се случва много рядко. В крайна сметка при голям брой добавяния усреднената сложност на добавянето на елемент към List<T> е константна – O(1). Тази усреднена сложност се нарича амортизирана сложност. Амортизирана линейна сложност озна­чава, че ако добавим последователно 10 000 елемента, ще извършим сумарно брой стъпки от порядъка на 10 000 и болшинството от тях ще се изпълнят за константно време, а останалите (една много малка част) ще се изпълнят за линейно време.

Търсенето в List<T> е бавна операция, защото трябва да се обходят всички елементи. Изтриването по индекс или по стойност се изпълнява за линейно време. Изтриването е бавна операция, защото е свързана с преместване на всички елементи, които са след изтрития с една позиция наляво. Достъпът по индекс в List<T> става непосредствено, за кон­стантно време, тъй като елементите се съхраняват вътрешно в масив.

На практика List<T> комбинира добрите страни на масивите и на списъците, заради което е предпочитана структура данни в много ситуа­ции. Например, ако трябва да обработим текстов файл и да извлечем от него всички думи, отговарящи на даден регулярен израз, най-удобната структура, в която можем да ги натрупваме, е List<T>, тъй като ни трябва списък, чиято дължина не е предварително известна и който да нараства динамично.

Динамичният масив (List<T>) е подходящ, когато трябва често да доба­вяме елементи и искаме да запазваме реда им на добавяне и да ги достъпваме често по индекс. Ако често търсим или изтриваме елемент, List<T> не е подходяща структура.

Ползвайте List<T>, когато трябва бързо да добавяте елементи и да ги достъпвате по индекс.

Стек (Stack)

Стекът е структура от данни, в която са дефинирани 3 операции: добавя­не на елемент на върха на стека, изтриване на елемент от върха на стека и извличане на елемент от върха на стека без премахването му. Всички тези операции се изпълняват бързо, с константна сложност. Операциите търсене и достъп по индекс не се поддържат.

Стекът е структура с поведение LIFO (last in, first out) – последен влязъл, пръв излязъл. Използва се, когато трябва да моделираме такова поведе­ние, например, ако трябва да пазим пътя до текущата позиция при рекур­сивно търсене.

Ползвайте стек, когато е необходимо да реализирате поведението "последен влязъл, пръв излязъл" (LIFO).

Опашка (Queue)

Опашката е структура от данни, в която са дефинирани две операции: добавяне на елемент и извличане на елемента, който е наред. Тези две операции се изпълняват бързо, с константна сложност, тъй като опашката обикновено се имплементира чрез свързан списък. Припомняме, че свър­заният списък може да добавя и изтрива бързо елементи в двата си края.

Поведението на структурата опашка е FIFO (first in, first out) – пръв влязъл, пръв излязъл. Операциите търсене и достъп по индекс не се поддържат. Опашката по естествен начин моделира списък от чакащи хора, задачи или други обекти, които трябва да бъдат обработени последователно, в реда на постъпването им.

Като пример за използване на опашка можем да посочим реализацията на алгоритъма "търсене в ширина", при който се започва от даден начален елемент и неговите съседи се добавят в опашка, след което се обработват по реда им на постъпване, а по време на обработката им техните съседи се добавят към опашката. Това се повтаря докато не се достигне до даден елемент, който търсим.

Ползвайте опашка, когато е необходимо да реализирате поведе­нието "пръв влязъл, пръв излязъл" (FIFO).

Речник, реализиран с хеш-таблица (Dictionary<K,T>)

Структурата "речник" предполага съхраняване на двойки ключ-стойност и осигурява бързо търсене по ключ. При реализацията с хеш-таблица (класа Dictionary<K,T>) в .NET Framework) добавянето, търсенето и изтриването на елементи работят много бързо – със константна сложност в средния случай. Операцията достъп по индекс не е достъпна, защото елементите в хеш-таблицата се нареждат по почти случаен начин и редът им на постъпване не се запазва.

Dictionary<K,T> съхранява вътрешно елементите си в масив, като поставя всеки елемент на позиция, която се дава от хеш-функцията. По този начин масивът се запълва частично – в някои клетки има стойност, докато други стоят празни. Ако трябва да се поставят няколко стойности в една и съща клетка, те се нареждат в свързан списък (chaining). Това е един от начините за решаване на проблема с колизиите. Когато степента на запълненост на хеш-таблицата надвиши 100% (това е стойността по подразбиране на параметъра load factor), размерът й нараства двойно и всички елементи заемат нови позиции. Тази операция работи с линейна сложност, но се изпълнява толкова рядко, че амортизираната сложност на операцията добавяне си остава константа.

Хеш-таблицата има една особеност: при неблагоприятно избрана хеш-функция, предизвикваща много колизии, основните операции могат да станат доста неефективни и да достигнат линейна сложност. В практи­ката, обаче, това почти не се случва. Затова се счита, че хеш-таблицата е най-бързата структура от данни, която осигурява добавяне и търсене по ключ.

Хеш-таблицата в .NET Framework предполага, че всеки ключ се среща в нея най-много веднъж. Ако запишем последователно два елемента с един и същ ключ, последният постъпил ще измести предходния и в крайна сметка ще изгубим единия елемент. Това е важна особеност, с която трябва да се съобразяваме.

Понякога се налага в един ключ да съхраняваме няколко стойности. Това не се поддържа стандартно, но можем да ползваме List<Т> като стойност за този ключ и в него да натрупваме поредица от елементи. Например ако ни трябва хеш-таблица Dictionary<int, string>, в която да натрупваме двойки {цяло число, символен низ} с повторения, можем да ползваме Dictionary<int, List<string>>.

Хеш-таблица се препоръчва да се използва винаги, когато ни трябва бързо търсене по ключ. Например, ако трябва да преброим колко пъти се среща в текстов файл всяка дума измежду дадено множество думи, можем да ползваме Dictionary<string, int> като ползваме за ключ търсените думи, а за стойност – колко пъти се срещат във файла.

Ползвайте хеш-таблица, когато искате бързо да добавяте елементи и да търсите по ключ.

Много програмисти (най-вече начинаещите) живеят със заблудата, че основното предимство на хеш-таблицата е в удобството да търсим дадена стойност по нейния ключ. Всъщност основното предимство въобще не е това. Търсене по ключ можем да реализираме и с масив и със списък и дори със стек. Няма проблем, всеки може да ги реализира. Можем да си дефинираме клас Entry, който съхранява ключ и стойност и да си работим с масив или списък от Entry елементи. Можете да си реализираме търсене, но при всички положения то ще работи бавно. Това е големият проблем при списъците и масивите – не предлагат бързо търсене. За разлика от тях хеш-таблицата може да търси бързо и да добавя бързо нови елементи.

Основното предимство на хеш-таблицата пред останалите структури от данни е изключително бързото търсене и добавяне на елементи. Удобството на работа е второстепенен фактор.

Речник, реализиран с дърво (SortedDictionary<K,T>)

Реализацията на структурата от данни "речник" чрез червено-черно дърво (класът SortedDictionary<K,T>) е структура, която позволява съхранение на двойки ключ-стойност, при което ключовете са подредени (сортирани) по големина. Структурата осигурява бързо изпълнение на основните опе­рации (добавяне на елемент, търсене по ключ и изтриване на елемент). Сложността, с която се изпълняват тези операции, е логаритмична – O(log(N)). Това означава 10 стъпки при 1000 елемента и 20 стъпки при 1 000 000 елемента.

За разлика от хеш-таблиците, където при лоша хеш-функция може да се достигне до линейна сложност на търсенето и добавянето, при структу­рата SortedDictionary<K,T> броят стъпки за изпълнение на основните операции в средния и в най-лошия случай е един и същ – log₂(N). При балансираните дървета няма хеширане, няма колизии и няма риск от използване на лоша хеш-функция.

Отново, както при хеш-таблиците, един ключ може да се среща в струк­турата най-много веднъж. Ако искаме да поставяме няколко стойности под един и същ ключ, трябва да ползваме за стойност на елементите някакъв списък, например List<Т>.

SortedDictionary<K,T> държи вътрешно елементите си в червено-черно балансирано дърво, подредени по ключа. Това означава, че ако обходим структурата (чрез нейния итератор или чрез foreach цикъл в C#), ще получим елементите сортирани в нарастващ ред по ключа им. Понякога това може да е много полезно.

Използвайте SortedDictionary<K,T> в случаите, в които е необходима структура, в която бързо да добавяте, бързо да търсите и имате нужда от извличане на елементите, сортирани в нарастващ ред. В общия случай Dictionary<K,T> работи малко по-бързо от SortedDictionary<K,T> и е за предпочитане.

Като пример за използване на SortedDictionary<K,T> можем да дадем следната задача: да се намерят всички думи в текстов файл, които се срещат точно 10 пъти и да се отпечатат по азбучен ред. Това е задача, която можем да решим също така успешно и с Dictionary<K,T>, но ще ни се наложи да направим едно сортиране повече. При решението на тази задача можем да използваме SortedDictionary<string, int> и да преми­нем през всички думи от текстовия файл като за всяка от тях да запазваме в сортирания речник по колко пъти се среща във файла. След това можем да преминем през всички елементи на речника и да отпеча­таме тези от тях, в които броят срещания е точно 10. Те ще бъдат подре­дени по азбучен ред, тъй като това в естествената вътрешна наредба на сортирания речник.

Използвайте SortedDictionary<K,T>, когато искате бързо да добавяте елементи и да търсите по ключ и елементите ще ви трябват след това сортирани по ключ.

Множество, реализирано с хеш-таблица (HashSet<Т>)

Структурата от данни "множество" представлява съвкупност от елементи, сред които няма повтарящи се. Основните операции са добавяне на еле­мент към множеството, проверка за принадлежност на елемент към мно­жеството (търсене) и премахване на елемент от множеството (изтриване). Операцията търсене по индекс не се поддържа, т.е. нямаме директен достъп до елементите по пореден номер, защото в тази структура поредни номера няма.

Множество, реализирано чрез хеш-таблица (класът HashSet<Т>), е частен случай на хеш-таблица, при който имаме само ключове, а стойностите, записани под всеки ключ са без значение. Този клас е включен в .NET Framework едва от версия 3.5 нататък.

Както и при хеш-таблицата, основните операции в структурата от данни HashSet<Т> са реализирани с константна сложност O(1). Както и при хеш-таблицата, при неблагоприятна хеш-функция може да се стигне до ли­нейна сложност на основните операции, но в практиката това почти не се случва.

Като пример за използването на HashSet<Т> можем да посочим задачата за намиране на всички различни думи в даден текстов файл.

Ползвайте HashSet<Т>, когато трябва бързо да добавяте еле­менти към множество и да проверявате дали даден еле­мент е от множеството.

Множество, реализирано с дърво (SortedSet<Т>)

Множество, реализирано чрез червено-черно дърво, е частен случай на SortedDictionary<K,T>, в който ключовете и стойностите съвпадат.

Както и при SortedDictionary<K,T> структурата, основните операции в SortedSet<T> са реализирани с логаритмична сложност O(log(N)), като тази сложност е една и съща и в средния и в най-лошия случай.

Като пример за използването на SortedSet<T> можем да посочим задачата за намиране на всички различни думи в даден текстов файл и отпечат­ването им подредени по азбучен ред.

Използвайте SortedSet<Т>, когато трябва бързо да добавяте елементи към множество и да проверявате дали даден елемент е от множеството и освен това елементите ще ви трябват сортирани в нарастващ ред.

Избор на структура от данни – примери

Сега ще дадем няколко задачи, при които изборът на подходяща струк­тура от данни е от решаващо значение за ефективността на тяхното решение. Целта е да ви покажем типични ситуации, в които се използват разгледаните структури от данни и да ви научим в какви ситуации какви структури от данни да използвате.

Генериране на подмножества

Дадено е множество от символни низове S, например S = {море, бира, пари, кеф}. Да се напише програма, която отпечатва всички подмно­жества на S.

Задачата има много и различни по идея решения, но ние ще се спрем на следното решение: Започваме от празно подмножество (с 0 елемента):

{}

Към него добавяме всеки от елементите на S и получаваме съвкупност от подмножества с по 1 елемент:

{море}, {бира}, {пари}, {кеф}

Към всяко от получените едноелементни подмножества добавяме всеки от елементите на S, който все още не се съдържа в съответното подмно­жество и получаваме всички двуелементни подмножества:

{море, бира}, {море, пари}, {море, кеф},  {бира, пари}, {бира, кеф}, {пари, кеф}

Ако продължим по същия начин, ще получим всички 3-елементни подмно­жества и след тях 4-елементните т. н. до N-елементните подмножества.

Как да реализираме този алгоритъм? Трябва да изберем подходящи струк­тури от данни, нали?

Можем да започнем с избора на структурата, която съхранява началното множество от елементи S. Тя може да е масив, свързан списък, динамичен масив (List<string>) или множество, реализи­рано като SortedSet<string> или HashSet<string>. За да си отговорим на въпроса коя структура е най-подходяща, нека помислим кои са операциите, които ще трябва да извършваме върху тази структура. Сещаме се само за една операция – обхождане на всички елементи на S. Тази операция може да бъде реализирана ефективно с всяка от изброените структури. Избираме масив, защото е най-простата структура от възможните и с него се работи най-лесно.

Следва да изберем структурата, в която ще съхраняваме едно от подмно­жествата, които генерираме, например {море, кеф}. Отново си задаваме въпроса какви са операциите, които извършваме върху такова подмноже­ство от думи. Операциите са проверка за съществуване на елемент и добавяне на елемент, нали? Коя структура реализира бързо тази двойка операции? Масивите и списъците не търсят бързо, речниците съхраняват двойки ключ-стойност, което не е нашия случай. Остана да видим струк­турата множество. Тя поддържа бързо търсене и бързо добавяне. Коя имплементация да изберем – SortedSet<string> или HashSet<string>? Нямаме изискване за сортиране на думите по азбучен ред, така че избираме по-бързата имплементация – HashSet<string>.

Остана да изберем още една структура от данни – структурата, в която съхраняваме съвкупност от подмножества от думи, например:

{море, бира}, {море, пари}, {море, кеф},  {бира, пари}, {бира, кеф}, {пари, кеф}

В тази структура трябва да можем да добавяме, както и да обхождаме елементите й последователно. На тези изисквания отговарят структурите списък, стек, опашка и множество. Във всяка от тях можем да добавяме бързо и да обхождаме елементите й. Ако разгледаме внимателно алгори­тъма за генериране на подмножествата, ще забележим, че всяко от тях се обработва в стил "пръв генериран, пръв обработен". Подмножеството, което първо е било получено първо, се обработва първо и от него се получават подмножествата с 1 елемент повече, нали? Следователно на нашия алгоритъм най-точно ще пасне структурата от данни опашка. Можем да опишем алгоритъма така:

1.  Започваме от опашка, съдържаща празното множество {}.

2.  Взимаме поредния елемент subset от опашката и към него се опитваме да добавим всеки елемент от S, който не се съдържа в subset. Резултатът е множество, което добавяме към опашката.

3.  Повтаряме предходната стъпка докато опашката свърши.

Виждате, че с разсъждения стигнахме до класическия алгоритъм "търсене в ширина". След като знаем какви структури от данни да използваме, имплементацията става бързо и лесно. Ето как би могла да изглежда тя:

string[] words = {"море", "бира", "пари", "кеф"}; Queue<HashSet<string>> subsetsQueue =       new Queue<HashSet<string>>(); HashSet<string> emptySet = new HashSet<string>(); subsetsQueue.Enqueue(emptySet); while (subsetsQueue.Count > 0) {       HashSet<String> subset = subsetsQueue.Dequeue();             // Print current subset       Console.Write("{ ");       foreach (string word in subset)       {             Console.Write("{0} ", word);       }       Console.WriteLine("}");         // Generate and enqueue all possible child subsets       foreach (string element in words)       {             if (! subset.Contains(element))             {                   HashSet<string> newSubset = new HashSet<string>();                   newSubset.UnionWith(subset);                   newSubset.Add(element);                   subsetsQueue.Enqueue(newSubset);                                        }       } }

Ако изпълним горния код, ще се убедим, че той генерира успешно всички подмножества на S, но някои от тях ги генерира по няколко пъти:

{ } { море } { бира } { пари } { кеф } { море бира } { море пари } { море кеф } { бира море } ...

В примера множествата { море бира } и { бира море } са всъщност едно и също множество. Изглежда не сме се сетили за повторенията, които се получават при разбъркване на реда на елементите на едно и също множество. Как можем да ги избегнем?

Да номерираме думите по техните индекси:

море à 0

бира à 1

пари à 2

кеф à 3

Понеже подмножествата {1, 2, 3} и {2, 1, 3} са всъщност едно и също подмножество, за да нямаме повторения, ще наложим изискването да генерираме само подмножества, в които индексите са подредени по големина. Можем вместо множества от думи да пазим множества от индекси, нали? В тези множества от индекси ни трябват две операции: добавяне на индекс и взимане на най-големия индекс, за да добавяме само индекси, по-големи от него. Очевидно HashSet<T> вече не ни върши работа, но можем успешно да ползваме List<T>, в който елементите са наредени по големина и най-големият елемент по естествен начин е последен в списъка.

В крайна сметка нашия алгоритъм добива следната форма:

1.  Нека N е броят елементи в S. Започваме от опашка, съдържаща празния списък {}.

2.  Взимаме поредния елемент subset от опашката. Нека start е най-големия индекс в subset. Към subset добавяме всички индекси, които са по-големи от start и по-малки от N. В резултат получа­ваме няколко нови подмножества, които добавяме към опашката.

3.  Повтаряме последната стъпка докато опашката свърши.

Ето как изглежда реализацията на новия алгоритъм:

using System; using System.Collections.Generic;   public class Subsets {       static string[] words = { "море", "бира", "пари", "кеф" };         static void Main()       {             Queue<List<int>> subsetsQueue = new Queue<List<int>>();             List<int> emptySet = new List<int>();             subsetsQueue.Enqueue(emptySet);             while (subsetsQueue.Count > 0)             {                   List<int> subset = subsetsQueue.Dequeue();                   Print(subset);                   int start = -1;                   if (subset.Count > 0)                   {                         start = subset[subset.Count - 1];                   }                   for (int i = start + 1; i < words.Length; i++)                   {                         List<int> newSubset = new List<int>();                         newSubset.AddRange(subset);                         newSubset.Add(i);                         subsetsQueue.Enqueue(newSubset);                   }             }       }         static void Print(List<int> subset) {             Console.Write("[ ");             for (int i=0; i<subset.Count; i++) {                   int index = subset[i];                   Console.Write("{0} ", words[index]);             }             Console.WriteLine("]");       } }

Ако изпълним програмата, ще получим очаквания коректен резултат:

[ ] [ море ] [ бира ] [ пари ] [ кеф ] [ море бира ] [ море пари ] [ море кеф ] [ бира пари ] [ бира кеф ] [ пари кеф ] [ море бира пари ] [ море бира кеф ] [ море пари кеф ] [ бира пари кеф ] [ море бира пари кеф ]

Подреждане на студенти

Даден е текстов файл, съдържащ данните за група студенти и курсовете, които те изучават, разделени с |. Файлът изглежда по следния начин:

Кирил  | Иванов   | C# Милена | Стефанова | PHP Кирил | Иванов    | Java Петър  | Иванов   | C# Стефка | Василева  | Java Милена | Василева  | C# Милена | Стефанова | C#

Да се напише програма, която отпечатва всички курсове и за всеки от тях студентите, които са ги записали, подредени първо по фамилия, след това по име (ако фамилиите съвпадат).

Задачата можем да реализираме чрез хеш-таблица, която по име на курс пази списък от студенти. Избираме хеш-таблица, защото в нея можем бързо да търсим по име на курс.

За да изпълним условието за подредба по фамилия и име, при отпечатва­нето на студентите от всеки курс ще трябва да сортираме съответния списък. Другият вариант е да ползваме SortedSet<Т> за студентите от всеки курс (понеже той вътрешно е сортиран), но понеже може да има студенти с еднакви имена, трябва да ползваме SortedSet<List<String>>. Става твърде сложно. Избираме по-лесния вариант – да ползваме List<Student> и да го сортираме преди да го отпечатаме.

При всички случаи ще трябва да реализираме интерфейса IComparable, за да дефинираме наредбата на елементите от тип Student според условието на задачата. Необходимо е първо да сравняваме фамилията и при еднаква фамилия да сравняваме след това името. Напомняме, че за да сортираме елементите на даден клас в нарастващ ред, е необходимо изрично да дефинираме логиката на тяхната наредба. В .NET Framework това става чрез интерфейса IComparable<T>. Нека дефинираме класа Student и импле­ментираме IComparable<Student>. Получаваме нещо такова:

public class Student : IComparable<Student> {       private string firstName;       private string lastName;             public Student(string firstName, string lastName)       {             this.firstName = firstName;             this.lastName = lastName;       }         public int CompareTo(Student student)       {             int result = lastName.CompareTo(student.lastName);             if (result == 0)             {                   result = firstName.CompareTo(student.firstName);             }             return result;       }         public override String ToString()       {             return firstName + " " + lastName;       } }

Сега вече можем да напишем кода, който прочита студентите и техните курсове и ги записва в хеш-таблица, която по име на курс пази списък със студентите в този курс (Dictionary<string, ArrayList<Student>>). След това вече е лесно – итерираме по курсовете, сортираме студентите и ги отпечатваме:

// Read the file and build the hash-table of courses Dictionary<string, List<Student>> courses =       new Dictionary<string, List<Student>>(); StreamReader reader = new StreamReader("Students.txt",       Encoding.GetEncoding("windows-1251")); using (reader) {       while (true)       {             string line = reader.ReadLine();             if (line == null)             {                   break;             }             string[] entry = line.Split(new char[] { '|' });             string firstName = entry[0].Trim();             string lastName = entry[1].Trim();             string course = entry[2].Trim();             List<Student> students;             if (! courses.TryGetValue(course, out students))             {                   // New course -> create a list of students for it                   students = new List<Student>();                   courses.Add(course, students);             }             Student student = new Student(firstName, lastName);             students.Add(student);       } }   // Print the courses and their students foreach (string course in courses.Keys) {       Console.WriteLine("Course " + course + ":");       List<Student> students = courses[course];       students.Sort();       foreach (Student student in students)       {             Console.WriteLine("\t{0}", student);       } }

Примерният код чете студентите от файла Students.txt като изрично задава кодиране "windows-1251" за да се прочете правилно кирилицата. След това парсва редо­вете му последователно един по един като ги разделя по вертикална черта "|" и след това ги изчиства от интервали в началото и в края. След прочитането на всеки студент се проверява хеш-таблицата дали съдържа неговия курс. Ако курсът е наме­рен, студентът се добавя към списъка със студенти за този курс. Ако курсът не е намерен, се създава нов списък, към него се добавя студента и списъкът се записва в хеш-таблицата под ключ името на курса.

Отпечатването на курсовете и студентите не е сложно. От хеш-таблицата се извличат всички ключове. Това са имената на курсовете. За всеки курс се извлича списък от студентите му, те се сортират и се отпечатват. Сортирането става с вградения метод Sort(), като се използва  метода за сравнение CompareTo(…) от интерфейса IComparable<T> както е дефи­нирано в класа Student (сравнение първо по фамилия, а при еднакви фамилии – по име). Накрая сортираните студенти се отпечатват чрез предефинирания в тях виртуален метод ToString(). Ето как изглежда изходът от горната програма:

Course C#:         Милена Василева         Кирил Иванов         Петър Иванов         Милена Стефанова Course PHP:         Милена Стефанова Course Java:         Стефка Василева         Кирил Иванов

Подреждане на телефонен указател

Даден е текстов файл, който съдържа имена на хора, техните градове и телефони. Файлът изглежда по следния начин:

Киро | Варна   | 052 / 23 45 67 Пешо | София   | 02 / 234 56 78 Мими | Пловдив | 0888 / 22 33 44 Лили | София   | 0899 / 11 22 33 Дани | Варна   | 0897 / 44 55 66

Да се напише програма, която отпечатва всички градове по азбучен ред и за всеки от тях отпечатва всички имена на хора по азбучен ред и съответния им телефон.

Задачата можем да решим по много начини, например като сортираме по два критерия: на първо място по град и на второ място по телефон и след това отпечатаме телефонния указател.

Нека, обаче решим задачата без сортиране, като използваме стандартните структури от данни в .NET Framework. Искаме да имаме в сортиран вид градовете. Това означава, че е най-добре да ползваме структура, която държи вътрешно елементите си в сортиран вид. Такава е например балан­сираното дърво – SortedSet<Т> или SortedDictionary<K,T>. Понеже всеки запис от телефон­ния указател съдържа освен град и други данни, е по-удобно да имаме SortedDictionary<K,T>, който по ключ име на град пази списък от хора и техните телефони. Понеже искаме списъкът на хората за всеки град също да е сортиран по азбучен ред по имената на хората, можем отново да ползваме структурата SortedDictionary<K,T>. Като ключ можем да слагаме име на човек, а като стойност – неговия телефон. В крайна сметка получаваме структурата SortedDictionary<string, SortedDictionary<string, string>>. Следва примерна импле­мен­тация, която показва как можем да решим задачата с тази структура:

// Read the file and build the phone book SortedDictionary<string, SortedDictionary<string, string>>       phonesByTown = new SortedDictionary<string,             SortedDictionary<string, string>>(); StreamReader reader = new StreamReader("PhoneBook.txt",       Encoding.GetEncoding("windows-1251")); using (reader) {       while (true)       {             string line = reader.ReadLine();             if (line == null)             {                   break;             }             string[] entry = line.Split(new char[]{'|'});             string name = entry[0].Trim();             string town = entry[1].Trim();             string phone = entry[2].Trim();                         SortedDictionary<string, string> phoneBook;             if (! phonesByTown.TryGetValue(town, out phoneBook))             {                   // This town is new. Create a phone book for it                   phoneBook = new SortedDictionary<string, string>();                   phonesByTown.Add(town, phoneBook);             }             phoneBook.Add(name, phone);       } }   // Print the phone book by towns foreach (string town in phonesByTown.Keys) {       Console.WriteLine("Town " + town + ":");       SortedDictionary<string, string> phoneBook =             phonesByTown[town];       foreach (var entry in phoneBook)       {             string name = entry.Key;             string phone = entry.Value;             Console.WriteLine("\t{0} - {1}", name, phone);       } }

Ако изпълним този примерен код с вход примерния телефонен указател, ще получим очаквания резултат:

Town Варна:       Дани - 0897 / 44 55 66       Киро - 052 / 23 45 67 Town Пловдив:       Мими - 0888 / 22 33 44 Town София:       Лили - 0899 / 11 22 33       Пешо - 02 / 234 56 78

Търсене в телефонен указател

Ще даден още един пример, за да затвърдим начина, по който разсъжда­ваме, за да изберем подходящи структури от данни. Даден е телефонен указател, записан в текстов файл, който съдържа имена на хора, техните градове и телефони. Имената на хората могат да бъдат във формат малко име или прякор или име + фамилия или име + презиме + фамилия. Файлът би могъл да има следния вид:

Киро Киров        | Варна   | 052 / 23 45 67 Мундьо            | София   | 02 / 234 56 78 Киро Киров Иванов | Пловдив | 0888 / 22 33 44 Лили Иванова      | София   | 0899 / 11 22 33 Киро              | Плевен  | 064 / 88 77 66 Киро бирата       | Варна   | 0897 / 44 55 66 Киро              | Плевен  | 0897 / 44 55 66

Възможно е да има няколко души, записани под едно и също име, дори и от един и същ град. Възможно е някой да има няколко телефона и в такъв случай той се изписва няколко пъти във входния файл. Телефонният указател може да бъде доста голям (до 1 000 000 записа).

Даден е файл със заявки за търсене. Заявките са два вида:

-      Търсене по име / прякор / презиме / фамилия. Заявката има вида list(name).

-      Търсене по име / прякор / презиме / фамилия + град. Заявката има вида find(name, town).

Ето примерен файл със заявки:

list(Киро) find(Пешо, София) list(Лили) list(Киров) find(Иванов, Пловдив) list(Баба)

Да се напише програма, която по даден телефонен указател и файл със заявки да върне всички отговори на заявките за търсене. За всяка заявка да се изведе списък от записите в телефонния указател, които й съответ­стват или съобщението "Not found", ако заявката не намира нищо. Заяв­ките могат да са голям брой (например 50 000).

Тази задача не е толкова лесна, колкото предходните. Едно лесно за реализация решение е при всяка заявка да се сканира целият телефонен указател и да се изваждат всички записи, в които има съвпадения с търсената информация. Това, обаче ще работи бавно, защото записите могат да са много и заявките също могат да са много. Необходимо е да намерим начин да търсим бързо, без да сканираме всеки път целия телефонен указател.

В хартиените телефонни указатели телефоните са дадени по имената на хората, подредени в азбучен ред. Сортирането няма да ни помогне, защото някой може да търси по име, друг по фамилия, а трети – по прякор и име на град. Ние трябва да можем да търсим по всичко това едновре­менно. Въпросът е как да го направим?

Ако поразсъждаваме малко, ще се убедим, че в задачата се изисква търсене по всяка от думите, които се срещат в първата колона на теле­фонния указател и евентуално по комбинацията дума от първата колона и град от втората колона. Знаем, че най-бързото търсене, което познаваме, се реализира с хеш-таблица. Добре, но какво да използваме за ключ и какво да използваме за стойност в хеш-таблицата?

Дали пък да не ползваме няколко хеш-таблици: една за търсене по първата дума от първата колона, още една за търсене по втората колона, една за търсене по град и т.н. Ако се замислим още малко, ще си зададем въпроса – защо са ни няколко хеш-таблици? Не може ли да търсим само в една хеш-таблица. Ако имаме "Петър Иванов", в таблицата ще сложим под ключ "Петър" неговия телефон и същевременно под ключ "Иванов" същия телефон. Ако някой търси една от двете думи, ще намери телефона на Петър.

До тук добре, обаче как ще търсим по име и по град, например "Петър от Варна"? Възможно е първо да намерим всички с име "Петър" и от тях да отпечатаме само тези, които са от Варна. Това ще работи, но ако има достатъчно много хора с име Петър, търсенето по град ще работи бавно. Тогава защо не направим хеш-таблица по ключ име на човек и стойност друга хеш-таблица, която по град връща списък от телефони? Това би трябвало да работи. Нещо подобно правихме в предходната задача, нали?

Може ли да ни хрумне нещо още по-умно? Не може ли в основната хеш-таблица за телефонния указател да сложим под ключ "Петър от Варна" телефоните на всички, които се казват Петър и са от Варна? Изглежда това ще реши проблема и ще можем да използваме само една хеш-таблица за всички търсения.

Използвайки последната идея стигаме до следния алгоритъм: четем ред по ред теле­фонния указател и за всяка дума от името на човека d₁, d₂, ..., d_k и за всеки град t добавяме текущия запис от указателя под следните ключове: d₁, d₂, ..., d_k, "d₁ от t", "d₂ от t", …, "d_k от t". Така си гарантираме, че ще можем да търсим по всяко от имената на съответния човек и по всяка двойка име + град. За да можем да търсим без значение на регистъра (главни или малки букви), можем да направим предва­рително всички букви малки. След това търсенето е тривиално – просто търсим в хеш-таблицата подадената дума d или ако ни подадат дума d и град t, търсим по ключ "d от t". Понеже за един и същ ключ може да има много телефони, ползваме за стойност в хеш-таблицата списък от символни низове (List<string>). Нека разгледаме една имплементация на описания алгоритъм:

class PhoneBookFinder {       const string PhoneBookFileName = "PhoneBook.txt";       const string QueriesFileName = "Queries.txt";         static Dictionary<string, List<string>> phoneBook =             new Dictionary<string, List<string>>();         static void Main()       {             ReadPhoneBook();             ProcessQueries();       }         static void ReadPhoneBook()       {             StreamReader reader = new StreamReader(                   PhoneBookFileName, Encoding.GetEncoding("windows-1251"));             using (reader)             {                   while (true)                   {                         string line = reader.ReadLine();                         if (line == null)                         {                               break;                         }                         string[] entry = line.Split(new char[]{'|'});                         string names = entry[0].Trim();                         string town = entry[1].Trim();                           string[] nameTokens =                               names.Split(new char[] {' ', '\t'} );                         foreach (string name in nameTokens)                         {                               AddToPhoneBook(name, line);                               string nameAndTown = CombineNameAndTown(town, name);                               AddToPhoneBook(nameAndTown, line);                         }                   }             }       }         static string CombineNameAndTown(   string town, string name)       {             return name + " от " + town;       }         static void AddToPhoneBook(string name, string entry)       {             name = name.ToLower();             List<string> entries;             if (! phoneBook.TryGetValue(name, out entries))             {                   entries = new List<string>();                   phoneBook.Add(name, entries);             }             entries.Add(entry);                 }         static void ProcessQueries()       {             StreamReader reader = new StreamReader(QueriesFileName,                   Encoding.GetEncoding("windows-1251"));             using (reader)             {                   while (true)                   {                         string query = reader.ReadLine();                         if (query == null)                         {                               break;                         }                         ProcessQuery(query);                   }             }       }         static void ProcessQuery(string query)       {             if (query.StartsWith("list("))             {                   int listLen = "list(".Length;                   string name = query.Substring(                         listLen, query.Length-listLen-1);                   name = name.Trim().ToLower();                   PrintAllMatches(name);             }             else if (query.StartsWith("find("))             {                   string[] queryParams = query.Split(                         new char[] { '(', ' ', ',', ')' },                         StringSplitOptions.RemoveEmptyEntries);                   string name = queryParams[1];                   name = name.Trim().ToLower();                   string town = queryParams[2];                   town = town.Trim().ToLower();                   string nameAndTown =                         CombineNameAndTown(town, name);                   PrintAllMatches(nameAndTown);             }             else             {                   Console.WriteLine(                         query + " is invalid command!");             }       }         static void PrintAllMatches(string key)       {             List<string> allMatches;             if (phoneBook.TryGetValue(key, out allMatches))             {                   foreach (string entry in allMatches)                   {                         Console.WriteLine(entry);                   }             }             else             {                   Console.WriteLine("Not found!");             }             Console.WriteLine();       } }

При прочитането на телефонния указател чрез разделяне по вертикална черта "|" от него се извличат трите колони (име, град и телефон) от всеки негов ред. След това името се разделя на думи и всяка от думите се добавя в хеш-таблицата. Допълнително се добавя и всяка дума, комбини­рана с града (за да можем да търсим по двойката име + град).

Следва втората част на алгоритъма – изпълнението на командите. В нея файлът с коман­дите се чете ред по ред и всяка команда се обработва. Обработката включва парсване на командата, извличането на име или име и град от нея и търсене по даденото име или име, комбинирано с града. Търсенето се извършва директно в хеш-таблицата, която се създава при прочитане на телефонния указател.

За да се игнорират разликите между малки и главни букви, всички ключове в хеш-таблицата се добавят с малки букви и при търсенето ключовете се търсят също с малки букви.

Избор на структури от данни – изводи

От множеството примери става ясно, че изборът на подходяща структура от данни силно зависи от конкретната задача. Понякога се налага струк­турите от данни да се комбинират или да се използват едновременно няколко структури.

Кога каква структура да подберем зависи най-вече от операциите, които извършваме, така че винаги си задавайте въпроса "какви операции трябва да изпълнява ефективно структурата, която ми трябва". Ако знаете операциите, лесно може да съобразите коя структура ги изпълнява най-ефективно и същевременно е лесна и удобна за ползване.

За да изберете ефективно структура от данни, трябва първо да измислите алгоритъма, който ще имплементирате и след това да потърсите подходя­щите структури за него.

Тръгвайте винаги от алгоритъма към структурите от данни, а не обратното.

Външни библиотеки с .NET колекции

Добре известен факт е, че библиотеката със стандартни структури от данни в .NET Framework System.Collections.Generic е доста бедна откъм функционалност. В нея липсват имплементации на основни концепции в структурите данни, мултимножества и приоритетни опашки, за които би трябвало да има както стандартни класове, така и базови системни интерфейси.

Когато ни се наложи да използваме струк­тура от данни, която стандартно не е импле­ментирана в .NET Framework имаме два варианта:

• Първи вариант: имплементираме си сами структурата от данни. Това дава гъвкавост, тъй като импле­ментацията ще е съобразена напълно с нашите нужди, но отнема много време и има голяма вероятност от допускане на грешки. Например, ако трябва да се имплементира по кадърен начин балансирано дърво, това може да отнеме на добър програмист няколко дни (заедно с тестовете). Ако се имплементира от неопитен програмист ще отнеме още повече време и има огромна вероятност в имплементацията да има грешки.
• Вторият вариант (като цяло за предпочитане): да си намерим външна библиотека, в която е реализирана на готово нужната ни функционалност. Този подход има предимството, че ни спестява време и проблеми, тъй като готовите библиотеки със структури от данни в повечето случаи са добре тествани. Те са използвани години наред от хиляди разработчици и това ги прави зрели и надеждни.

Power Collections for .NET

Една от най-популярните и най-пълни библиотеки с ефективни реали­зации на фундаментални структури от данни за C# и .NET разработчици е проектът с отворен код "Wintellect's Power Collections for .NET" – http://powercollections.codeplex.com/. Той предоставя свободна, надеждна, ефективна, бърза и удобна имплементация на следните често използвани структури от данни, които липсват или са непълно имплементирани в .NET Framework:

• Set<T> – множество от елементи, имплементирано чрез хеш-таблица. Реализира по ефективен начин основните операции над множества: добавяне на елемент, изтриване на елемент, търсене на елемент, обединение, сечение и разлика на множества и други. По функционалност и начин на работа класът прилича на стандартния клас HashSet<T> в .NET Framework.
• Bag<T> – мултимножество от елементи (множество с повторения), имплементирано чрез хеш-таблица. Реализира ефективно всички основни операции с мултимножества.
• OrderedSet<T> – подредено множество от елементи (без повто­рения), имплементи­рано чрез балансирано дърво. Реализира ефек­тивно всички основни операции с множества и при обхождане връща еле­ментите си в нарастващ ред (според използвания компаратор). Поз­волява бързо извличане на подмножества от стойностите в даден интервал от стойности.
• OrderedBag<T> – подредено мултимножество от елементи, импле­ментирано чрез балансирано дърво. Реализира ефективно всички основни операции с мултимножества и при обхождане връща еле­ментите си в нарастващ ред (според използвания компаратор). Поз­волява бързо извличане на подмножества от стойностите в даден интервал от стойности.
• MultiDictionary<K,T> – представлява хеш-таблица, позволяваща повторения на ключовете. За един ключ се пази съвкупност от стойности, а не една единична стойност.
• OrderedDictionary<K,T> – представлява речник, реализиран с балансирано дърво. Позволява бързо търсене по ключ и при обхож­дане на елементите ги връща сортирани в нарастващ ред. Позво­лява бързо извличане на елементите в даден диапазон от ключове. По функционалност и начин на работа класът прилича на стан­дартния клас SortedDictionary<K,T> в .NET Framework.
• Deque<Т> – представлява ефективна реализация на опашка с два края (double ended queue), която на практика комбинира струк­турите стек и опашка. Позволява ефективно добавяне, извличане и изтриване на елементи в двата края.
• BagList<T> – списък от елементи, достъпни по индекс, който позволява бързо вмъкване и изтриване на елемент от определена позиция. Операциите достъп по индекс, добавяне, вмъкване на позиция и изтриване от позиция имат сложност O(log N). Реализа­цията е с балансирано дърво. Структу­рата е добра алтернатива на List<T>, при която вмъкването и изтриването от определена позиция отнема линейно време поради нуждата от преместване на линеен брой елементи наляво или надясно.

Оставяме на читателя възможността да си изтегли библиотеката "Power Collections for .NET" от нейния сайт и да експериментира с нея. Тя може да е много полезна при решаването на някои задачи от упражненията.

Упражнения

1.  Хеш-таблиците не позволяват в един ключ да съхраняваме повече от една стойност. Как може да се заобиколи това ограничение?

2.  Реализирайте структура от данни, която изпълнява бързо следните две операции: добавяне на елемент и извличане на най-малкия елемент. Структурата трябва да позволява включването на повтарящи се еле­менти.

3.  Текстов файл students.txt съдържа информация за студенти и техните специалност в следния формат:

Spas Delev | Computer Sciences Ivan Ivanov | Software Engeneering Gergana Mineva | Public Relations Nikolay Kostov | Computer Sciences Stanimira Georgieva | Public Relations Vasil Ivanov | Software Engeneering

Като използвате SortedDictionary<K,T> изведете на конзолата в азбучен ред специалностите и за всеки от тях изведете имената на студентите, сортирани първо по фамилия, после по първо име, както е показано:

Computer Sciences: Spas Delev, Nikolay Kostov Public Relations: Stanimira Georgieva, Gergana Mineva Software Engeneering: Ivan Ivanov, Vasil Ivanov

4.  Имплементирайте клас BiDictionary<K1,K2,T>, който позволява добавяне на тройки {key1, key2, value} и бързо търсене по ключовете key1, key2 и търсене по двата ключа. Заб.: Разрешено е добавянето на много елементи с един и същ ключ.

5.  В една голяма верига супермаркети се продават милиони стоки. Всяка от тях има уникален номер (баркод), производител, наименование и цена. Каква структура от данни можем да използваме, за да можем бързо да намерим всички стоки, които струват между 5 и 10 лева?

6.  Голяма компания за продажби притежава милиони статии, всяка от които има баркод, производител, заглавие и цена. Имплементирайте структура от данни, която позволява бързи заявки за статии по цена на статията в определен интервал [x…y].

7.  Разписанието на дадена конгресна зала представлява списък от събития във формат [начална дата и час; крайна дата и час; наименование на събитието]. Какви структури от данни можем да ползваме, за да можем бързо да проверим дали залата е свободна в даден интервал [начална дата и час; крайна дата и час]?

8.  Имплементирайте структурата от данни PriorityQueue<T>, която предоставя бърз достъп за изпълнение на следните операции: добавяне на елемент, изкарване на най-малкия елемент.

9.  Представете си, че разработвате търсачка в обявите за продажба на коли на старо, която обикаля десетина сайта за обяви и събира от тях всички обяви за последните няколко години. След това търсачката позволява бързо търсене по един или няколко критерии: марка, модел, цвят, година на производство и цена. Нямате право да ползвате система за управление на бази от данни и трябва да реализирате собствено индексиране на обявите в паметта, без да пишете на твър­дия диск и без да използвате LINQ. При търсене по цена се подава минимална и максимална цена. При търсене по година на производство се задава начална и крайна година. Какви структури от данни ще ползвате, за да осигурите бързо търсене по един или няколко критерия?

Решения и упътвания

1.  Можете да използвате Dictionary<key, List<value>> или да си създадете собствен клас MyCollection, който да се грижи за стойностите с еднакъв ключ и да използвате Dictionary<key, MyCollection>.

2.  Можете да използвате SortedSet<List<int>> и неговите операции Add() и First(). Задачата има и по-ефективно решение – структурата от данни "двоична пирамида" (binary heap). Можете да прочетете за нея от Уикипедия: http://en.wikipedia.org/wiki/Binary_heap.

3.  Задачата е много подобна на тази от секцията "Подреждане на студенти".

4.  Едно от решенията на тази задача е да използвате две инстанции на класа Dictionary по една за всеки от двата ключа и когато добавяте или махате елемент от BiDictionary, съответно да го добавяте или махате и в двете хеш-таблици. Когато търсите по първия или по втория ключ, ще гледате за елементи съответно в първата или втората хеш-таблица, а когато търсите за елемент по двата ключа, ще гледате в двете хеш-таблици и ще връщате само елементите, които се намират и в двете намерени множества.

5.  Ако държим стоките в сортиран по цена масив (например в структура List<Product>, който първо запълваме и накрая сортираме), за да намерим всички стоки, които струват между 5 и 10 лева можем два пъти да използваме двоично търсене. Първо можем да намерим най-малкия индекс start, на който стои стока струваща най-малко 5 лева. След това можем да намерим най-големия индекс end, на който стои стока струваща най-много 10 лева. Всички стоки на позиции в интервала [start … end] струват между 5 и 10 лв. За двоично търсене в сортиран масив можете да прочетете в Уикипедия: http://en.wikipedia. org/wiki/Binary_search.

Като цяло подходът с използването на сортиран масив и двоично търсене в него работи отлично, но има един недостатък: в сортиран масив добавянето на нов елемент е много бавна операция, тъй като изисква преместване на линеен брой елементи с една позиция напред спрямо вмъкнатия нов елемент. Класовете SortedDictionary<T,K> и SortedSet<T> съответно позволяват бързо вмъкване, запазващо елемен­тите в сортиран вид, но не позволява достъп по индекс, двоично търсене и съответно извличане на всички елементи, които са по-големи или по-малки от даден ключ. Това е ограничение на имплементацията на тези структури в .NET Framework. В класическите имплементации на балансирано дърво има стандартна операция за бързо извличане на поддърво с елементите в даден интервал от два ключа. Това е реализи­рано например в класа OrderedSet<T> от библиотеката "Wintellect's Power Collections for .NET" (http://www.codeplex.com/PowerCollections).

6.  Използвайте структурата от данни OrderedMultiDictionary от Wintellect's Power Collections.

7.  Можем да конструираме два сортирани масива (List<Event>): единият да пази събитията сортирани в нарастващ ред по ключ началната дата и час, а другият да пази същите събития сортирани по ключ крайна дата и час. Можем да намерим чрез двоично търсене всички събития, които се съдържат частично или изцяло между два момента от времето [start, end] по следния начин:

-     Намираме всички събития, завършващи след момента start (чрез двоично търсене).

-     Намираме всички събития, започващи преди момента end (чрез двоично търсене).

-     Ако двете множества от събития имат общи елементи, то в търсения интервал от време [start, end] залата е заета. В противен случай залата е свободна.

Друго решение, което е по-лесно и по-ефективно, е чрез две инстанции на класа OrderedBag<T> от библиотеката "Power Collections for .NET", който има метод за извличане на всички елементи в даден интервал.

8.  Тъй като в .NET няма вградена имплементация на структурата от данни приоритетна опашка, можете да използвате структурата OrderedBag<T> от Wintellect's Power Collections. За приоритетната опашка (Priority Queue) можете да прочетете повече в Уикипедия: http://en.wikipedia.org/wiki/Priority_Queue.

9.  За търсенето по марка, модел и цвят можем да използваме по една хеш-таблица, която търси по даден критерий и връща списък от коли (Dictionary<string, List<Car>>).

За търсенето по година на производство и по ценови диапазон можем да използваме списъци List<Car>, сортирани в нарастващ ред съо­тветно по година на производство и по цена.

Ако търсим по няколко критерия едновременно, можем да извлечем множествата коли по първия критерии, след това множествата коли по втория критерий и т.н. Накрая можем да намерим сечението на множе­ствата. Сечение на две множества се намира, като всеки елемент на по-малкото множество се търси в по-голямото множество. Най-лесно е да се дефинират Equals() и GetHashCode() за класа Car и след това за сечение на множества да се ползва класа HashSet<Car>.

Дискусионен форум

Коментирайте книгата и задачите в нея във: форума на софтуерната академия.