Структури на данни и алгоритми в Java, Част 1: Общ преглед

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

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

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

Структурите на данните се основават на абстрактни типове данни (ADT), които Уикипедия определя, както следва:

[A] математически модел за типове данни, при който типът данни се дефинира от неговото поведение (семантика) от гледна точка на потребител на данните, по-специално по отношение на възможни стойности, възможни операции с данни от този тип и поведение от тези операции.

ADT не се интересува от представянето на паметта на своите стойности или как се изпълняват неговите операции. Това е като Java интерфейс, който е тип данни, който е прекъснат от всяко изпълнение. За разлика от това, структурата на данните е конкретна реализация на един или повече ADT, подобно на това как Java класовете реализират интерфейси.

Примерите за ADT включват служител, превозно средство, масив и списък. Да разгледаме списъка ADT (известен също като Sequence ADT), който описва подредена колекция от елементи, които споделят общ тип. Всеки елемент в тази колекция има своя позиция и се допускат дублиращи се елементи. Основните операции, поддържани от списъка ADT, включват:

  • Създаване на нов и празен списък
  • Добавяне на стойност в края на списъка
  • Вмъкване на стойност в списъка
  • Изтриване на стойност от списъка
  • Итерация върху списъка
  • Унищожаване на списъка

Структурите на данни, които могат да реализират ADT на списъка, включват едномерни масиви с фиксиран размер и динамичен размер и единично свързани списъци. (Ще се запознаете с масивите в част 2 и свързаните списъци в част 3.)

Класифициране на структури от данни

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

Примитиви срещу агрегати

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

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

Всички структури от данни, които ще разгледаме в тази поредица, са агрегати.

Контейнери

Всичко, от което се съхраняват и извличат елементи от данни, може да се счита за структура на данните. Примерите включват структури от данни, получени от споменатите по-горе ADT за служители, превозни средства, масиви и списъци.

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

Освен че са агрегати, всички структури от данни, които ще разгледаме в тази серия, са и контейнери.

Структури на данни и алгоритми в Java Collections

Java Collections Framework поддържа много видове структурирани с данни структури и свързани алгоритми. Тази поредица ще ви помогне да разберете по-добре тази рамка.

Проектиране на модели и структури от данни

Стана доста често да се използват модели на проектиране, за да се запознаят студентите със структурите на данните. Документ от университета Браун изследва няколко модела на проектиране, които са полезни за проектиране на висококачествени структури от данни. Наред с други неща, хартията показва, че моделът на адаптера е полезен за проектиране на стекове и опашки. Демонстрационният код е показан в Листинг 1.

Листинг 1. Използване на адаптерния модел за стекове и опашки (DequeStack.java)

public class DequeStack implements Stack { Deque D; // holds the elements of the stack public DequeStack() { D = new MyDeque(); } @Override public int size() { return D.size(); } @Override public boolean isEmpty() { return D.isEmpty(); } @Override public void push(Object obj) { D.insertLast(obj); } @Override public Object top() throws StackEmptyException { try { return D.lastElement(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } @Override public Object pop() throws StackEmptyException { try { return D.removeLast(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } }

Списък 1 откъсва DequeStackкласа на хартията на университета Браун , който показва модела на адаптера Имайте предвид, че Stackи Dequeса интерфейси, които описват Stack и Deque ADT. MyDequeе клас, който изпълнява Deque.

Замяна на интерфейсните методи

Оригиналният код, който Обява 1 се основава на не представи на изходния код на Stack, Dequeи MyDeque. За по-голяма яснота въведох @Overrideпояснения, за да покажа, че всички DequeStackнеконструкторски методи заместват Stackметодите.

DequeStackадаптира, MyDequeтака че да може да изпълнява Stack. Всички DequeStackметоди на са едноредови повиквания към Dequeметодите на интерфейса. Има обаче малка бръчка, при която Dequeизключенията се превръщат в Stackизключения.

Какво е алгоритъм?

Исторически използвани като инструмент за математическо изчисление, алгоритмите са дълбоко свързани с компютърните науки и по-специално със структурите на данни. Един алгоритъм е последователност от инструкции, които изпълнява задача, в краен период от време. Качествата на алгоритъма са както следва:

