Conseils pour l'utilisation des collections

1. Liste des collections

Comme vous vous en souvenez peut-être, Java a des collections - un outil pratique pour stocker des objets du même type.

Essayons de rappeler les principales interfaces liées aux collections :

Liste , Ensemble , Carte et File d' attente .

Comme d'habitude, les outils ne sont pas nécessairement bons ou mauvais - ce qui compte, c'est de savoir si vous les utilisez aux fins prévues. Et pour cela, il faut bien comprendre leurs spécificités afin de savoir quelle collection utiliser et quand.

1. Liste

Commençons par la collection la plus utilisée.

Liste aussi proche que possible d'un ancien tableau ordinaire.

Cette collection nous permet de stocker facilement une liste d'objets du même type sans nous soucier de la taille de la collection elle-même, comme nous le ferions si nous utilisions un tableau. Les éléments de la collection sont accessibles par index. Si nous savons exactement où se trouve un objet et que nous devons y accéder fréquemment sans avoir souvent besoin d'ajouter ou de supprimer des éléments, une liste est idéale.

2. Définir

Set a une structure complètement différente.

Set est le plus approprié lorsque nous avons besoin de stocker des objets uniques. Par exemple, un ensemble d'auteurs dans une bibliothèque où chaque auteur est unique. Mais nous ne pouvons pas simplement aller chercher un auteur spécifique. Set nous permet de vérifier rapidement si un auteur particulier est présent dans notre bibliothèque, c'est-à-dire que nous pouvons vérifier si un objet unique est présent dans un Set . Nous pouvons également itérer sur l'ensemble de la collection, en accédant à chaque élément, mais cela n'est pas optimal.

En d'autres termes, pour notre bibliothèque, un ensemble peut représenter la collection de tous les auteurs uniques pour vérifier rapidement si un auteur particulier est présent.

3. Carte

Map ressemble plus à un classeur, où chaque fichier est signé et peut stocker des objets individuels ou des structures entières. Map doit être utilisé dans les cas où nous devons maintenir un mappage d'une valeur à une autre.

Pour Map , ces relations sont appelées paires clé-valeur.

Nous pourrions utiliser cette structure dans notre bibliothèque en utilisant des objets auteur comme clés et des listes ( objets List ) de livres comme valeurs. Ainsi, après avoir vérifié un Set pour voir si un objet author existe dans la bibliothèque, nous pouvons utiliser le même objet author pour obtenir une List de ses livres à partir d'un Map .

4. File d'attente

Queue est une collection qui — surprise ! — implémente le comportement d'une file d'attente. Et la file d'attente peut être LIFO (Last In, First Out) ou FIFO (First In, First Out). De plus, la file d'attente peut être bidirectionnelle ou "à double extrémité".

Cette structure est utile lorsque les objets ajoutés à la classe doivent être utilisés dans l'ordre dans lequel ils sont reçus. Par exemple, prenez notre bibliothèque.

Nous pouvons ajouter des visiteurs nouvellement arrivés à une file d'attente et les servir à tour de rôle, en leur publiant les livres qu'ils viennent chercher.

Comme nous pouvons le voir, chacune de ces structures est bonne si elle est utilisée conformément à sa destination. Et nous avons trouvé de bonnes utilisations pour les quatre types de collections dans un seul exemple de bibliothèque.

2. Complexité

Comme déjà noté, les collections que nous avons considérées ci-dessus sont des interfaces, ce qui signifie qu'elles doivent avoir des implémentations pour que nous puissions les utiliser.

Tout comme marteler des clous au microscope n'est pas la meilleure idée, toutes les réalisations d'une collection ne sont pas adaptées à toutes les situations.

Lors du choix du bon outil pour un travail, nous examinons généralement 2 caractéristiques :

• Dans quelle mesure l'outil convient-il au travail ?
• À quelle vitesse fera-t-il le travail ?

Nous avons passé un certain temps à comprendre comment choisir un outil adapté à un travail, mais sa rapidité est quelque chose de nouveau.

En informatique, la vitesse d'un outil est souvent exprimée en termes de complexité temporelle et notée par la lettre majuscule O.

Qu'est-ce que la complexité temporelle ?

En termes simples, la complexité temporelle indique le temps nécessaire à un algorithme de la collection pour effectuer une action particulière (ajout/suppression d'un élément, recherche d'un élément).

ArrayList vs LinkedList

Regardons cela en utilisant deux implémentations de l' interface List — ArrayList et LinkedList .

