Struktury danych i algorytmy w Javie, Część 1: Przegląd

Programiści Java używają struktur danych do przechowywania i organizowania danych, a my używamy algorytmów do manipulowania danymi w tych strukturach. Im więcej wiesz o strukturach danych i algorytmach oraz o tym, jak one ze sobą współpracują, tym wydajniejsze będą Twoje programy Java.

Ten samouczek uruchamia krótką serię przedstawiającą struktury danych i algorytmy. W części 1 dowiesz się, czym jest struktura danych i jak są klasyfikowane struktury danych. Dowiesz się również, czym jest algorytm, w jaki sposób są reprezentowane i jak używać funkcji złożoności czasu i przestrzeni do porównywania podobnych algorytmów. Kiedy już opanujesz te podstawy, będziesz gotowy, aby nauczyć się wyszukiwania i sortowania za pomocą jednowymiarowych tablic w części 2.

Co to jest struktura danych?

Struktury danych są oparte na abstrakcyjnych typach danych (ADT), które Wikipedia definiuje w następujący sposób:

[A] model matematyczny dla typów danych, w których typ danych jest określony przez jego zachowanie (semantykę) z punktu widzenia użytkownika danych, w szczególności pod względem możliwych wartości, możliwych operacji na danych tego typu oraz zachowania tych operacji.

ADT nie dba o reprezentację swoich wartości w pamięci ani sposób implementacji jego operacji. To jest jak interfejs Java, który jest typem danych niezwiązanym z żadną implementacją. W przeciwieństwie do tego struktura danych jest konkretną implementacją jednego lub więcej ADT, podobnie jak klasy Java implementują interfejsy.

Przykłady ADT obejmują pracownika, pojazd, tablicę i listę. Rozważmy List ADT (znany również jako Sequence ADT), który opisuje uporządkowaną kolekcję elementów, które mają wspólny typ. Każdy element w tej kolekcji ma własną pozycję i dozwolone są zduplikowane elementy. Podstawowe operacje obsługiwane przez List ADT obejmują:

  • Tworzenie nowej, pustej listy
  • Dołączanie wartości na końcu listy
  • Wstawianie wartości na liście
  • Usuwanie wartości z listy
  • Iterowanie po liście
  • Zniszczenie listy

Struktury danych, które mogą zaimplementować List ADT, obejmują jednowymiarowe tablice o stałym rozmiarze i dynamiczne rozmiary oraz listy z pojedynczym połączeniem. (Tablice zostaną wprowadzone w części 2, a listy połączone w części 3.)

Klasyfikacja struktur danych

Istnieje wiele rodzajów struktur danych, od pojedynczych zmiennych po tablice lub połączone listy obiektów zawierających wiele pól. Wszystkie struktury danych można sklasyfikować jako prymitywy lub agregaty, a niektóre są klasyfikowane jako kontenery.

Prymitywy a agregaty

Najprostszy rodzaj struktury danych przechowuje pojedyncze elementy danych; na przykład zmienna przechowująca wartość logiczną lub zmienna przechowująca liczbę całkowitą. Nazywam takie struktury danych prymitywami .

Wiele struktur danych może przechowywać wiele elementów danych. Na przykład tablica może przechowywać wiele elementów danych w swoich różnych gniazdach, a obiekt może przechowywać wiele elementów danych za pośrednictwem swoich pól. Nazywam te struktury danych agregatami .

Wszystkie struktury danych, którym przyjrzymy się w tej serii, są agregacjami.

Pojemniki

Wszystko, z czego elementy danych są przechowywane i pobierane, można uznać za strukturę danych. Przykłady obejmują struktury danych pochodzące z wcześniej wspomnianych ADT pracowników, pojazdów, tablic i list.

Wiele struktur danych jest zaprojektowanych do opisywania różnych jednostek. Instancje Employeeklasy to struktury danych, które istnieją na przykład w celu opisania różnych pracowników. W przeciwieństwie do tego, niektóre struktury danych istnieją jako ogólne naczynia do przechowywania innych struktur danych. Na przykład tablica może przechowywać wartości pierwotne lub odniesienia do obiektów. Nazywam tę ostatnią kategorię struktur danych kontenerami .

Oprócz tego, że są agregatami, wszystkie struktury danych, którym przyjrzymy się w tej serii, są kontenerami.

Struktury danych i algorytmy w kolekcjach Java

Java Collections Framework obsługuje wiele rodzajów kontenerowych struktur danych i powiązanych algorytmów. Ta seria pomoże ci lepiej zrozumieć te ramy.

Wzorce projektowe i struktury danych

Dość powszechne stało się używanie wzorców projektowych do wprowadzania studentów w struktury danych. W artykule Uniwersytetu Brown przeanalizowano kilka wzorców projektowych, które są przydatne przy projektowaniu struktur danych o wysokiej jakości. W artykule wykazano między innymi, że wzorzec adaptera jest przydatny do projektowania stosów i kolejek. Kod demonstracyjny jest pokazany na liście 1.

Listing 1. Używanie wzorca adaptera dla stosów i kolejek (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(); } } }

Listing 1 zawiera fragmenty artykułu z Brown University DequeStack, które demonstrują wzorzec adaptera. Zauważ, że Stacki Dequesą to interfejsy opisujące Stack i Deque ADT. MyDequeto klasa, która implementuje Deque.

Zastępowanie metod interfejsu

Oryginalny kod, który Zamieszczone 1 oparta jest na nie przedstawił kodu źródłowego Stack, Dequeoraz MyDeque. Dla jasności wprowadziłem @Overrideadnotacje pokazujące, że wszystkie DequeStackmetody niebędące konstruktorami przesłaniają Stackmetody.

DequeStackdostosowuje się MyDequetak, aby mógł zaimplementować Stack. Wszystkie DequeStackmetody to jednowierszowe wywołania Dequemetod interfejsu. Istnieje jednak mała zmarszczka, w której Dequewyjątki są przekształcane w Stackwyjątki.

Co to jest algorytm?

Historycznie używane jako narzędzie do obliczeń matematycznych, algorytmy są głęboko związane z informatyką, w szczególności ze strukturami danych. Algorytm jest ciągiem instrukcji, który realizuje zadania w skończonym czasie. Cechy algorytmu są następujące:

  • Otrzymuje zero lub więcej danych wejściowych
  • Tworzy co najmniej jedno wyjście
  • Zawiera jasne i jednoznaczne instrukcje
  • Kończy się po skończonej liczbie kroków
  • Jest na tyle podstawowa, że ​​można to wykonać za pomocą ołówka i papieru

Należy pamiętać, że chociaż programy mogą mieć charakter algorytmiczny, wiele programów nie kończy się bez interwencji z zewnątrz.

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.
  • Funkcja złożoności przestrzennej mierzy złożoność przestrzeni algorytmu - czyli ilość narzutu pamięci wymaganej przez algorytm do wykonania swojego zadania.

Obie funkcje złożoności są oparte na rozmiarze danych wejściowych ( n ), co w pewien sposób odzwierciedla ilość danych wejściowych. Rozważ następujący pseudokod do drukowania tablic:

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

Funkcje złożoności czasowej i złożoności czasowej

Złożoność czasową tego algorytmu można wyrazić, określając funkcję złożoności czasowej , gdzie (stały mnożnik) reprezentuje ilość czasu potrzebną do zakończenia jednej iteracji pętli i reprezentuje czas konfiguracji algorytmu. W tym przykładzie złożoność czasowa jest liniowa.t(n) = an+bab