Strutture dati e algoritmi in Java, Parte 1: Panoramica

I programmatori Java utilizzano strutture di dati per memorizzare e organizzare i dati e noi usiamo algoritmi per manipolare i dati in quelle strutture. Più comprendi le strutture dati e gli algoritmi, e come funzionano insieme, più efficienti saranno i tuoi programmi Java.

Questo tutorial lancia una breve serie che introduce strutture di dati e algoritmi. Nella Parte 1, imparerai cos'è una struttura dati e come vengono classificate le strutture dati. Imparerai anche cos'è un algoritmo, come sono rappresentati gli algoritmi e come utilizzare le funzioni di complessità temporale e spaziale per confrontare algoritmi simili. Una volta acquisite queste nozioni di base, sarai pronto per imparare a cercare e ordinare con array unidimensionali, nella Parte 2.

Cos'è una struttura dati?

Le strutture dati sono basate su tipi di dati astratti (ADT), che Wikipedia definisce come segue:

[A] modello matematico per tipi di dati in cui un tipo di dati è definito dal suo comportamento (semantica) dal punto di vista di un utente dei dati, in particolare in termini di valori possibili, possibili operazioni su dati di questo tipo e comportamento di queste operazioni.

Un ADT non si preoccupa della rappresentazione in memoria dei suoi valori o di come vengono implementate le sue operazioni. È come un'interfaccia Java, che è un tipo di dati disconnesso da qualsiasi implementazione. Al contrario, una struttura dati è un'implementazione concreta di uno o più ADT, simile a come le classi Java implementano le interfacce.

Esempi di ADT includono Employee, Vehicle, Array e List. Considera l'elenco ADT (noto anche come Sequence ADT), che descrive una raccolta ordinata di elementi che condividono un tipo comune. Ogni elemento in questa raccolta ha la propria posizione e sono consentiti elementi duplicati. Le operazioni di base supportate da List ADT includono:

  • Creazione di un elenco nuovo e vuoto
  • Aggiunta di un valore alla fine dell'elenco
  • Inserimento di un valore all'interno della lista
  • Eliminazione di un valore dall'elenco
  • Iterando sulla lista
  • Distruggere l'elenco

Le strutture dati che possono implementare List ADT includono array unidimensionali di dimensioni fisse e dinamicamente dimensionati ed elenchi collegati singolarmente. (Ti verranno presentati gli array nella Parte 2 e gli elenchi collegati nella Parte 3.)

Classificazione delle strutture dati

Esistono molti tipi di strutture dati, che vanno dalle singole variabili agli array o agli elenchi collegati di oggetti contenenti più campi. Tutte le strutture di dati possono essere classificate come primitive o aggregate e alcune sono classificate come contenitori.

Primitive vs aggregati

Il tipo più semplice di struttura dati memorizza singoli elementi di dati; ad esempio, una variabile che memorizza un valore booleano o una variabile che memorizza un numero intero. Mi riferisco a tali strutture di dati come primitive .

Molte strutture dati sono in grado di memorizzare più elementi di dati. Ad esempio, un array può memorizzare più elementi di dati nei suoi vari slot e un oggetto può memorizzare più elementi di dati tramite i suoi campi. Mi riferisco a queste strutture di dati come aggregati .

Tutte le strutture di dati che esamineremo in questa serie sono aggregate.

Contenitori

Tutto ciò da cui gli elementi di dati vengono memorizzati e recuperati potrebbe essere considerato una struttura di dati. Gli esempi includono le strutture dati derivate dagli ADT Employee, Vehicle, Array e List precedentemente menzionati.

Molte strutture dati sono progettate per descrivere varie entità. Le istanze di una Employeeclasse sono strutture di dati che esistono per descrivere vari dipendenti, ad esempio. Al contrario, alcune strutture di dati esistono come contenitori di memoria generici per altre strutture di dati. Ad esempio, un array può memorizzare valori primitivi o riferimenti a oggetti. Mi riferisco a quest'ultima categoria di strutture dati come contenitori .

Oltre ad essere aggregate, tutte le strutture di dati che esamineremo in questa serie sono contenitori.

Strutture dati e algoritmi nelle collezioni Java

Il Java Collections Framework supporta molti tipi di strutture dati orientate ai contenitori e algoritmi associati. Questa serie ti aiuterà a comprendere meglio questo framework.

Modelli di progettazione e strutture dati

È diventato abbastanza comune utilizzare modelli di progettazione per introdurre gli studenti universitari alle strutture dati. Un documento della Brown University esamina diversi modelli di progettazione utili per progettare strutture di dati di alta qualità. Tra le altre cose, il documento dimostra che il pattern Adapter è utile per progettare stack e code. Il codice dimostrativo è mostrato nel listato 1.

Listato 1. Utilizzo del pattern Adapter per stack e code (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(); } } }

Il Listato 1 riprende la DequeStacklezione del documento della Brown University , che mostra il pattern Adapter. Notare che Stacke Dequesono interfacce che descrivono gli ADT Stack e Deque. MyDequeè una classe che implementa Deque.

Sostituzione dei metodi di interfaccia

Il codice originale che Listato 1 si basa su non ha presentato il codice sorgente per Stack, Dequee MyDeque. Per chiarezza, ho introdotto @Overrideannotazioni per mostrare che tutti DequeStacki metodi non costruttori sovrascrivono i Stackmetodi.

DequeStacksi adatta in MyDequemodo che possa implementare Stack. Tutti DequeStacki metodi di sono chiamate di una riga ai Dequemetodi dell'interfaccia. Tuttavia, c'è una piccola ruga in cui le Dequeeccezioni vengono convertite in Stackeccezioni.

Cos'è un algoritmo?

Storicamente utilizzati come strumento per il calcolo matematico, gli algoritmi sono profondamente connessi con l'informatica e con le strutture dati in particolare. Un algoritmo è una sequenza di istruzioni che esegue un'attività in un periodo di tempo finito. Le qualità di un algoritmo sono le seguenti:

  • Riceve zero o più input
  • Produce almeno un output
  • Consiste in istruzioni chiare e inequivocabili
  • Termina dopo un numero finito di passaggi
  • È abbastanza semplice che una persona possa eseguirlo usando carta e matita

Si noti che mentre i programmi possono essere di natura algoritmica, molti programmi non terminano senza intervento esterno.

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.
  • Una funzione di complessità spaziale misura la complessità dello spazio di un algoritmo, ovvero la quantità di overhead di memoria richiesta dall'algoritmo per eseguire il suo compito.

Entrambe le funzioni di complessità si basano sulla dimensione dell'input ( n ), che in qualche modo riflette la quantità di dati di input. Considera il seguente pseudocodice per la stampa di array:

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

Funzioni di complessità temporale e complessità temporale

È possibile esprimere la complessità temporale di questo algoritmo specificando la funzione di complessità temporale , dove (un moltiplicatore costante) rappresenta la quantità di tempo per completare l'iterazione di un ciclo e rappresenta il tempo di configurazione dell'algoritmo. In questo esempio, la complessità temporale è lineare.t(n) = an+bab