Structures de données et algorithmes en Java, partie 1: présentation

Les programmeurs Java utilisent des structures de données pour stocker et organiser les données, et nous utilisons des algorithmes pour manipuler les données dans ces structures. Plus vous comprendrez les structures de données et les algorithmes, et comment ils fonctionnent ensemble, plus vos programmes Java seront efficaces.

Ce tutoriel lance une courte série présentant les structures de données et les algorithmes. Dans la partie 1, vous apprendrez ce qu'est une structure de données et comment les structures de données sont classées. Vous apprendrez également ce qu'est un algorithme, comment les algorithmes sont représentés et comment utiliser les fonctions de complexité temporelle et spatiale pour comparer des algorithmes similaires. Une fois que vous avez ces bases, vous serez prêt à en savoir plus sur la recherche et le tri avec des tableaux unidimensionnels, dans la partie 2.

Qu'est-ce qu'une structure de données?

Les structures de données sont basées sur des types de données abstraits (ADT), que Wikipédia définit comme suit:

[A] modèle mathématique pour les types de données où un type de données est défini par son comportement (sémantique) du point de vue d'un utilisateur des données, notamment en termes de valeurs possibles, d'opérations possibles sur des données de ce type et du comportement de ces opérations.

Un ADT ne se soucie pas de la représentation en mémoire de ses valeurs ou de la façon dont ses opérations sont implémentées. C'est comme une interface Java, qui est un type de données déconnecté de toute implémentation. En revanche, une structure de données est une implémentation concrète d'un ou plusieurs ADT, similaire à la façon dont les classes Java implémentent les interfaces.

Les exemples d'ADT incluent l'employé, le véhicule, la baie et la liste. Considérez la liste ADT (également connue sous le nom de séquence ADT), qui décrit une collection ordonnée d'éléments partageant un type commun. Chaque élément de cette collection a sa propre position et les éléments en double sont autorisés. Les opérations de base prises en charge par List ADT comprennent:

  • Créer une nouvelle liste vide
  • Ajout d'une valeur à la fin de la liste
  • Insérer une valeur dans la liste
  • Supprimer une valeur de la liste
  • Itérer sur la liste
  • Détruire la liste

Les structures de données qui peuvent implémenter la liste ADT comprennent des tableaux unidimensionnels de taille fixe et de taille dynamique et des listes à liaison unique. (Vous serez présenté aux tableaux dans la partie 2 et aux listes liées dans la partie 3.)

Classification des structures de données

Il existe de nombreux types de structures de données, allant des variables simples aux tableaux ou aux listes liées d'objets contenant plusieurs champs. Toutes les structures de données peuvent être classées comme primitives ou agrégats, et certaines sont classées comme conteneurs.

Primitifs vs agrégats

Le type le plus simple de structure de données stocke des éléments de données uniques; par exemple, une variable qui stocke une valeur booléenne ou une variable qui stocke un entier. Je qualifie ces structures de données de primitives .

De nombreuses structures de données sont capables de stocker plusieurs éléments de données. Par exemple, un tableau peut stocker plusieurs éléments de données dans ses différents emplacements, et un objet peut stocker plusieurs éléments de données via ses champs. J'appelle ces structures de données des agrégats .

Toutes les structures de données que nous examinerons dans cette série sont des agrégats.

Conteneurs

Tout élément à partir duquel des éléments de données sont stockés et extraits peut être considéré comme une structure de données. Les exemples incluent les structures de données dérivées des ADT Employé, Véhicule, Array et Liste mentionnés précédemment.

De nombreuses structures de données sont conçues pour décrire diverses entités. Les instances d'une Employeeclasse sont des structures de données qui existent pour décrire divers employés, par exemple. En revanche, certaines structures de données existent en tant que conteneurs de stockage génériques pour d'autres structures de données. Par exemple, un tableau peut stocker des valeurs primitives ou des références d'objet. J'appelle cette dernière catégorie de structures de données des conteneurs .

En plus d'être des agrégats, toutes les structures de données que nous examinerons dans cette série sont des conteneurs.

Structures de données et algorithmes dans les collections Java

Le Java Collections Framework prend en charge de nombreux types de structures de données orientées conteneur et d'algorithmes associés. Cette série vous aidera à mieux comprendre ce cadre.

Modèles de conception et structures de données

Il est devenu assez courant d'utiliser des modèles de conception pour présenter aux étudiants universitaires les structures de données. Un article de l'Université Brown examine plusieurs modèles de conception utiles pour concevoir des structures de données de haute qualité. Entre autres choses, l'article démontre que le modèle d'adaptateur est utile pour concevoir des piles et des files d'attente. Le code de démonstration est présenté dans la liste 1.

Liste 1. Utilisation du modèle d'adaptateur pour les piles et les files d'attente (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(); } } }

Le listing 1 extrait la DequeStackclasse du papier de l'Université Brown , qui montre le modèle Adapter. Notez que Stacket Dequesont des interfaces qui décrivent les ADT Stack et Deque. MyDequeest une classe qui implémente Deque.

Remplacer les méthodes d'interface

Le code original que l' inscription 1 est basée sur ne présente pas le code source Stack, Dequeet MyDeque. Pour plus de clarté, j'ai introduit des @Overrideannotations pour montrer que toutes DequeStackles méthodes non constructeurs de s remplacent les Stackméthodes.

DequeStacks'adapte MyDequepour qu'il puisse mettre en œuvre Stack. Toutes DequeStackles méthodes de sont des appels sur une ligne aux Dequeméthodes de l' interface. Cependant, il y a une petite ride dans laquelle les Dequeexceptions sont converties en Stackexceptions.

Qu'est-ce qu'un algorithme?

Historiquement utilisés comme outil de calcul mathématique, les algorithmes sont profondément liés à l'informatique, et aux structures de données en particulier. Un algorithme est une séquence d'instructions qui accomplit une tâche dans une période de temps finie. Les qualités d'un algorithme sont les suivantes:

  • Reçoit zéro ou plusieurs entrées
  • Produit au moins une sortie
  • Se compose d'instructions claires et sans ambiguïté
  • Se termine après un nombre fini d'étapes
  • Est suffisamment basique pour qu'une personne puisse l'exécuter à l'aide d'un crayon et de papier

Notez que si les programmes peuvent être de nature algorithmique, de nombreux programmes ne se terminent pas sans intervention externe.

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.
  • Une fonction de complexité spatiale mesure la complexité spatiale d' un algorithme, c'est-à- dire la quantité de surcharge mémoire requise par l'algorithme pour effectuer sa tâche.

Les deux fonctions de complexité sont basées sur la taille de l'entrée ( n ), qui reflète en quelque sorte la quantité de données d'entrée. Considérez le pseudo-code suivant pour l'impression de tableaux:

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

Fonctions de complexité temporelle et de complexité temporelle

Vous pouvez exprimer la complexité temporelle de cet algorithme en spécifiant la fonction de complexité temporelle , où (un multiplicateur constant) représente le temps nécessaire pour terminer une itération de boucle et représente le temps de configuration de l'algorithme. Dans cet exemple, la complexité temporelle est linéaire.t(n) = an+bab