Структуры данных и алгоритмы в Java, часть 1: Обзор

Программисты на Java используют структуры данных для хранения и организации данных, а мы используем алгоритмы для управления данными в этих структурах. Чем больше вы понимаете структуры данных и алгоритмы, а также то, как они работают вместе, тем эффективнее будут ваши программы Java.

Это руководство запускает небольшую серию статей, посвященных структурам данных и алгоритмам. В части 1 вы узнаете, что такое структура данных и как классифицируются структуры данных. Вы также узнаете, что такое алгоритм, как представлены алгоритмы и как использовать функции временной и пространственной сложности для сравнения похожих алгоритмов. Освоив эти основы, вы будете готовы узнать о поиске и сортировке с помощью одномерных массивов в части 2.

Что такое структура данных?

Структуры данных основаны на абстрактных типах данных (ADT), которые Википедия определяет следующим образом:

[A] математическая модель для типов данных, в которой тип данных определяется своим поведением (семантикой) с точки зрения пользователя данных, в частности с точки зрения возможных значений, возможных операций с данными этого типа и поведения этих операций.

ADT не заботится о представлении в памяти своих значений или о том, как реализованы его операции. Это похоже на интерфейс Java, который представляет собой тип данных, не связанный с какой-либо реализацией. Напротив, структура данных - это конкретная реализация одного или нескольких ADT, подобно тому, как классы Java реализуют интерфейсы.

Примеры ADT включают Employee, Vehicle, Array и List. Рассмотрим ADT списка (также известный как ADT последовательности), который описывает упорядоченный набор элементов, имеющих общий тип. Каждый элемент в этой коллекции имеет свое собственное положение, и разрешены повторяющиеся элементы. Основные операции, поддерживаемые List ADT, включают:

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

Структуры данных, которые могут реализовать List ADT, включают одномерные массивы фиксированного и динамического размера и односвязные списки. (Вы познакомитесь с массивами в Части 2 и связанными списками в Части 3.)

Классификация структур данных

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

Примитивы против агрегатов

В простейшем виде структуры данных хранятся отдельные элементы данных; например, переменная, в которой хранится логическое значение, или переменная, в которой хранится целое число. Я называю такие структуры данных примитивами .

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

Все структуры данных, которые мы рассмотрим в этой серии, являются агрегированными.

Контейнеры

Все, из чего хранятся и извлекаются элементы данных, можно рассматривать как структуру данных. Примеры включают структуры данных, полученные из ранее упомянутых ADT Employee, Vehicle, Array и List.

Многие структуры данных предназначены для описания различных сущностей. Экземпляры Employeeкласса - это структуры данных, которые существуют, например, для описания различных сотрудников. Напротив, некоторые структуры данных существуют как общие сосуды для хранения других структур данных. Например, массив может хранить примитивные значения или ссылки на объекты. Я называю эту последнюю категорию структур данных контейнерами .

Все структуры данных, которые мы рассмотрим в этой серии, не только агрегаты, но и контейнеры.

Структуры данных и алгоритмы в коллекциях Java

Платформа 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являются интерфейсами, описывающими 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