Съвети за използване на колекции

1. Списък на колекциите

Както може би си спомняте, Java има колекции — удобен инструмент за съхраняване на обекти от същия тип.

Нека се опитаме да си припомним основните интерфейси, свързани с колекцията:

Списък , набор , карта и опашка .

Както обикновено, инструментите не са непременно добри or лоши - важното е дали ги използвате по преднаmeaning. И за да направим това, трябва да разберем подробно техните специфични характеристики, за да знаем коя колекция да използваме и кога.

1. Списък

Да започнем с най-използваната колекция.

Списък възможно най-близо до обикновен стар масив.

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

2. Комплект

Комплектът има съвсем различна структура.

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

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

3. Карта

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

За Map тези отношения се наричат ​​двойки ключ-стойност.

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

4. Опашка

Queue е колекция, която — изненада! — прилага поведението на опашка. И опашката може да бъде LIFO (последен влязъл, първи излязъл) or FIFO (първи влязъл, първи излязъл). Нещо повече, опашката може да бъде двупосочна or "двустранна".

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

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

Както виждаме, всяка от тези структури е добра, ако се използва по преднаmeaning. И намерихме добри applications за всичките четири типа колекции в един пример за библиотека.

2. Сложност

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

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

Когато избираме правилния инструмент за дадена работа, ние обикновено разглеждаме 2 характеристики:

• Колко добре пасва инструментът на работата?
• Колко бързо ще свърши работата?

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

В изчисленията скоростта на даден инструмент често се изразява като времева сложност и се обозначава с главна буква O.

Какво, по дяволите, е сложността на времето?

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

ArrayList срещу LinkedList

Нека да разгледаме това с помощта на две реализации на интерфейса List — ArrayList и LinkedList .

За външен вид работата с тези колекции е подобна:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

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

Поради различните им реализации на интерфейса List , тези две структури изпълняват различни действия по-ефективно от други.

Помислете за премахване и добавяне на елемент.

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

Да предположим, че имаме списък от 5 елемента и искаме да премахнем 3-тия.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

В този случай премахването освобождава една клетка, така че трябва да напишем 4-тия елемент там, където е бил 3-тият, и 5-тия, където е бил 4-тият.

Това е крайно неефективно.

Същото се случва при добавяне на елемент в средата на списъка.

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

Връщайки се към примера със същия списък от 5 елемента, след премахването на 3-тия елемент, всичко, което трябва да направим, е просто да променим препратката на 2-рия елемент към следващия елемент и препратката на 4-тия елемент към предишния.

Когато елемент се добави към списъка, се случва същият процес, но в обратна посока.

Забележете колко по-малко работа трябва да свършим в LinkedList в сравнение с ArrayList . И това са само 5 елемента. Ако нашият списък имаше 100 or повече елемента, превъзходството на LinkedList щеше да стане още по-забележимо.

Но How се променя ситуацията, ако имаме достъп до елемент по индекс?

Тук всичко е точно обратното.

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

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

Да се ​​опитаме ли да изразим всичко това с голямото О?

Нека започнем с достъп до елемент по индекс.

В ArrayList това се случва в една стъпка, независимо къде се намира елементът в списъка. Дали в края or в началото.

В този случай времевата сложност ще бъде O(1) .

В LinkedList трябва да преминем през редица елементи, равни на стойността на индекса, от който се нуждаем.

Времевата сложност за такова действие е O(n) , където n е индексът на елемента, от който се нуждаем.

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

Ще се върнем ли към премахването и добавянето?

Да започнем с LinkedList.

Тъй като не е необходимо да извършваме голям брой действия, за да добавим or премахнем елемент, а скоростта на тази операция не зависи по ниHowъв начин от това къде се намира елементът, неговата сложност се изразява като O(1) и се казва да бъде постоянна.

Времевата сложност на тази операция за ArrayList също е O(n) , което наричаме линейна сложност.

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

Времевата сложност може да бъде и логаритмична. Това се изразява като O(log n) .

Като пример, помислете за сортиран TreeSet , състоящ се от 10 числа. Искаме да намерим числото 2.

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

Ето table, която обобщава времевата сложност на останалите колекции.

Сега, когато имаме table, показваща времевата сложност на популярните колекции, можем да отговорим на въпроса защо от толкова много колекции най-често използваме ArrayList , HashSet и HashMap .

Просто те са най-ефективни за повечето задачи :)