Free C# / Java / JavaScript / Python / C++ Programming Books » Глава 19. Структури от данни

Автори

Светлин Наков

Николай Недялков

В тази тема...

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

Съдържание

Видео

Презентация

19. Java data structures algorithms and complexity from Intro C# Book

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

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

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

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

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

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

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

Сложност на алгоритъм е метрика, която отразява порядъка на броя операции, необходими за изпълнение на дадена операция или алгоритъм като функция на обема на входните данни. Формулирано още по-просто, сложност е груба, приблизителна оценка на броя стъпки за изпълнение на даден алгоритъм. Означава се най-често с нотацията О(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/2 или 3*N за N елемента.
	O(n*log(n))	За извършване на дадена операция върху N елемента са необходими приблизително N*log(N) стъпки. Примерно при 1 000 елемента са нужни около 10 000 стъпки.
квадратична	O(n²)	За извършване на дадена операция са необходими N² на брой стъпки, където N характеризира обема на входните данни. Примерно за дадена операция върху 100 елемента са необходими 10 000 стъпки. Ако броят стъпки е в квадратна зависимост спрямо обема на входните данни, то сложността е квадратична.
кубична	O(n³)	За извърхване на дадена операция са необходими от порадъка на N³ стъпки, където N характеризира обема на входните данни. Примерно при 100 елемента се изпълняват около 1 000 000 стъпки.
експоненциална	O(2ⁿ), O(N!), O(n^k), …	За извърпване на дадена операция или изчисление са необходими брой стъпки, който е в експоненциалназависимост спрямо размера на входните данни. Например при N=10 експоненциалната функция 2^N има стойност 1024, при N=20 има стойност 1 048 576, а при N=100 функцията има стойност, която е число с около 30 цифри.

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

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

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

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

алгоритъм	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(n²)	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	2 сек.	3-4 мин.
O(n³)	< 1 сек.	< 1 сек.	< 1 сек.	< 1 сек.	20 сек.	5.55 часа	231.5 дни
O(2ⁿ)	< 1 сек.	< 1 сек.	260 дни	заспива	заспива	заспива	заспива
O(n!)	< 1 сек.	заспива	заспива	заспива	заспива	заспива	заспива
O(nⁿ)	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 (бързо сортиране), който в средния случай работи малко по-добре от MergeSort (сортиране чрез сливане), но в най-лошия случай QuickSort прави от порядъка на n² стъпки.

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

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

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

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

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

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

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

Понякога е трудно да оценим точно сложността на даден алгоритъм, тъй като изпълняваме операции, за които не знаем колко бързо се изпълняват. Да вземем за пример търсенето на дадена дума в масив от текстове. Трябва да обходим масива и във всеки от текстовете да търсим със substring() или с регулярен израз дадената дума. Ако имаме 10 000 текста, това бързо ли ще работи? Не може да се каже, защото трябва да знаем колко са обемни текстовете. Можем да оценим сложността на най-малко O(L), където L е сумата от дължините на всички текстове. При някои специални ситуации, обаче търсенето зависи съществено и от дължината на търсената дума и тази оценка може да се окаже силно занижена.

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

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

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

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

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

int findMaxElement(int[] array) {

int max = array[0];

for (int i=0; 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; 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 = 0; a < n; a++)

for (int b = 0; b < n; b++)

for (int c = 0; 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 = 0; x < n; x++)

for (int y = 0; 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 = 0; x < n; x++)

for (int y = 0; y < m; y++)

if (x == y)

for (int i = 0; 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ⁿ, т.е. имаме експоненциална сложност.

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

public static long fibonacci(int n) {

long fn = 1;

long fn_1 = 1;

long fn_2 = 1;

for (int i = 2; i < n; i++) {

fn = fn_1 + fn_2;

fn_2 = fn_1;

fn_1 = fn;

}

return fn;

}

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

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

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

структура	добавяне	търсене	изтриване	достъп по индекс
Array	O(N)	O(N)	O(N)	О(1)
LinkedList	О(1)	O(N)	O(N)	O(N)
ArrayList	О(1)	O(N)	O(N)	O(1)
Stack	О(1)	-	О(1)	-
Queue	О(1)	-	О(1)	-
HashMap	О(1)	О(1)	О(1)	-
TreeMap	О(log(N))	О(log(N))	О(log(N))	-
HashSet	О(1)	О(1)	О(1)	-
TreeSet	О(log(N))	О(log(N))	О(log(N))	-

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

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

Масив (Array)

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

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

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

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

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

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

Свързан списък в практиката се използва много рядко, защото динамичният масив (ArrayList) изпълнява почти всички операции, които могат да бъдат изпълнени с LinkedList, но за повечето от тях работи по-бързо.

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

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

Динамичен масив (ArrayList)

Динамичният масив (ArrayList) е една от най-използваните в практиката структура от данни. Той няма фиксиран размер, както масивите и има директен достъп по индекс, за разлика от свързания списък.

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

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

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

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

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

Стек (Stack)

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

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

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

Опашка (Queue)

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

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

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

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

Речник, реализиран с хеш-таблица (HashMap)

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

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

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

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

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

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

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

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

Речник, реализиран с дърво (TreeMap)

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

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

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

TreeMap държи вътрешно елементите си в червено-черно дърво, подредени по ключа. Това означава, че ако обходим структурата (чрез нейния итератор), ще получим елементите сортирани в нарастващ ред по ключа им. Понякога това може да е много полезно.

Използвайте TreeMap в случаите, в които ви трябва структура, в която бързо да добавяте, бързо да търсите и имате нужда от извличане на елементите, сортирани в нарастващ ред. В общия случай HashMap работи малко по-бързо от TreeMap и е за предпочитане.

Като пример за използване на TreeMap можем да дадем следната задача: Да се намерят всички думи в текстов файл, които се срещат точно 10 пъти и да се отпечатат по азбучен ред. Това е задача, която можете да решите също така успешно и с HashMap, но ще ви се наложи да направите едно сортиране повече.

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

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

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

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

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

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

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

Множество, реализирано с дърво (TreeSet)

Множество, реализирано чрез червено-черно дърво (класът TreeSet), е частен случай на TreeMap, в който ключовете и стойностите съвпадат.

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

Като пример за използването на TreeSet можем да посочим задачата за намиране на всички различни думи в даден текстов файл и отпечатването им по азбучен ред.

Ползвайте TreeSet, когато трябва бързо да добавяте елементи към множество и да проверявате дали даден елемент е от множеството и освен това елементите ще ви трябват сортирани в нарастващ ред.

Други структури в Java платформата

Ако разгледаме стандартните библиотеки на Java платформата, ще се убедим, че освен разгледаните до момента колекции (имплементации на List, Map и Set), тя ни предоставя и много техни варианти със специално предназначение. Такива са например неизменимите (read only) колекции (Collections.UnmodifiableCollection) и синхронизираните колекции, които позволяват конкурентен достъп от няколко нишки (Collections. SynchronizedCollection, Vector, Hashtable, ConcurrentHashMap) и др. Те се ползват в много специфични ситуации, така е малко вероятно да имате нужда от тях.

Измежду структурите от стандартната библиотека на Java, които не сме споменавали до момента полезни могат да ви бъдат PriorityQueue и LinkedHashSet.

Приоритетна опашка (PriorityQueue)

Абстрактната структура от данни "приоритетната опашка" прилича на опашка, но елементите, които попадат в нея постъпват с даден приоритет. Елементите напускат опашката по ред, определен от приоритета им. Елементите с по-висок приоритет напускат опашката по рано, отколкото елементите с по-нисък приоритет. Елементите с еднакъв приоритет напускат опашката в неопределен ред.

Класът PriorityQueue имплементира ефективно приоритетна опашка чрез дървовидна структура, наречена двоична пирамида (binary heap). Тази имплементация гарантира добавяне и премахване на елементи със сложност O(log(N)) и начално построяване на структурата пирамида от неподреден списък с линейна сложност. За разлика от класа TreeSet в PriorityQueue можем да имаме повтарящи се елементи.

Ще демонстрираме как можем да използваме класа PriorityQueue с един пример:

import java.util.PriorityQueue;

public class PriorityQueueExample {

static class Person implements Comparable<Person> {

String name;

int priority;

public Person(String name, int priority) {

this.name = name;

this.priority = priority;

}

@Override

public int compareTo(Person p) {

if (this.priority > p.priority) {

return 1;

} else if (this.priority < p.priority) {

return -1;

} else {

return 0;

}

@Override

public String toString() {

return "[" + name + " : " + priority + "]";

}

public static void main(String[] args) {

PriorityQueue<Person> queue = new PriorityQueue<Person>();

queue.add(new Person("Maria", 8));

queue.add(new Person("Peter", 5));

queue.add(new Person("George", 3));

while (! queue.isEmpty()) {

System.out.println(queue.poll());

}

// Output is sorted according to the priority:

// [George : 3]

// [Peter : 5]

// [Maria : 8]

}

В примера създаваме клас Person, който дефинира име и приоритет. Имплементираме интерфейса Comparable, за да дефинираме наредба по полето priority. Предефинираме toString() метода, за да можем свободно да отпечатваме Person обекти в конзолата. След това създаваме приоритетна опашка и добавяме в нея три обекта от тип Person в случаен ред. След това ги изваждаме и отпечатваме. От резултата се убеждаваме, че приоритетната опашка изважда елементите по реда, дефиниран от приоритета им.

Множество, запазващо наредбата (LinkedHashSet)

Класът LinkedHashSet представлява множество, имплементирано с хеш-таблица, което запазва реда на постъпване на елементите. LinkedHashSet е комбинация между HashSet и двусвързан списък. При обхождане елементите се обработват по реда им на постъпване, който се запазва в допълнителен списък. Класът е удобен, когато искаме да работим с множество с голяма бързина (HashSet), но не искаме да губим реда на постъпване на елементите.

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

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

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

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

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

{}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

String[] words = {"море", "бира", "пари", "кеф"};

Queue<Set<String>> subsetsQueue = new LinkedList<Set<String>>();

Set<String> emptySet = new HashSet<String>();

subsetsQueue.offer(emptySet);

while (! subsetsQueue.isEmpty()) {

Set<String> subset = subsetsQueue.poll();

System.out.println(subset);

for (String element : words) {

if (! subset.contains(element)) {

Set<String> newSubset = new HashSet<String>();

newSubset.addAll(subset);

newSubset.add(element);

subsetsQueue.offer(newSubset);

}

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

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

море à 0

бира à 1

пари à 2

кеф à 3

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

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

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

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

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

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

import java.util.*;

public class Subsets {

private static String[] words =

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

public static void main(String[] args) {

Queue<ArrayList<Integer>> subsetsQueue =

new LinkedList<ArrayList<Integer>>();

ArrayList<Integer> emptySet = new ArrayList<Integer>();

subsetsQueue.offer(emptySet);

while (! subsetsQueue.isEmpty()) {

ArrayList<Integer> subset = subsetsQueue.poll();

print(subset);

int start = -1;

if (subset.size() > 0) {

start = subset.get(subset.size()-1);

}

for (int index = start+1; index < words.length; index++){

ArrayList<Integer> newSubset =

new ArrayList<Integer>();

newSubset.addAll(subset);

newSubset.add(index);

subsetsQueue.offer(newSubset);

}

private static void print(ArrayList<Integer> subset) {

System.out.print("[ ");

for (int i=0; i<subset.size(); i++) {

int index = subset.get(i);

System.out.print(words[index] + " ");

}

System.out.println("]");

}

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

[ ]

[ море ]

[ бира ]

[ пари ]

[ кеф ]

[ море бира ]

[ море пари ]

[ море кеф ]

[ бира пари ]

[ бира кеф ]

[ пари кеф ]

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

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

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

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

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

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

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

Кирил | Иванов | Java

Милена | Стефанова | PHP

Благой | Иванов | Java

Петър | Иванов | Linux

Стефка | Василева | C++

Милена | Василева | Java

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

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

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

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

public class Student implements Comparable<Student> {

private String firstName;

private String lastName;

public Student(String firstName, String lastName) {

this.firstName = firstName;

this.lastName = lastName;

}

public String getName() {

return this.firstName + " " + this.lastName;

}

public int compareTo(Student student) {

int result = this.lastName.compareTo(student.lastName);

if (result == 0) {

result = this.firstName.compareTo(student.firstName);

}

return result;

}

@Override

public String toString() {

return firstName + " " + lastName;

}

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

// Read the file and build the hash-table of courses

HashMap<String, ArrayList<Student>> courses =

new HashMap<String, ArrayList<Student>>();

Scanner input =

new Scanner(new File("Students.txt"), "windows-1251");

try {

while (input.hasNext()) {

String line = input.nextLine();

String[] studentEntry = line.split("\\s*\\|\\s*");

String firstName = studentEntry[0];

String lastName = studentEntry[1];

String course = studentEntry[2];

ArrayList<Student> students = courses.get(course);

if (students == null) {

// New course -> create a list of students for it

students = new ArrayList<Student>();

courses.put(course, students);

}

Student student = new Student(firstName, lastName);

students.add(student);

}

} finally {

input.close();

}

// Print the courses and their students

Set<String> coursesNames = courses.keySet();

for (String course : coursesNames) {

System.out.println("Course " + course + ":");

ArrayList<Student> students = courses.get(course);

Student[] studentsArr =

students.toArray(new Student[students.size()]);

Arrays.sort(studentsArr);

for (Student student : studentsArr) {

System.out.printf("\t%s\n", student);

}

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

Отпечатването на курсовете и студентите е просто. От хеш-таблицата се извличат всички ключове. Това са имената на курсовете. За всеки курс се извлича списък от студентите му. Списъкът се превръща в масив, за да може да се сортира с Arrays.sort(). Сортирането се извършва, както е дефинирано в компаратора на класа Student – първо по фамилия, а при еднакви фамилии – по име. Накрая сортираните студенти се отпечатват чрез предефинирания в тях виртуален метод toString(). Ето как изглежда изходът от горната програма:

Course Linux:

Петър Иванов

Course PHP:

Милена Стефанова

Course C++:

Стефка Василева

Course Java:

Милена Василева

Благой Иванов

Кирил Иванов

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

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

Киро | Варна | 052 / 23 45 67

Пешо | София | 02 / 234 56 78

Мими | Пловдив | 0888 / 22 33 44

Лили | София | 0899 / 11 22 33

Дани | Варна | 0897 / 44 55 66

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

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

Нека, обаче решим задачата без сортиране, като използваме стандартните структури от данни в Java. Искаме да имаме в сортиран вид градовете. Това означава, че трябва да ползваме структура, която държи елементите си в сортиран вид. Такава е балансираното дърво – TreeSet или TreeMap. Понеже всеки запис от телефонния указател съдържа освен град и други данни, е по-удобно да имаме TreeMap, който по ключ име на град пази списък от хора и техните телефони. Понеже искаме списъкът на хората за всеки град да е сортиран по имената на хората, можем отново да ползваме TreeMap. Като ключ можем да държим име на човек, а като стойност – неговият телефон. В крайна сметка получаваме структурата TreeMap<String, TreeMap<String, String>>. Следва примерна имплементация, която показва как можем да решим задачата с тази структура:

// Read the file and build the phone book

TreeMap<String, TreeMap<String, String>> phonesByTown =

new TreeMap<String, TreeMap<String, String>>();

Scanner input = new Scanner(

new File("PhoneBook.txt"), "windows-1251");

try {

while (input.hasNext()) {

String line = input.nextLine();

String[] phoneBookEntry = line.split("\\s*\\|\\s*");

String name = phoneBookEntry[0];

String town = phoneBookEntry[1];

String phone = phoneBookEntry[2];

TreeMap<String, String> phoneBook = phonesByTown.get(town);

if (phoneBook == null) {

// This town is new. Create a phone book for it

phoneBook = new TreeMap<String, String>();

phonesByTown.put(town, phoneBook);

}

phoneBook.put(name, phone);

}

} finally {

input.close();

}

// Print the phone book by towns

Set<String> towns = phonesByTown.keySet();

for (String town : towns) {

System.out.println("Town " + town + ":");

TreeMap<String, String> phoneBook = phonesByTown.get(town);

for (Map.Entry<String, String> entry : phoneBook.entrySet()) {

String name = entry.getKey();

String phone = entry.getValue();

System.out.printf("\t%s - %s\n", 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 и град t, търсим по ключ "d от t". Понеже за един и същ ключ може да има много телефони, ползваме за стойност списък от символни низове (ArrayList<String>). Нека разгледаме една имплементация на описания алгоритъм:

import java.io.*;

import java.util.*;

public class PhoneBookFinder {

private static final String PHONE_BOOK_FILE = "PhoneBook.txt";

private static final String QUEIRES_FILE = "Queries.txt";

public static void main(String[] args) throws IOException {

HashMap<String, ArrayList<String>> phoneBook =

readPhoneBook(PHONE_BOOK_FILE);

processQueries(QUEIRES_FILE, phoneBook);

}

private static HashMap<String, ArrayList<String>>

readPhoneBook(String fileName) throws FileNotFoundException {

HashMap<String, ArrayList<String>> phoneBook =

new HashMap<String, ArrayList<String>>();

Scanner input =

new Scanner(new File(fileName), "windows-1251");

try {

while (input.hasNext()) {

String entry = input.nextLine();

String[] phoneBookEntry =

entry.split("\\s*\\|\\s*");

String names = phoneBookEntry[0];

String town = phoneBookEntry[1];

String[] nameTokens = names.split("\\s+");

for (String name : nameTokens) {

addToPhoneBook(phoneBook, name, entry);

String nameAndTown =

combineNameAndTown(town, name);

addToPhoneBook(phoneBook, nameAndTown, entry);

}

} finally {

input.close();

}

return phoneBook;

}

private static String combineNameAndTown(

String town, String name) {

return name + " от " + town;

}

private static void addToPhoneBook(

HashMap<String, ArrayList<String>> phoneBook,

String name, String entry) {

name = name.toLowerCase();

ArrayList<String> entries = phoneBook.get(name);

if (entries == null) {

entries = new ArrayList<String>();

phoneBook.put(name, entries);

}

entries.add(entry);

}

private static void processQueries(String fileName,

HashMap<String, ArrayList<String>> phoneBook)

throws IOException {

Scanner input =

new Scanner(new File(fileName), "windows-1251");

try {

while (input.hasNext()) {

String query = input.nextLine();

processQuery(phoneBook, query);

}

} finally {

input.close();

}

private static void processQuery(HashMap<String,

ArrayList<String>> phoneBook, String query) {

if (query.startsWith("list(")) {

String name = query.substring(

"list(".length(), query.length()-1);

name = name.trim().toLowerCase();

printAllMatches(name, phoneBook);

} else if (query.startsWith("find(")) {

int commaIndex = query.indexOf(',');

String name = query.substring(

"find(".length(), commaIndex);

name = name.trim().toLowerCase();

String town = query.substring(

commaIndex+1, query.length()-1);

town = town.trim().toLowerCase();

String nameAndTown = combineNameAndTown(town, name);

printAllMatches(nameAndTown, phoneBook);

} else {

System.out.println(query + " is invalid command!");

}

private static void printAllMatches(String key,

HashMap<String, ArrayList<String>> phoneBook) {

List<String> allMatches = phoneBook.get(key);

if (allMatches != null) {

for (String entry : allMatches) {

System.out.println(entry);

}

} else {

System.out.println("Not found!");

}

System.out.println();

}

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

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

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

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

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

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

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

Упражнения

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

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

3. Реализирайте структура от данни, която съхранява тройки елементи от вида (key1, key2, value) и позволява да търсим бързо по кой да е измежду двата ключа.

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

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

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

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

1. Можем да използваме HashMap<key, List<value>>.

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

3. Използвайте комбинация от две хеш-таблици.

4. Ако държим стоките в TreeMap, където за ключ се използва цената, можем да използваме метода subMap(5.0, 10.001), за да намерим всички стоки, които струват между 5 и 10 лева. Странното е, че при този метод долната граница се задава включително, а горната – изключително.

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

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

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

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

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

За търсенето по година на производство и по ценови диапазон можем да използваме TreeMap<String, HashSet<Car>>. Тази структура ще ни позволи по даден диапазон да намерим съвкупност от множества коли, които влизат в него. Ако обединим множествата, ще получим всички коли в даден диапазон (ценови диапазон или диапазон за годината на производство).

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

За класа Car ще трябва да дефинираме методите equals() и hashCode(), за да можем да го ползваме като елемент на множество HashSet. Можем да използваме средствата на Eclipse за автоматично генериране на тези методи.

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

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

Коментирай

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

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

Автори

В тази тема...

Съдържание

Видео

Презентация

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

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

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

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

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

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

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

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

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

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

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

Масив (Array)

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

Динамичен масив (ArrayList)

Стек (Stack)

Опашка (Queue)

Речник, реализиран с хеш-таблица (HashMap)

Речник, реализиран с дърво (TreeMap)

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

Множество, реализирано с дърво (TreeSet)

Други структури в Java платформата

Приоритетна опашка (PriorityQueue)

Множество, запазващо наредбата (LinkedHashSet)

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

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

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

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

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

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

Упражнения

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

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

Коментирай