Überblick
In der Java -Sprache wird ein Datenerfassungsframework bereitgestellt, das einige abstrakte Datentypen wie List und Set definiert. Jeder abstrakte Datentyp verfügt über eine eigene spezifische Implementierung, und die zugrunde liegende Ebene verwendet verschiedene Implementierungsmethoden wie ArrayList und LinkedList.
Darüber hinaus bietet Java auch verschiedene Möglichkeiten, Datensätze zu durchqueren. Entwickler müssen die Merkmale, anwendbaren Anlässe und die Leistung in verschiedenen zugrunde liegenden Implementierungen klar verstehen. Lassen Sie uns diesen Inhalt im Folgenden im Folgenden ausführlich analysieren.
Wie werden Datenelemente im Speicher gespeichert?
Es gibt zwei Hauptspeichermethoden für Datenelemente im Speicher:
1. Sequentieller Speicher, Zufallszugriff (Direktzugriff):
Auf diese Weise werden benachbarte Datenelemente in benachbarten Speicheradressen gespeichert, und die gesamte Speicheradresse ist kontinuierlich. Die Speicheradresse kann basierend auf der Position des Elements direkt berechnet werden und direkt lesen. Die durchschnittliche Zeitkomplexität des Lesens eines Elements an einem bestimmten Ort ist O (1). Normalerweise haben nur Sätze, die basierend auf Arrays implementiert sind, diese Funktion. ArrayList ist in Java dargestellt.
2. Kettenspeicher, sequentieller Zugriff:
Auf diese Weise muss nicht jedes Datenelement in einer benachbarten Position im Speicher sein, und jedes Datenelement enthält die Speicheradresse seines nächsten Elements. Die Speicheradresse kann nicht direkt auf der Position des Elements berechnet werden, und die Elemente können nur in der Reihenfolge gelesen werden. Die durchschnittliche Zeitkomplexität des Lesens eines Elements an einem bestimmten Ort ist O (n). Es wird hauptsächlich durch verknüpfte Listen dargestellt.
LinkedList ist in Java dargestellt.
Was sind die in Java bereitgestellten Traversalmethoden?
1. traditionell für die Schleifenquelle, basierend auf dem Zähler:
Der Traverser selbst behält einen Zähler außerhalb der Sammlung bei, liest die Elemente an jeder Position nacheinander und stoppt, wenn das letzte Element gelesen wird. Die Hauptsache ist, das Element nach seiner Position zu lesen. Dies ist auch die primitivste Sammlungs -Traversal -Methode.
Die Schreibmethode lautet:
für (int i = 0; i <list.size (); i ++) {list.get (i);}2. Iterator Traversal, Iterator:
Iterator war ursprünglich ein OO -Designmuster, mit dem Hauptziel, die Eigenschaften verschiedener Datensätze zu blockieren und die Schnittstellen der Sammlung einheitlich zu durchqueren. Als OO -Sprache unterstützt Java natürlich den Iteratormodus in Sammlungen.
Die Schreibmethode lautet:
Iterator iterator = list.Iterator (); while (iterator.hasnext ()) {iterator.next ();}3. für die Ereignisschleife durchquert:
Iterator und Zähler, die explizit deklariert werden, werden blockiert.
Vorteile: Der Code ist präzise und nicht anfällig für Fehler.
Nachteile: Es können nur einfache Traverals durchgeführt werden, und Datensammlungen können während des Traversalprozesses nicht betrieben werden (löschen, ersetzen) werden.
Die Schreibmethode lautet:
für (Elementtype Element: Liste) {}Was ist das Implementierungsprinzip jeder Durchlaufmethode?
1. traditionell für die Schleifenquelle, basierend auf dem Zähler:
Der Traverser selbst behält einen Zähler außerhalb der Sammlung bei, liest die Elemente an jeder Position nacheinander und stoppt, wenn das letzte Element gelesen wird. Die Hauptsache ist, das Element nach seiner Position zu lesen.
2. Iterator Traversal, Iterator:
Jeder spezifische Implementierungsdatensatz muss im Allgemeinen einen entsprechenden Iterator bereitstellen. Im Vergleich zu traditionellen Schleifen verboten Iterator explizite Traversal -Zähler. Daher kann Iterator basierend auf der sequentiellen Speicherung von Sammlungen nach dem Standort direkt auf Daten zugreifen. Der Iterator basierend auf Kettenspeichersätzen und normale Implementierungen erfordern, dass der aktuelle Traversal -Standort gespeichert wird. Bewegen Sie dann den Zeiger nach der aktuellen Position nach vorne oder rückwärts.
3. für die Ereignisschleife durchquert:
Laut dem dekompilierten Bytecode kann festgestellt werden, dass für Foreach auch die Iterator -Methode verwendet wird, um sie zu implementieren, der Java -Compiler hat uns jedoch geholfen, diese Codes zu generieren.
Wie funktioniert jede Traversal -Methode für verschiedene Speichermethoden?
1. traditionell für die Schleifenquelle, basierend auf dem Zähler:
Da es auf der Position des Elements basiert, lesen Sie nach Position. Wir können also wissen, dass für die sequentielle Speicherung, da die durchschnittliche Zeitkomplexität von Leseelementen an einem bestimmten Ort O (1) beträgt, die durchschnittliche Zeitkomplexität des Durchquerens des gesamten Satzes O (n) beträgt. Für die Kettenspeicherung, da die durchschnittliche Zeitkomplexität von Leseelementen an einem bestimmten Ort O (N) beträgt, beträgt die durchschnittliche Zeitkomplexität des Durchquerens des gesamten Satzes O (N2) (das Quadrat von N).
ArrayList -Code von Position gelesen: direkt nach Elementposition lesen.
Transient Object [] elementData; public e get (int index) {rangecheck (index); return elementData (index);} e elementData (int index) {return (e) elementData [index];}LinkedList -Code von Position gelesen: Jedes Mal, wenn Sie vom 0. Element rückwärts lesen müssen. Tatsächlich hat es auch intern auch kleine Optimierungen gemacht.
transient int size = 0; transient node <e> zuerst; transient node <e> letztes; public e get (int index) {teckElementIndex (Index); Rückgabeknoten (Index) .Item;} Knoten <e> Knoten (int index) {if (Index <(Größe >> 1) {// Die erste Hälfte der Index -. <index; i ++) x = x.Next; return x;} else {// Die Abfrageposition befindet2. Iterator Traversal, Iterator:
Dann gibt es für Sammlungen vom Typ RandomAccess -Typ keine große Bedeutung. Stattdessen werden einige zusätzliche Vorgänge zusätzliche Laufzeit hinzufügen. Für die sequentielle Zugriffskollektion ist es jedoch von großer Bedeutung, da Iterator die aktuelle Traversalposition beibehält. Jedes Mal, wenn Sie durchqueren, müssen Sie nicht aus dem ersten Element der Sammlung nachschlagen. Bewegen Sie einfach den Zeiger nacheinander. Auf diese Weise wird die zeitliche Komplexität des Überfahrens des gesamten Satzes auf o (n) reduziert;
(Dies wird nur als Beispiel LinkedList verwendet.) Der Iterator von LinkedList wird intern implementiert, weshalb die aktuelle Durchquerungsposition beibehalten und dann den Zeiger umzugehen, um sich zu bewegen:
Code:
public e next () {techeforComodification (); if (! (Weiter == NULL)? letztes: next.prev; nextIndex-; return lastreturn.item;}3. für die Ereignisschleife durchquert:
Durch die Analyse des Java -Bytecode können wir feststellen, dass das interne Implementierungsprinzip von foreach auch über Iterator implementiert wird. Dieser Iterator wird jedoch vom Java -Compiler für uns generiert, sodass wir sie nicht manuell schreiben müssen. Da jedoch jedes Mal Typ -Conversion -Überprüfungen erforderlich sind, dauert es etwas länger als Iterator. Die Zeitkomplexität ist die gleiche wie die des Iterators.
Bytecode mit Iterator:
CODE: NEU # // Klasse Java/Util/ArrayListDUpinVokespecial # // Methode java/util/arrayList. java/util/iterator.next :() ljava/lang/objekt; popaload_invokeInterface #, // interfacemethod java/util/iterator.hasnext :() Zifne Return
Verwenden Sie die Bytecode von Foreach:
CODE: NEU # // Klasse Java/Util/ArrayListDUpinVokespecial # // Methode java/util/arrayList. java/util/iterator.next :() ljava/lang/objekt; checkcast # // class Loop/modelastore_aload_invokeInterface #, // interfacemethod java/util/iterator.hasnext :() Zifne Return
In welchen Gelegenheiten gilt jede durchquerende Methode?
1. traditionell für die Schleifenquelle, basierend auf dem Zähler:
Sequentielle Speicherung: hohe Leseleistung. Geeignet für die durchlaufende sequentielle Speichersammlungen.
Kettenspeicherung: Die Zeitkomplexität ist zu hoch und ist nicht zum Durchqueren von Sammlungen der Kettenspeicherung geeignet.
2. Iterator Traversal, Iterator:
Sequentielle Speicherung: Wenn Sie nicht zu viel Zeit interessieren, wird empfohlen, diese Methode auszuwählen. Schließlich ist der Code prägnanter und verhindert auch das Problem von Off-by-One.
Kettenspeicherung: Es ist von großer Bedeutung. Die durchschnittliche Zeitkomplexität wird auf O (n) reduziert, was sehr attraktiv ist, daher wird diese Durchlaufmethode empfohlen.
3. für die Ereignisschleife durchquert:
Foreach macht den Code nur prägnanter, hat jedoch einige Nachteile, dh er kann während des Durchquellenprozesses keine Datensammlungen (Löschen usw.) betreiben, sodass er in einigen Fällen nicht verwendet wird. Darüber hinaus wird es basierend auf Iterator implementiert, aber aufgrund des Problems der Typumwandlung ist es etwas langsamer als die direkte Verwendung von Iterator direkt. Glücklicherweise ist die Zeitkomplexität gleich. So wählen Sie die beiden oben genannten Methoden, um eine Kompromissauswahl zu treffen.
Was sind die besten Praktiken für Java?
Im Java -Datenerfassungs -Framework wird eine zufällige Schnittstelle bereitgestellt, die keine Methoden enthält, sondern nur ein Tag. Es wird normalerweise durch die Implementierung der Listenschnittstelle verwendet, um zu markieren, ob die Implementierung der Liste den Zufallszugriff unterstützt.
Ein Datensatz implementiert diese Schnittstelle, dh sie unterstützt den Zufallszugriff, und die durchschnittliche Zeitkomplexität der Leseelemente nach Ort ist O (1). Zum Beispiel ArrayList.
Wenn diese Schnittstelle nicht implementiert wird, bedeutet dies, dass der Zufallszugriff nicht unterstützt wird. Zum Beispiel LinkedList.
Es scheint also, dass JDK -Entwickler dieses Problem ebenfalls bemerkt haben. Die empfohlene Möglichkeit besteht darin, zuerst festzustellen, ob der Zufallszugriff unterstützt wird, dh Listinstance von RandomAccess.
Zum Beispiel:
if (listinstance von randomAccess) {// Verwenden Sie traditionell für die Schleifenquelle. } else {// Iterator oder foreach verwenden. }Die oben genannte Analyse der vom Editor vorgestellten Analyse der Java -Traversal -Sammelmethode (Implementierungsprinzip, Algorithmusleistung und anwendbaren Anlässe). Ich hoffe, es wird für alle hilfreich sein!