Préface
Grâce à cet article, vous pouvez comprendre les cinq méthodes de traversée de la liste, leurs performances respectives et la mise en œuvre de FOREACH et ITERATOR, et approfondir votre compréhension des implémentations ArrayList et LinkedList. Jetons un coup d'œil ci-dessous.
1. Cinq façons de parcourir la liste
1. Pour chaque boucle
List <Integer> list = new ArrayList <Neger> (); pour (Integer j: list) {// Utilisez J}2. Itérateur de collecte d'appels d'affichage
List <Integer> list = new ArrayList <Integer> (); for (iterator <nteger> iterator = list.iterator (); iterator.hasnext ();) {iterator.next ();}ou
List <Integer> list = new ArrayList <Neger> (); iterator <Integer> iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Boucle incrémentielle de l'indice, la condition de terminaison consiste à comparer et à juger chaque fois que la fonction de taille () est appelée
List <Integer> list = new ArrayList <Integer> (); pour (int j = 0; j <list.size (); j ++) {list.get (j);}4. Cycle incrémentiel de l'indice, comparaison et jugement des variables temporaires dont les conditions de terminaison sont une somme égale à la taille ()
List <Integer> list = new ArrayList <Neger> (); int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j);}5. Cycle de déclin des indices
List <Integer> list = new ArrayList <Neger> (); for (int j = list.size () - 1; j> = 0; j--) {list.get (j);}Test de performance et comparaison de cinq méthodes de traction de liste
Ce qui suit est le code de test de performances, qui étend le temps consacré à diverses méthodes de traversée d'ArrayList et de liste liée de différents ordres de grandeur.
Package cn.trinea.java.test; import java.text.decimalformat; import java.util.arraylist; import java.util.calendar; import java.util.itreator; import java.util.linkedlist; 2013-10-28 * / classe publique javalooptest {public static void main (String [] args) {System.out.print ("Comparez les performances de boucle de ArrayList"); LoopListCompare (getArraylists (10000, 100000, 100000, 9000000)); System.out.print ("/ r / n / r / ncompare Loop Performance of LinkedList"); LoopListCompare (GetLinkedlists (100, 1000, 10000, 10000)); } public static list <Integer> [] getArrayLists (int ... sizearray) {list <Integer> [] listArray = new ArrayList [sizEarray.length]; for (int i = 0; i <listArray.length; i ++) {int size = sizEarray [i]; List <Integer> list = new ArrayList <Integer> (); pour (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return listArray; } public static list <Integer> [] getLinkEdLists (int ... sizearray) {list <Integer> [] listArray = new LinkedList [sizearray.length]; for (int i = 0; i <listArray.length; i ++) {int size = sizEarray [i]; List <Integer> list = new LinkedList <Integer> (); pour (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return listArray; } public static void looplistCompare (list <Integer> ... listArray) {printheader (listArray); Long Startime, Fintime; // type 1 pour (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmilis (); for (Integer j: list) {// Utiliser J} EndTime = Calendar.getInstance (). GetTimeInMillis (); printCosttime (i, listArray.length, "pour chacun", Endtime - starttime); } // type 2 pour (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmilis (); // iterator <Integer> iterator = list.iterator (); // while (iterator.hasnext ()) {// iterator.next (); //} pour (Iterator <Integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next (); } endtime = calendar.getInstance (). getTimeInmillis (); printCosttime (i, listArray.length, "For Iterator", Endtime - starttime); } // type 3 pour (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmilis (); pour (int j = 0; j <list.size (); j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCosttime (i, listArray.length, "For list.size ()", endtime - starttime); } // type 4 pour (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmilis (); int size = list.size (); pour (int j = 0; j <size; j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCosttime (i, listArray.length, "For size = list.size ()", EndTime - starttime); } // type 5 pour (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). getTimeInmilis (); pour (int j = list.size () - 1; j> = 0; j--) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printCosttime (i, listArray.length, "pour J--", Endtime - starttime); }} static int first_column_length = 23, autre_column_length = 12, total_column_length = 71; static final decimalformat comma_format = new decimalformat ("#, ###"); Public static void printheader (list <Integer> ... listArray) {printrowdivider (); for (int i = 0; i <listArray.length; i ++) {if (i == 0) {StringBuilder sb = new StringBuilder (). APPEND ("List Size"); while (sb.length () <premier_column_length) {sb.append (");} system.out.print (sb);} stringBuilder sb = new StringBuilder (). APPEND (" | ") .APPEND (Comma_format.Format (listArray [i] .size ()); while (sb.Length SB.APPELLAGE (");} System.out.print (SB); (sb.length () <total_column_length) {sb.append ("-");} System.out.println (sb); <Premier_column_length) {sb.append (""); System.out.print (SB); }}} PS: Si l'exécution de l'exécution, une exception in thread “main” java.lang.OutOfMemoryError: Java heap space , veuillez réduire la taille de list size dans main .
La fonction getArrayLists renverra une liste Array avec différentes size , et la fonction getLinkedLists renverra une liste liée à différentes size .
loopListCompare utilisera la méthode de traversée ci-dessus 1-5 pour parcourir la liste dans chaque tableau de liste (y compris les listes de différentes tailles).
La fonction commençant par print est une fonction d'assistance de sortie.
L'environnement de test est Windows 7 32 bits Système 3.2G Mémoire de CPU 4G Dual-Core, Java 7, Eclipse -XMS512M -XMX512M
Les résultats des tests finaux sont les suivants:
Comparez les performances de boucle de ArrayList ----------------------------------------------------------------------- Taille de la liste | 10 000 | 100 000 | 1 000 000 | 10 000 000 ------------------------------------------------------------------- Pour chacun | 1 ms | 3 ms | 14 ms | 152 ms ------------------------------------------------------------------- Pour itérateur | 0 ms | 1 ms | 12 ms | 114 MS ------------------------------------------------------------------- Pour List.Size () | 1 ms | 1 ms | 13 ms | 128 ms ------------------------------------------------------------------- Pour taille = list.size () | 0 ms | 0 ms | 6 ms | 62 ms ------------------------------------------------------------------- Pour J-- | 0 ms | 1 ms | 6 ms | 63 MS ----------------------------------------------------------------------- Comparez les performances de boucle de LinkedList ------------------------------------------------------------------- Taille de la liste | 100 | 1 000 | 10 000 | 100 000 ------------------------------------------------------------------- Pour chacun | 0 ms | 1 ms | 1 ms | 2 ms ------------------------------------------------------------------- Pour itérateur | 0 ms | 0 ms | 0 ms | 2 ms ------------------------------------------------------------------- Pour List.Size () | 0 ms | 1 ms | 73 MS | 7972 MS ------------------------------------------------------------------- Pour taille = list.size () | 0 ms | 0 ms | 67 ms | 8216 MS ------------------------------------------------------------------- Pour J-- | 0 ms | 1 ms | 67 ms | 8277 ms ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Le premier tableau est le résultat de comparaison d'ArrayList, et le deuxième tableau est le résultat de comparaison de LinkedList.
La direction horizontale du tableau est la consommation temporelle de traversée de différentes tailles de listes dans la même méthode de traversée, et la direction verticale est la consommation de temps de traversée de différentes méthodes de traversée de la même liste.
PS: Étant donné que la première traversée de la liste prendra un peu plus de temps, les résultats de for each sont légèrement déviés. Si vous échangez plusieurs types dans le code de test, vous constaterez que for each fois, il est proche de celui de for iterator .
Analyse des résultats des tests de performance de la méthode de traversée
1. Introduction de Forach
Forach est une structure de boucle très puissante introduite par Java SE5.0. for (Integer j : list) doit être lu for each int in list .
for (Integer j : list) l'implémentation est presque équivalente à
Iterator <Integer> iterator = list.iterator (); while (iterator.hasnext ()) {entier j = iterator.next ();}Le code foreach est simple à écrire, et il n'est pas nécessaire de se soucier de la valeur initiale, de fin de la valeur et de la transfrontsion, il n'est donc pas facile de faire des erreurs.
2. Analyse des résultats de la méthode de traversée ArrayList
un. Avant que la taille de la liste Array ne soit de 100 000, la consommation temporelle des cinq méthodes de traversée était presque la même
né Après 100 000, les quatrième et cinquième méthodes de traversée sont plus rapides que les trois premières, la méthode GET est meilleure que la méthode Iterator, et
int size = list.size (); pour (int j = 0; j <size; j ++) {list.get (j);} Le remplacement de list.size() par une taille de variable temporaire est de meilleures performances. Jetons un coup d'œil à la mise en œuvre d' Iterator et get des méthodes dans ArrayList
classe privée ITR implémente Iterator <E> {int Cursor; // Index de l'élément suivant pour retourner int lastret = -1; // Index du dernier élément renvoyé; -1 si aucun tel int attendModCount = modCount; public boolean hasnext () {return Cursor! = size; } @SuppressWarnings ("Unchecked") public e suivant () {checkForComodification (); int i = curseur; if (i> = size) lancez new nosuchementElementException (); Object [] elementData = arrayList.this.ElementData; if (i> = elementData.Length) lancez de nouveaux mododification ConcurrentException (); curseur = i + 1; return (e) elementData [lastret = i]; }…} Public e get (int index) {rangeCheck (index); return elementData (index);} À partir de cela, nous pouvons voir que les next fonctions de get et Iterator obtiennent également des éléments en positionnant directement les données, mais il n'y a que quelques jugements supplémentaires.
c. D'après ce qui précède, nous pouvons voir que même dans la liste de billets de dizaines de millions, la différence entre les différentes méthodes de traversée n'est que d'environ 50 ms, et le temps est presque égal à environ 100 000. Compte tenu des avantages de Foreach, nous pouvons choisir d'utiliser la méthode simple de Foreach Foreach pour la traversée.
3. Analyse des résultats de la méthode de traversée liée
un. Lorsque la taille de LinkedList est proche de 10 000, la méthode get et la méthode Iterator sont déjà environ deux ordres de grandeur différents. Lorsque le 100 000, les performances de Iterator sont bien meilleures que la méthode GET.
Jetons un coup d'œil à la mise en œuvre des itérateurs et get des méthodes dans LinkedList
classe privée listitR implémente ListIterator <E> {nœud privé <e> lastreTurned = null; Node privé <e> Suivant; private int nextIndex; private int attendModCount = modCount; ListItrTr (int index) {// Assert IsPositionIndex (index); suivant = (index == taille)? null: nœud (index); NextIndex = index; } public boolean hasnext () {return nextIndex <size; } public e suivant () {checkForComodification (); if (! Hasnext ()) lance un nouveau nosuchementElementException (); lastreTurned = Suivant; Next = next.next; NextIndex ++; retourner lastreturned.item; }…} Public e get (int index) {checkElementIndex (index); Node de retour (index) .item;} / ** * renvoie le nœud (non nulle) à l'indice d'élément spécifié. * / Nœud <e> node (int index) {// affirmer iseElementIndex (index); if (index <(size >> 1)) {node <e> x = premier; pour (int i = 0; i <index; i ++) x = x.next; retour x; } else {node <e> x = dernier; pour (int i = size - 1; i> index; i--) x = x.prev; retour x; }} À partir du code ci-dessus, nous pouvons voir que la fonction next de l'itérateur LinkedList Linked obtient rapidement l'élément suivant via le pointeur suivant et revient. La méthode GET traversera le début jusqu'à l'indice d'index, et trouvera un élément avec une complexité temporelle de O (n), et la complexité temporelle de la traversée atteindra O (N2).
Par conséquent, il est recommandé d'utiliser ForEach pour la traversée de LinkedList pour éviter d'utiliser get .
4. Analyse comparative des résultats de l'arraylist et des méthodes de traversée LinkedList
D'après l'ordre de grandeur ci-dessus, il s'agit également d'une traversée de boucle FOREAK, et le temps d'ArrayList et de LinkedList est similaire. Si vous modifiez légèrement cet exemple et augmentez list size vous constaterez que les deux sont essentiellement du même ordre de grandeur.
Cependant, la complexité temporelle de ArrayList get est O (1), tandis que la complexité temporelle de la fonction LinkedList Get est O (n).
Si vous considérez la consommation d'espace, il est recommandé de choisir d'abord ArrayList. Pour l'insertion et la suppression individuelles, vous pouvez utiliser LinkedList.
Résumé de la conclusion
Grâce à l'analyse ci-dessus, nous pouvons essentiellement résumer:
Résumer
Ce qui précède est l'intégralité du contenu de cet article. J'espère que le contenu de cet article sera utile à tout le monde lors de l'apprentissage ou de l'utilisation de Java. Si vous avez des questions, vous pouvez laisser un message pour communiquer.