Pour les apparences extérieures, travailler avec ces collections est similaire :

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Comme vous pouvez le constater, pour les deux types de collection, l'ajout, l'obtention et la suppression d'éléments se ressemblent. En effet, ce sont des implémentations sur la même interface. Mais c'est là que s'arrêtent les similitudes.

En raison de leurs implémentations différentes de l' interface List , ces deux structures effectuent des actions différentes plus efficacement que d'autres.

Envisagez de supprimer et d'ajouter un élément.

Si nous devons supprimer un élément du milieu d'un ArrayList , nous devons écraser la partie de la liste qui suit l'élément que nous supprimons.

Supposons que nous ayons une liste de 5 éléments et que nous voulions supprimer le 3ème.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Dans ce cas, la suppression libère une cellule, il faut donc écrire le 4e élément là où se trouvait le 3e, et le 5e là où se trouvait le 4e.

C'est très inefficace.

La même chose se produit lors de l'ajout d'un élément au milieu de la liste.

LinkedList est structuré différemment. L'ajout ou la suppression d'éléments est rapide, car il suffit de modifier les références dans les éléments précédents et suivants, excluant ainsi l'objet que nous supprimons de la chaîne d'éléments.

Reprenant l'exemple de la même liste de 5 éléments, après avoir supprimé le 3ème élément, il suffit de changer la référence du 2ème élément à l'élément suivant et la référence du 4ème élément au précédent.

Lorsqu'un élément est ajouté à la liste, le même processus se produit, mais en sens inverse.

Remarquez combien de travail en moins nous devons faire dans une LinkedList par rapport à une ArrayList . Et ce ne sont que 5 éléments. Si notre liste avait 100 éléments ou plus, la supériorité de LinkedList deviendrait encore plus perceptible.

Mais comment la situation change-t-elle si nous accédons à un élément par index ?

Tout est exactement le contraire ici.

Puisque ArrayList est structuré comme un tableau ordinaire, obtenir n'importe quel élément par son index sera très facile pour nous. Nous déplaçons simplement le pointeur vers un certain endroit et obtenons l'élément de la cellule correspondante.

Mais une LinkedList ne fonctionne tout simplement pas de cette façon. Nous devons parcourir tous les éléments de la liste pour trouver l'élément avec un certain index.

Allons-nous essayer d'exprimer tout cela en termes de grand O ?

Commençons par accéder à un élément par index.

Dans une ArrayList , cela se produit en une seule étape, quel que soit l'emplacement de l'élément dans la liste. Que ce soit à la fin ou au début.

Dans ce cas, la complexité temporelle sera O(1) .

Dans une LinkedList , nous devons itérer sur un nombre d'éléments égal à la valeur de l'index dont nous avons besoin.

La complexité temporelle d'une telle action est O(n) , où n est l'indice de l'élément dont nous avons besoin.

Ici vous voyez que le nombre que nous mettons entre parenthèses big-O correspond au nombre d'actions effectuées.

Shell revenons-nous à la suppression et à l'ajout ?

Commençons par LinkedList.

Parce que nous n'avons pas besoin de faire un grand nombre d'actions pour ajouter ou supprimer un élément, et que la vitesse de cette opération ne dépend en aucune façon de l'endroit où se trouve l'élément, sa complexité s'exprime en O(1) et se dit être constant.

La complexité temporelle de cette opération pour ArrayList est également O(n) , que nous appelons complexité linéaire.

Dans les algorithmes à complexité linéaire, le temps d'exécution dépend directement du nombre d'éléments à traiter. Cela peut aussi dépendre de la position de l'élément, qu'il soit au début de la liste ou vers la fin.

La complexité temporelle peut également être logarithmique. Ceci est exprimé en O(log n) .

Par exemple, considérons un TreeSet trié composé de 10 nombres. Nous voulons trouver le numéro 2.

Étant donné que la liste est triée et ne contient pas de doublons, nous pouvons la diviser en deux et vérifier quelle moitié contiendrait le nombre souhaité, supprimer la partie non pertinente, puis répéter ce processus jusqu'à ce que nous atteignions l'élément souhaité. En fin de compte, nous trouverons (ou ne trouverons pas) le nombre après traitement du nombre log(n) d'éléments.

Voici un tableau qui résume la complexité temporelle du reste des collections.

Maintenant que nous avons un tableau montrant la complexité temporelle des collections populaires, nous pouvons répondre à la question pourquoi, parmi tant de collections, nous utilisons le plus souvent ArrayList , HashSet et HashMap .

C'est simplement qu'ils sont les plus efficaces pour la plupart des tâches :)