Aperçu
Dans la langue Java, un cadre de collecte de données est fourni, qui définit certains types de données abstraits tels que la liste et le jeu. Chaque type de données abstrait a sa propre implémentation spécifique, et la couche sous-jacente adopte différentes méthodes d'implémentation, telles que ArrayList et LinkedList.
De plus, Java fournit également plusieurs façons différentes de parcourir les ensembles de données. Les développeurs doivent clairement comprendre les caractéristiques, les occasions applicables et les performances dans différentes implémentations sous-jacentes. Analysons ce contenu en détail ci-dessous.
Comment les éléments de données sont-ils stockés en mémoire?
Il existe deux principales méthodes de stockage pour les éléments de données en mémoire:
1. Stockage séquentiel, accès aléatoire (accès direct):
De cette façon, les éléments de données adjacents sont stockés dans les adresses de mémoire adjacentes et toute l'adresse mémoire est continue. L'adresse mémoire peut être directement calculée en fonction de l'emplacement de l'élément et la lire directement. La complexité de temps moyenne de la lecture d'un élément à un emplacement spécifique est O (1). Normalement, seuls les ensembles implémentés en fonction des tableaux ont cette fonctionnalité. ArrayList est représenté en Java.
2. Stockage de la chaîne, accès séquentiel:
De cette façon, chaque élément de données n'est pas nécessaire d'être dans une position adjacente en mémoire, et chaque élément de données contient l'adresse mémoire de son prochain élément. L'adresse mémoire ne peut pas être calculée directement sur la base de l'emplacement de l'élément, et les éléments ne peuvent être lus que dans l'ordre. La complexité de temps moyenne de la lecture d'un élément à un emplacement spécifique est O (n). Il est principalement représenté par des listes liées.
LinkedList est représenté dans Java.
Quelles sont les méthodes de traversée fournies en Java?
1. Traditionnel pour la traversée de boucle, basée sur le compteur:
Le Traverser lui-même maintient un comptoir à l'extérieur de la collection, puis lit les éléments à chaque position en séquence, et s'arrête lorsque le dernier élément est lu. L'essentiel est de lire l'élément selon sa position. Il s'agit également de la méthode de traversée de collecte la plus primitive.
La méthode d'écriture est:
pour (int i = 0; i <list.size (); i ++) {list.get (i);}2. Traversion itérateur, itérateur:
Iterator était à l'origine un modèle de conception OO, avec son objectif principal étant de bloquer les caractéristiques de différents ensembles de données et de traverser les interfaces de la collection uniformément. En tant que langue OO, Java prend naturellement le support du mode itérateur dans les collections.
La méthode d'écriture est:
Iterator iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Traversion en boucle foreach:
L'itérateur et les compteurs déclarés explicitement sont bloqués.
Avantages: le code est concis et non sujet aux erreurs.
Inconvénients: seules des traversées simples peuvent être effectuées et les collections de données ne peuvent pas être utilisées (supprimer, remplacer) pendant le processus de traversée.
La méthode d'écriture est:
pour (élément elementType: list) {}Quel est le principe de mise en œuvre de chaque méthode de traversée?
1. Traditionnel pour la traversée de boucle, basée sur le compteur:
Le Traverser lui-même maintient un comptoir à l'extérieur de la collection, puis lit les éléments à chaque position en séquence, et s'arrête lorsque le dernier élément est lu. L'essentiel est de lire l'élément selon sa position.
2. Traversion itérateur, itérateur:
Chaque ensemble de données d'implémentation spécifique doit généralement fournir un itérateur correspondant. Par rapport à la traditionnelle pour les boucles, l'itérateur interdit les compteurs de traverse explicites. Par conséquent, l'itérateur basé sur le stockage séquentiel des collections peut accéder directement aux données par emplacement. L'itérateur en fonction des ensembles de stockage de chaînes, les implémentations normales nécessitent que l'emplacement de traversée actuel soit enregistré. Déplacez ensuite le pointeur vers l'avant ou vers l'arrière en fonction de la position actuelle.
3. Traversion en boucle foreach:
Selon le bytecode décompilé, il peut être constaté que ForEach utilise également la méthode Itérator pour l'implémenter, mais le compilateur Java nous a aidés à générer ces codes.
Comment chaque méthode de traversée fonctionne-t-elle pour différentes méthodes de stockage?
1. Traditionnel pour la traversée de boucle, basée sur le compteur:
Parce qu'il est basé sur la position de l'élément, lisez par position. Nous pouvons donc savoir que pour le stockage séquentiel, car la complexité temporelle moyenne des éléments de lecture à un emplacement particulier est O (1), la complexité temporelle moyenne de la traversée de l'ensemble entier est O (n). Pour le stockage de la chaîne, car la complexité temporelle moyenne des éléments de lecture à un emplacement spécifique est O (n), la complexité temporelle moyenne de la traversée de l'ensemble entier est O (N2) (le carré de n).
Code ArrayList Lire par position: Lire directement par position d'élément.
objet transitoire [] elementData; public e get (int index) {rangecheck (index); return elementData (index);} e elementData (int index) {return (e) elementData [index];}Code LinkedList Lire par position: Chaque fois que vous devez lire à l'envers à partir du 0ème élément. En fait, il a également fait de petites optimisations en interne.
transitoire int size = 0; nœud transitoire <e> d'abord; nœud transitoire <e> dernier; public e get (int index) {checkElementIndex (index); retour nœud (index) .item;} nœud <e> nœud (int index) {if (index <(size> 1)) {// la position de requête est dans la première moitié de la liste liée, et recherchez le nœud <e> pour (pour int i; pour le 0; <index; i ++) x = x.next; return x;} else {// La position de requête est dans la seconde moitié de la liste liée, et recherchez le nœud <e> x = dernier; pour (int i = taille - 1; i> index; i -) x = x.prev; return x;}}2. Traversion itérateur, itérateur:
Ensuite, pour les collections de type à accès aléatoire, il n'y a pas beaucoup de sens. Au lieu de cela, certaines opérations supplémentaires ajouteront un temps d'exécution supplémentaire. Cependant, il est d'une grande importance pour la collection d'accès séquentiel, car Iterator conserve la position de traversée actuelle, donc chaque fois que vous traversez, vous n'avez pas besoin de commencer à rechercher le premier élément de la collection. Déplacez simplement le pointeur un par un. De cette façon, la complexité du temps de traverser l'ensemble entier est réduite à O (n);
(Ceci est uniquement utilisé LinkedList comme exemple) L'itérateur de LinkedList est implémenté en interne, qui est de maintenir la position de traversée actuelle, puis de faire fonctionner le pointeur pour se déplacer:
Code:
public e next () {checkForComodification (); if (! Hasnext ()) lance un nouveau nosuchementElementException (); lasTreturned = next; next = next.next; nextIndex ++; return lastreTurned.Item;} public e précédemment () {checkForComodification (); if (! hasprevious () throw new New NosucheLelementException (); lastreTrEner = Next = Next = thorp == null)? dernier: next.prev; nextIndex -; return lastreturned.item;}3. Traversion en boucle foreach:
En analysant le bytecode Java, nous pouvons voir que le principe de mise en œuvre interne de Foreach est également mis en œuvre via Iterator, mais cet itérateur est généré par le compilateur Java pour nous, nous n'avons donc pas besoin de l'écrire manuellement. Cependant, parce que les vérifications de conversion de type sont nécessaires à chaque fois, cela prend un peu plus de temps que l'itérateur. La complexité du temps est la même que celle de l'itérateur.
Bytecode utilisant iterator:
Code: Nouveau # // Classe java / util / arrayListDupInvokeSpecial # // Méthode java / util / arrayList. "<Init>" :() Vastore_Aload_invokeInterface #, // interfacethod java / util / list.iterator :() ljava / util / iterator; store_goto aload_invofoketer InterfaceMethod java / util / iterator.next :() ljava / lang / objet; popaload_invokeinterface #, // interfaceMethod java / util / iterator.hasnext :() zifne return
Utilisez Bytecode de ForEach:
Code: Nouveau # // Classe java / util / arrayListDupInvokeSpecial # // Méthode java / util / arrayList. "<Init>" :() Vastore_Aload_invokeInterface #, // interfacethod java / util / list.iterator :() ljava / util / iterator; store_goto aload_invofoketer InterfaceMethod Java / util / iterator.next :() ljava / lang / objet; Checkcast # // LOOP CLASS / MODELASTORE_ALOAD_INVOKEInterface #, // interfaceMethod Java / util / iterator.hasnext :() RETOUR RETOUR
Dans quelles occasions s'appliquent chaque méthode de traversée?
1. Traditionnel pour la traversée de boucle, basée sur le compteur:
Stockage séquentiel: performances de lecture élevée. Convient pour les collections de stockage séquentiels de traversée.
Stockage de la chaîne: La complexité temporelle est trop élevée et ne convient pas pour traverser les collections de stockage de chaînes.
2. Traversion itérateur, itérateur:
Stockage séquentiel: si vous ne vous souciez pas trop du temps, il est recommandé de choisir cette méthode. Après tout, le code est plus concis et empêche également le problème du red-by un.
Stockage de la chaîne: il est d'une grande importance. La complexité du temps moyenne est réduite à O (n), ce qui est assez attrayant, donc cette méthode de traversée est recommandée.
3. Traversion en boucle foreach:
ForEach ne fait que le code plus concis, mais il présente certains inconvénients, c'est-à-dire qu'il ne peut pas faire fonctionner les collections de données (délétion, etc.) pendant le processus de traversée, il n'est donc pas utilisé à certaines occasions. De plus, il est mis en œuvre sur la base d'Iterator, mais en raison du problème de la conversion de type, il sera un peu plus lent que d'utiliser directement Iterator. Heureusement, la complexité du temps est la même. Alors, comment choisir, reportez-vous aux deux méthodes ci-dessus pour faire un choix de compromis.
Quelles sont les meilleures pratiques pour Java?
Dans le cadre de collecte de données Java, une interface aléatoire est fournie, qui n'a pas de méthodes, juste une balise. Il est généralement utilisé par l'implémentation de l'interface de liste pour marquer si l'implémentation de la liste prend en charge l'accès aléatoire.
Un ensemble de données implémente cette interface, ce qui signifie qu'il prend en charge l'accès aléatoire, et la complexité de temps moyenne des éléments de lecture par emplacement est O (1). Par exemple, ArrayList.
Si cette interface n'est pas implémentée, cela signifie que l'accès aléatoire n'est pas pris en charge. Par exemple, LinkedList.
Il semble donc que les développeurs JDK aient également remarqué ce problème. Le moyen recommandé est de déterminer d'abord si l'accès aléatoire est pris en charge, c'est-à-dire la liste des instances de RandomAccess.
Par exemple:
if (list instanceof randomaccess) {// Utilisez traditionnel pour la traversée de boucle. } else {// Utilisez iterator ou foreach. }Ce qui précède est l'analyse de la méthode de collecte de traversée Java (principe de mise en œuvre, des performances d'algorithme et des occasions applicables) introduites par l'éditeur. J'espère que ce sera utile à tous!