Datenstrukturen und Algorithmen in Java, Teil 1: Übersicht

Java-Programmierer verwenden Datenstrukturen zum Speichern und Organisieren von Daten, und wir verwenden Algorithmen, um die Daten in diesen Strukturen zu bearbeiten. Je mehr Sie über Datenstrukturen und Algorithmen wissen und wie diese zusammenarbeiten, desto effizienter werden Ihre Java-Programme.

Dieses Tutorial startet eine kurze Reihe, in der Datenstrukturen und Algorithmen vorgestellt werden. In Teil 1 erfahren Sie, was eine Datenstruktur ist und wie Datenstrukturen klassifiziert werden. Sie erfahren auch, was ein Algorithmus ist, wie Algorithmen dargestellt werden und wie Sie Zeit- und Raumkomplexitätsfunktionen verwenden, um ähnliche Algorithmen zu vergleichen. Sobald Sie diese Grundlagen haben, können Sie in Teil 2 lernen, wie Sie mit eindimensionalen Arrays suchen und sortieren.

Was ist eine Datenstruktur?

Datenstrukturen basieren auf abstrakten Datentypen (ADT), die Wikipedia wie folgt definiert:

[A] mathematisches Modell für Datentypen, bei dem ein Datentyp durch sein Verhalten (Semantik) aus Sicht eines Benutzers der Daten definiert wird, insbesondere hinsichtlich möglicher Werte, möglicher Operationen an Daten dieses Typs und des Verhaltens dieser Operationen.

Ein ADT kümmert sich nicht um die Speicherdarstellung seiner Werte oder die Implementierung seiner Operationen. Es ist wie eine Java-Schnittstelle, ein Datentyp, der von jeder Implementierung getrennt ist. Im Gegensatz dazu ist eine Datenstruktur eine konkrete Implementierung eines oder mehrerer ADTs, ähnlich wie Java-Klassen Schnittstellen implementieren.

Beispiele für ADTs sind Mitarbeiter, Fahrzeug, Array und Liste. Betrachten Sie die List ADT (auch als Sequence ADT bezeichnet), die eine geordnete Sammlung von Elementen beschreibt, die einen gemeinsamen Typ haben. Jedes Element in dieser Sammlung hat seine eigene Position und doppelte Elemente sind zulässig. Grundlegende Operationen, die von List ADT unterstützt werden, umfassen:

  • Erstellen einer neuen und leeren Liste
  • Anhängen eines Werts an das Ende der Liste
  • Einfügen eines Wertes in die Liste
  • Löschen eines Wertes aus der Liste
  • Durch die Liste iterieren
  • Die Liste zerstören

Datenstrukturen, die das Listen-ADT implementieren können, umfassen eindimensionale Arrays mit fester und dynamischer Größe sowie einfach verknüpfte Listen. (In Teil 2 werden Sie mit Arrays und in Teil 3 mit verknüpften Listen vertraut gemacht.)

Datenstrukturen klassifizieren

Es gibt viele Arten von Datenstrukturen, von einzelnen Variablen bis hin zu Arrays oder verknüpften Listen von Objekten, die mehrere Felder enthalten. Alle Datenstrukturen können als Grundelemente oder Aggregate klassifiziert werden, und einige werden als Container klassifiziert.

Primitive gegen Aggregate

Die einfachste Art der Datenstruktur speichert einzelne Datenelemente. Zum Beispiel eine Variable, die einen Booleschen Wert speichert, oder eine Variable, die eine Ganzzahl speichert. Ich bezeichne solche Datenstrukturen als Grundelemente .

Viele Datenstrukturen können mehrere Datenelemente speichern. Beispielsweise kann ein Array mehrere Datenelemente in seinen verschiedenen Steckplätzen speichern, und ein Objekt kann mehrere Datenelemente über seine Felder speichern. Ich bezeichne diese Datenstrukturen als Aggregate .

Alle Datenstrukturen, die wir in dieser Reihe betrachten, sind Aggregate.

Behälter

Alles, aus dem Datenelemente gespeichert und abgerufen werden, kann als Datenstruktur betrachtet werden. Beispiele hierfür sind die Datenstrukturen, die aus den zuvor genannten ADTs für Mitarbeiter, Fahrzeuge, Arrays und Listen abgeleitet wurden.

