Vorwort
In diesem Artikel können Sie die fünf Traversal -Methoden der Liste, ihre jeweiligen Leistungen und die Implementierung von Foreach und Iterator verstehen und Ihr Verständnis von ArrayList- und LinkedList -Implementierungen vertiefen. Schauen wir uns unten einen Blick zusammen.
1. Fünf Möglichkeiten zur durchqueren Liste
1. Für jede Schleife
List <Ganzzahl> list = new ArrayList <Integer> (); for (Integer j: list) {// J} verwenden2. Iterator für Anrufsammlungsanlagen anzeigen
List <Ganzzahl> list = new ArrayList <Ganzzahl> (); für (Iterator <GanzEger> iterator = list.iterator (); iterator.hasnext ();) {iterator.next ();}oder
List <Ganzzahl> list = new ArrayList <Ganzzahl> (); Iterator <Grapier> iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Die inkrementelle Schleife des Indexs ist die Kündigungsbedingung zu vergleichen und zu beurteilen, wenn die size () -Funktion aufgerufen wird
List <Ganzzahl> list = new ArrayList <Ganzzahl> (); für (int j = 0; j <list.size (); j ++) {list.get (j);}4. Inkrementeller Zyklus von Index, Vergleich und Beurteilung von vorübergehenden Variablen, deren Beendungsbedingungen gleich groß sind ()
List <Gearner> list = new ArrayList <Integer> (); int size = list.size (); für (int j = 0; j <size; j ++) {list.get (j);}5. Abnahmeverringerung des Zyklus
List <Integer> list = new ArrayList <GanzEger> (); for (int j = list.size ()-1; j> = 0; j-) {list.get (j);}Leistungstest und Vergleich von fünf Durchlaufmethoden der Liste
Das Folgende ist der Performance -Testcode, der die Zeit für verschiedene Traversal -Methoden von ArrayList und Linkedlist mit verschiedenen Größenordnungen ausgibt.
Paket cn.trinea.java.test; import java.text.decimalformat; import java.util.arraylist; import java.util.calendar; import Java.util.iterator; import Java.util.linkedlist; Import Java.util.list; 2013-10-28 */öffentliche Klasse Javalooptest {public static void main (String [] args) {System.out.print ("Schleifenleistung von ArrayList vergleichen"); LoopListCompare (GetArraynlisten (10000, 100000, 100000, 9000000)); System.out.print ("/r/r/r/ncompare Loop -Leistung der LinkedList"); LoopListCompare (getLinkedLists (100, 1000, 10000, 10000)); } public static list <Integer> [] GetArraynlisten (int ... Sizearray) {list <Integer> [] listArray = new ArrayList [Sizearray.length]; für (int i = 0; i <listArray.length; i ++) {int size = sizearray [i]; List <Ganzzahl> list = new ArrayList <Ganzzahl> (); für (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]; für (int i = 0; i <listArray.length; i ++) {int size = sizearray [i]; List <Ganzzahl> list = new LinkedList <Ganzzahl> (); für (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return listArray; } public static void LoopListCompare (List <GanzEger> ... ListArray) {PrinTheader (ListArray); lange Startzeit, Endzeit; // Typ 1 für (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). GetTimeInmillis (); für (Integer J: Liste) {// Verwenden Sie J} endTime = calendar.getInstance (). GetTimeInmillis (); printCosttime (i, listArray.length, "für jedes", Endtime - StartTime); } // Typ 2 für (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). GetTimeInmillis (); // Iterator <Ganzzahl> iterator = list.Iterator (); // while (iterator.hasnext ()) {// iterator.next (); //} für (Iterator <GanzEger> iterator = list.iterator (); iterator.hasnext ();) {iterator.next (); } endTime = calendar.getInstance (). GetTimeInmillis (); printCosttime (i, listArray.length, "for iterator", Endtime - StartTime); } // Typ 3 für (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). GetTimeInmillis (); für (int j = 0; j <list.size (); j ++) {list.get (j); } endTime = calendar.getInstance (). GetTimeInmillis (); printCostTime (i, listArray.length, "für list.size ()", Endime - StartTime); } // Typ 4 für (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). GetTimeInmillis (); int size = list.size (); für (int j = 0; j <size; j ++) {list.get (j); } endTime = calendar.getInstance (). GetTimeInmillis (); printCostTime (i, listArray.length, "für size = list.size ()", Endime - StartTime); } // Typ 5 für (int i = 0; i <listArray.length; i ++) {list <Integer> list = listArray [i]; startTime = calendar.getInstance (). GetTimeInmillis (); für (int j = list.size ()-1; j> = 0; j--) {list.get (j); } endTime = calendar.getInstance (). GetTimeInmillis (); printCosttime (i, listArray.length, "für J-", Endime-StartTime); }} static int first_column_length = 23, other_column_length = 12, Total_column_length = 71; statische endgültige Dezimalformat comma_format = new DecimalFormat ("#, ###"); public static void PrinTheader (Liste <Ganzzahl> ... ListArray) {PrinTrowDivider (); für (int i = 0; i <listArray.length; i ++) {if (i == 0) {stringBuilder sb = new StringBuilder (). append ("Listgröße"); while (sb.length () <first_column_length) {sb.append (");} system.out.print (sb);} StringBuilder sb = new StringBuilder (). append (" | ") .Append (comma_format.format (listarray [i] .Size ()); SB.Append (""); (sb.length () <Total_Column_Length) {SB.Append ("-"); First_Column_Length) {SB.Append (""); if (i == Größe - 1) {PrintrowDivider (); }}} PS: Wenn der Lauf eine Ausnahme in thread “main” java.lang.OutOfMemoryError: Java heap space , reduzieren Sie bitte die Größe list size in main .
Die Funktion getArrayLists gibt eine ArrayList mit unterschiedlichen size zurück, und die Funktion getLinkedLists gibt eine LinkedList mit unterschiedlichen size zurück.
loopListCompare -Funktion verwendet die oben genannte Traversal-Methode 1-5, um die Liste in jedem Listen-Array (einschließlich Listen verschiedener Größen) zu durchqueren.
Die Funktion, die mit print beginnt, ist eine Ausgangshelferfunktion.
Die Testumgebung ist Windows 7 32 -Bit -System 3.2G Dual -Core -CPU 4G -Speicher, Java 7, Eclipse -xms512m -xmx512m
Die endgültigen Testergebnisse sind wie folgt:
Vergleichen Sie die Schleifenleistung von ArrayList ------------------------------------------------------------------- Listgröße | 10.000 | 100.000 | 1.000.000 | 10.000.000 ---------------------------------------------------------------------------- 1 ms | 3 ms | 14 ms | 152 ms --------------------------------------------------------------------------- für Iterator | 0 ms | 1 ms | 12 ms | 114 ms --------------------------------------------------------------------------------------- für die Liste.size () | 1 ms | 1 ms | 13 ms | 128 ms ------------------------------------------------------------------------------- für size = list.size () | 0 ms | 0 ms | 6 ms | 62 ms ----------------------------------------------------------------------------------- für J- | 0 ms | 1 ms | 6 ms | 63 ms -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 100 | 1.000 | 10.000 | 100.000 ---------------------------------------------------------------------------- 0 ms | 1 ms | 1 ms | 2 MS ----------------------------------------------------------------------- für Iterator | 0 ms | 0 ms | 0 ms | 2 ms ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- für list.size () | 0 ms | 1 ms | 73 ms | 7972 ms ------------------------------------------------------------------- für size = list.size () | 0 ms | 0 ms | 67 ms | 8216 MS ------------------------------------------------------------------- für J- | 0 ms | 1 ms | 67 ms | 8277 MS ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Die erste Tabelle ist das Vergleichsergebnis von ArrayList, und die zweite Tabelle ist das Vergleichsergebnis von LinkedList.
Die horizontale Richtung der Tabelle ist der zeitliche Verbrauch von Durchlauf verschiedener Größen von Listen in derselben Traversalmethode, und die vertikale Richtung ist der zeitliche Verbrauch von Traversal verschiedener Traversalmethoden derselben Liste.
PS: Da der erste Traversal der Liste etwas mehr Zeit in Anspruch nimmt, sind die Ergebnisse for each leicht abgewichen. Wenn Sie mehrere Typen im Testcode austauschen, werden Sie feststellen, dass for each Mal die for iterator in der Nähe des Iterators liegt.
Analyse der Leistungstestergebnisse der Traversalmethode
1. für die Einführung
Foreach ist eine sehr mächtige Schleifenstruktur, die von Java SE5.0 eingeführt wird. for (Integer j : list) sollte for each int in list gelesen werden.
for (Integer j : list) ist die Implementierung fast gleichwertig zu
Iterator <Ganzzahl> iterator = list.Iterator (); while (iterator.hasnext ()) {Integer j = iterator.next ();}Der Foreach-Code ist einfach zu schreiben, und es besteht keine Notwendigkeit, sich um den ursprünglichen Wert, den Kündigungswert und grenzüberschreitende zu kümmern, sodass es nicht einfach ist, Fehler zu machen.
2. Analyse der Ergebnisse der ArrayList -Traversalmethode
A. Bevor die ArrayList -Größe 100.000 betrug
B. Nach 100.000 sind die vierten und fünften Traversalmethoden schneller als die ersten drei, die GET -Methode ist besser als die Iteratormethode, und
int size = list.size (); für (int j = 0; j <size; j ++) {list.get (j);} Das Ersetzen list.size() mit vorübergehender variabler Größe ist eine bessere Leistung. Schauen wir uns die Implementierung des Iterator an und get Methoden in ArrayList ab
Private Klasse ITR implementiert Iterator <E> {int Cursor; // Index des nächsten Elements zur Rückgabe von int lastret = -1; // Index des letzten Elements zurückgegeben; -1 Wenn kein solcher int erweitertmodcount = modcount; public boolean hasNext () {return cursor! = size; } @SuppressWarnings ("deaktiviert") public e next () {checkforComodification (); int i = cursor; if (i> = size) werfen neue noSuchelementException (); Object [] elementData = arrayList.this.ElementData; if (i> = elementData.length) werfen neue ConcurrentModificationException (); Cursor = i + 1; return (e) elementData [lastret = i]; }…} Public e get (int index) {rangecheck (index); returnelementData (Index);} Daraus können wir sehen, dass die next Funktionen von get und Iterator auch Elemente erhalten, indem sie Daten direkt positionieren, aber es gibt nur wenige weitere Urteile.
C. Aus diesem Grund können wir sehen, dass selbst in der Arraylist von zehn Millionen Menschen der Unterschied zwischen den verschiedenen Traversalmethoden nur etwa 50 ms beträgt und die Zeit fast 100.000 entspricht. In Anbetracht der Vorteile von foreach können wir die einfache Methode von foreach foreach für durchqueren verwenden.
3.. Analyse der Ergebnisse der LinkedList -Traversalmethode
A. Wenn die Größe der LinkedList nahe bei 10.000 liegt, unterliegt die get -Methode und Iterator -Methode bereits etwa zwei Größenordnungen. Bei 100.000 ist die Leistung der Iterator weitaus besser als die GET -Methode.
Schauen wir uns die Implementierung von Iteratoren an und get Methoden in LinkedList
private class listitr implements listIterator <e> {private Knoten <E> lastreturned = null; private Knoten <e> als nächstes; Privat int NextIndex; private int erweitertmodcount = modcount; Listitr (int index) {// ispositionIndex (index) geltend machen; Weiter = (index == Größe)? NULL: Knoten (Index); nextIndex = index; } public boolean hasNext () {return NextIndex <Größe; } public e next () {checkforComodification (); if (! hasNext ()) werfen neue noSuchelementException (); lastreturned = Weiter; next = next.next; NextIndex ++; return lastreturned.item; }…} Public e get (int index) {checkElementIndex (index); Rückgabeknoten (Index) .Item;} /*** Gibt den (Nicht-Null-) Knoten am angegebenen Elementindex zurück. */Node <e> node (int index) {// isSelementIndex (index); if (index <(Größe >> 1)) {Knoten <e> x = zuerst; für (int i = 0; i <index; i ++) x = x.Next; Rückkehr x; } else {node <e> x = last; für (int i = Größe-1; i> Index; i--) x = x.prev; Rückkehr x; }} Aus dem obigen Code können wir sehen, dass die next Funktion des LinkedList -Iterators das nächste Element durch den nächsten Zeiger und zurückgibt. Die GET -Methode durchquert von Anfang an bis zum Index -Index und findet ein Element mit einer zeitlichen Komplexität von O (n), und die zeitliche Komplexität des Traverses erreicht O (N2).
Daher wird empfohlen, für die Durchführung von LinkedList für die Verwendung von get zu verwenden.
4. Vergleichende Analyse der Ergebnisse von ArrayList und LinkedList Traversal -Methoden
Aus der oben genannten Größenordnung ist es auch eine Foreach -Loop -Traversal, und die Zeit von ArrayList und LinkedList ist ähnlich. Wenn Sie dieses Beispiel geringfügig ändern und list size werden Sie feststellen, dass sich die beiden im Grunde genommen in der gleichen Größenordnung befinden.
Die zeitliche Komplexität ArrayList get -Funktion ist jedoch O (1), während die zeitliche Komplexität der LinkedList -Funktion O (n) ist.
Wenn Sie den Raumverbrauch in Betracht ziehen, wird empfohlen, zuerst ArrayList zu wählen. Für die individuelle Einführung und Löschung können Sie LinkedList verwenden.
Fazit Zusammenfassung
Durch die obige Analyse können wir grundsätzlich zusammenfassen:
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, der Inhalt dieses Artikels wird für alle hilfreich sein, wenn sie Java lernen oder verwenden. Wenn Sie Fragen haben, können Sie eine Nachricht zur Kommunikation überlassen.