  • Получава нула или повече входове
  • Произвежда поне един изход
  • Състои се от ясни и недвусмислени инструкции
  • Прекратява се след краен брой стъпки
  • Достатъчно основно е човек да може да го изпълни с молив и хартия

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

Many code sequences qualify as algorithms. One example is a code sequence that prints a report. More famously, Euclid's algorithm is used to calculate the mathematical greatest common divisor. A case could even be made that a data structure's basic operations (such as store value in array slot) are algorithms. In this series, for the most part, I'll focus on higher-level algorithms used to process data structures, such as the Binary Search and Matrix Multiplication algorithms.

Flowcharts and pseudocode

How do you represent an algorithm? Writing code before fully understanding its underlying algorithm can lead to bugs, so what's a better alternative? Two options are flowcharts and pseudocode.

Using flowcharts to represent algorithms

A flowchart is a visual representation of an algorithm's control flow. This representation illustrates statements that need to be executed, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. Figure 1 reveals the various symbols that flowcharts use to visualize algorithms.

Consider an algorithm that initializes a counter to 0, reads characters until a newline (\n) character is seen, increments the counter for each digit character that's been read, and prints the counter's value after the newline character has been read. The flowchart in Figure 2 illustrates this algorithm's control flow.

A flowchart's simplicity and its ability to present an algorithm's control flow visually (so that it's is easy to follow) are its major advantages. Flowcharts also have several disadvantages, however:

  • It's easy to introduce errors or inaccuracies into highly-detailed flowcharts because of the tedium associated with drawing them.
  • It takes time to position, label, and connect a flowchart's symbols, even using tools to speed up this process. This delay might slow your understanding of an algorithm.
  • Flowcharts belong to the structured programming era and aren't as useful in an object-oriented context. In contrast, the Unified Modeling Language (UML) is more appropriate for creating object-oriented visual representations.

Using pseudocode to represent algorithms

An alternative to flowcharts is pseudocode, which is a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, there are no hard-and-fast rules for writing pseudocode.

You should strive for consistency when writing pseudocode. Being consistent will make it much easier to translate the pseudocode into actual source code. For example, consider the following pseudocode representation of the previous counter-oriented flowchart:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ ch IF ch GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\n' PRINT count END

The pseudocode first presents a couple of DECLARE statements that introduce variables ch and count, initialized to default values. It then presents a DO loop that executes UNTILch contains \n (the newline character), at which point the loop ends and a PRINT statement outputs count's value.

For each loop iteration, READ causes a character to be read from the keyboard (or perhaps a file--in this case it doesn't matter what constitutes the underlying input source) and assigned to ch. If this character is a digit (one of 0 through 9), count is incremented by 1.

Choosing the right algorithm

The data structures and algorithms you use critically affect two factors in your applications:

  1. Memory usage (for data structures).
  2. CPU time (for algorithms that interact with those data structures).

It follows that you should be especially mindful of the algorithms and data structures you use for applications that will process lots of data. These include applications used for big data and the Internet of Things.

Balancing memory and CPU

When choosing a data structure or algorithm, you will sometimes discover an inverse relationship between memory usage and CPU time: the less memory a data structure uses, the more CPU time associated algorithms need to process the data structure's data items. Also, the more memory a data structure uses, the less CPU time associated algorithms will need to process the data items–leading to faster algorithm results.

As much as possible, you should strive to balance memory use with CPU time. You can simplify this task by analyzing algorithms to determine their efficiency. How well does one algorithm perform against another of similar nature? Answering this question will help you make good choices given a choice between multiple algorithms.

Measuring algorithm efficiency

Some algorithms perform better than others. For example, the Binary Search algorithm is almost always more efficient than the Linear Search algorithm–something you'll see for yourself in Part 2. You want to choose the most efficient algorithm for your application's needs, but that choice might not be as obvious as you would think.

For instance, what does it mean if the Selection Sort algorithm (introduced in Part 2) takes 0.4 seconds to sort 10,000 integers on a given machine? That benchmark is only valid for that particular machine, that particular implementation of the algorithm, and for the size of the input data.

As computer scientist, we use time complexity and space complexity to measure an algorithm's efficiency, distilling these into complexity functions to abstract implementation and runtime environment details. Complexity functions reveal the variance in an algorithm's time and space requirements based on the amount of input data:

  • A time-complexity function measures an algorithm's time complexity--meaning how long an algorithm takes to complete.
  • Функцията за пространствена сложност измерва сложността на пространството на алгоритъма - означава размера на режийните разходи, необходими на алгоритъма за изпълнение на задачата му.

И двете функции на сложност се основават на размера на входа ( n ), който по някакъв начин отразява количеството на входните данни. Помислете за следния псевдокод за печат на масив:

 DECLARE INTEGER i, x[] = [ 10, 15, -1, 32 ] FOR i = 0 TO LENGTH(x) - 1 PRINT x[i] NEXT i END

Функции за сложност във времето и сложност във времето

Можете да изразите сложността на времето на този алгоритъм, като посочите функцията за време-сложност , където (постоянен множител) представлява времето за завършване на една итерация на цикъл и представлява времето за настройка на алгоритъма. В този пример сложността на времето е линейна.t(n) = an+bab