Datastrukturer och algoritmer i Java, del 1: översikt

Java-programmerare använder datastrukturer för att lagra och organisera data, och vi använder algoritmer för att manipulera data i dessa strukturer. Ju mer du förstår om datastrukturer och algoritmer, och hur de fungerar tillsammans, desto effektivare blir dina Java-program.

Denna handledning lanserar en kort serie som introducerar datastrukturer och algoritmer. I del 1 lär du dig vad en datastruktur är och hur datastrukturer klassificeras. Du lär dig också vad en algoritm är, hur algoritmer representeras och hur man använder tids- och rymdkomplexitetsfunktioner för att jämföra liknande algoritmer. När du har fått dessa grunder är du redo att lära dig mer om sökning och sortering med endimensionella matriser, i del 2.

Vad är en datastruktur?

Datastrukturer baseras på abstrakta datatyper (ADT), som Wikipedia definierar enligt följande:

[A] matematisk modell för datatyper där en datatyp definieras av dess beteende (semantik) ur en användares synvinkel, specifikt när det gäller möjliga värden, möjliga operationer av data av denna typ och beteende av dessa operationer.

En ADT bryr sig inte om minnesrepresentationen av dess värden eller hur dess operationer implementeras. Det är som ett Java-gränssnitt, vilket är en datatyp som är bortkopplad från alla implementeringar. Däremot är en datastruktur en konkret implementering av en eller flera ADT: er, liknande hur Java-klasser implementerar gränssnitt.

Exempel på ADT inkluderar medarbetare, fordon, matris och lista. Tänk på listan ADT (även känd som Sequence ADT), som beskriver en ordnad samling element som delar en gemensam typ. Varje element i denna samling har sin egen position och dubbletter är tillåtna. Grundläggande funktioner som stöds av List ADT inkluderar:

  • Skapa en ny och tom lista
  • Lägga till ett värde i slutet av listan
  • Infoga ett värde i listan
  • Radera ett värde från listan
  • Itererar över listan
  • Förstör listan

Datastrukturer som kan implementera List ADT inkluderar fasta och dynamiskt dimensionerade endimensionella matriser och enskilt länkade listor. (Du kommer att presenteras för arrays i del 2 och länkade listor i del 3.)

Klassificering av datastrukturer

Det finns många typer av datastrukturer, allt från enstaka variabler till matriser eller länkade listor med objekt som innehåller flera fält. Alla datastrukturer kan klassificeras som primitiva eller aggregat, och vissa klassificeras som behållare.

Primitiver mot aggregat

Den enklaste typen av datastruktur lagrar enskilda dataobjekt; till exempel en variabel som lagrar ett booleskt värde eller en variabel som lagrar ett heltal. Jag hänvisar till sådana datastrukturer som primitiva .

Många datastrukturer kan lagra flera dataobjekt. Till exempel kan en matris lagra flera dataobjekt i sina olika platser, och ett objekt kan lagra flera dataobjekt via sina fält. Jag hänvisar till dessa datastrukturer som aggregat .

Alla datastrukturer som vi kommer att titta på i denna serie är aggregat.

Behållare

Allt från vilket dataposter lagras och hämtas kan betraktas som en datastruktur. Exempel inkluderar datastrukturer härledda från tidigare nämnda anställda, fordon, matris och lista ADT.

Många datastrukturer är utformade för att beskriva olika enheter. Exempel på en Employeeklass är datastrukturer som finns för att till exempel beskriva olika anställda. Däremot finns vissa datastrukturer som generiska lagringsfartyg för andra datastrukturer. Till exempel kan en matris lagra primitiva värden eller objektreferenser. Jag hänvisar till den senare kategorin av datastrukturer som containrar .

Förutom att vara aggregat är alla datastrukturer som vi kommer att titta på i denna serie containrar.

Datastrukturer och algoritmer i Java-samlingar

Java Collections Framework stöder många typer av containerorienterade datastrukturer och tillhörande algoritmer. Denna serie hjälper dig att bättre förstå denna ram.

Designmönster och datastrukturer

Det har blivit ganska vanligt att använda designmönster för att introducera universitetsstudenter till datastrukturer. I ett Brown University-papper undersöks flera designmönster som är användbara för att utforma datastrukturer av hög kvalitet. Bland annat visar papperet att adaptermönstret är användbart för att utforma staplar och köer. Demonstrationskoden visas i Listing 1.

Listning 1. Använda adaptermönstret för stackar och köer (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(); } } }

Listning 1 utdrag ur Brown University-tidningens DequeStackklass, som visar adaptermönstret. Observera att Stackoch Dequeär gränssnitt som beskriver Stack och Deque ADT. MyDequeär en klass som implementeras Deque.

Åsidosättande gränssnittsmetoder

Den ursprungliga koden som Listing 1 baseras på inte presentera källkoden till Stack, Dequeoch MyDeque. För tydlighetens skull har jag infört @Overrideanteckningar för att visa att alla DequeStackicke-konstruktörmetoder åsidosätter Stackmetoder.

DequeStackanpassar sig MyDequeså att den kan implementeras Stack. Alla DequeStackmetoden är enradiga samtal till Dequegränssnittsmetoderna. Det finns dock en liten rynka där Dequeundantag omvandlas till Stackundantag.

Vad är en algoritm?

Historiskt används som ett verktyg för matematisk beräkning, algoritmer är djupt kopplade till datavetenskap, och med datastrukturer i synnerhet. En algoritm är en sekvens av instruktioner som utför en uppgift under en begränsad tidsperiod. Kvaliteterna hos en algoritm är som följer:

  • Tar emot noll eller fler ingångar
  • Producerar minst en produktion
  • Består av tydliga och entydiga instruktioner
  • Avslutas efter ett begränsat antal steg
  • Är tillräckligt grundläggande för att en person ska kunna utföra det med penna och papper

Observera att även om program kan vara av algoritmisk natur, avslutas många program inte utan extern intervention.

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.
  • En rymdkomplexitetsfunktion mäter en algoritms rymdkomplexitet - vilket betyder mängden minneomkostnader som krävs av algoritmen för att utföra sin uppgift.

Båda komplexitetsfunktionerna baseras på storleken på ingången ( n ), vilket på något sätt återspeglar mängden ingångsdata. Tänk på följande pseudokod för matrisutskrift:

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

Tidskomplexitet och tidskomplexitetsfunktioner

Du kan uttrycka tidskomplexiteten för denna algoritm genom att ange tidskomplexitetsfunktionen , där (en konstant multiplikator) representerar tiden för att slutföra en loop-iteration och representerar algoritmens inställningstid. I detta exempel är tidskomplexiteten linjär.t(n) = an+bab