Viele Datenstrukturen beschreiben verschiedene Entitäten. Instanzen einer EmployeeKlasse sind Datenstrukturen, die beispielsweise zur Beschreibung verschiedener Mitarbeiter vorhanden sind. Im Gegensatz dazu existieren einige Datenstrukturen als generische Speichergefäße für andere Datenstrukturen. Ein Array kann beispielsweise primitive Werte oder Objektreferenzen speichern. Ich bezeichne diese letztere Kategorie von Datenstrukturen als Container .

Alle Datenstrukturen, die wir in dieser Reihe betrachten, sind nicht nur Aggregate, sondern auch Container.

Datenstrukturen und Algorithmen in Java-Sammlungen

Das Java Collections Framework unterstützt viele Arten von containerorientierten Datenstrukturen und zugehörigen Algorithmen. Diese Serie wird Ihnen helfen, dieses Framework besser zu verstehen.

Entwurfsmuster und Datenstrukturen

Es ist ziemlich üblich geworden, Entwurfsmuster zu verwenden, um Universitätsstudenten in Datenstrukturen einzuführen. In einem Artikel der Brown University werden verschiedene Entwurfsmuster untersucht, die für den Entwurf hochwertiger Datenstrukturen nützlich sind. Das Papier zeigt unter anderem, dass das Adaptermuster zum Entwerfen von Stapeln und Warteschlangen nützlich ist. Der Demonstrationscode ist in Listing 1 dargestellt.

Listing 1. Verwenden des Adaptermusters für Stapel und Warteschlangen (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 zeigt einen Auszug aus der DequeStackKlasse der Brown University , in der das Adaptermuster demonstriert wird. Beachten Sie, dass Stackund DequeSchnittstellen sind, die Stack- und Deque-ADTs beschreiben. MyDequeist eine Klasse, die implementiert Deque.

Überschreiben von Schnittstellenmethoden

Der ursprüngliche Code , dass ein Eintrag auf beruht habe präsentieren den Quellcode nicht zu Stack, Dequeund MyDeque. Aus Gründen der Übersichtlichkeit habe ich @OverrideAnmerkungen eingeführt, um zu zeigen, dass alle DequeStackNicht-Konstruktor-Methoden Methoden überschreiben Stack.

DequeStackpasst sich an, MyDequedamit es implementiert werden kann Stack. Alle DequeStackMethoden sind einzeilige Aufrufe der DequeSchnittstellenmethoden. Es gibt jedoch eine kleine Falte, in der DequeAusnahmen in StackAusnahmen umgewandelt werden .

Was ist ein Algorithmus?

In der Vergangenheit als Werkzeug für mathematische Berechnungen verwendet, sind Algorithmen eng mit der Informatik und insbesondere mit Datenstrukturen verbunden. Ein Algorithmus ist eine Folge von Anweisungen, die eine Aufgabe in einem begrenzten Zeitraum ausführen. Die Eigenschaften eines Algorithmus sind wie folgt:

  • Empfängt null oder mehr Eingaben
  • Erzeugt mindestens eine Ausgabe
  • Besteht aus klaren und eindeutigen Anweisungen
  • Beendet nach einer endlichen Anzahl von Schritten
  • Ist grundlegend genug, dass eine Person es mit Bleistift und Papier ausführen kann

Beachten Sie, dass Programme zwar algorithmischer Natur sein können, viele Programme jedoch nicht ohne externe Intervention beendet werden.

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.
  • Eine Raumkomplexitätsfunktion misst die Raumkomplexität eines Algorithmus - dh den Speicheraufwand, den der Algorithmus zur Ausführung seiner Aufgabe benötigt.

Beide Komplexitätsfunktionen basieren auf der Größe der Eingabe ( n ), die irgendwie die Menge der Eingabedaten widerspiegelt. Betrachten Sie den folgenden Pseudocode für den Array-Druck:

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

Zeitkomplexität und Zeitkomplexitätsfunktionen

Sie können die Zeitkomplexität dieses Algorithmus ausdrücken, indem Sie die Zeitkomplexitätsfunktion angeben , wobei (ein konstanter Multiplikator) die Zeitdauer für die Durchführung einer Schleifeniteration und die Einrichtungszeit des Algorithmus darstellt. In diesem Beispiel ist die zeitliche Komplexität linear.t(n) = an+bab