[Einführung in die Java-Datenstruktur] Erstellen Sie Ihre eigene schnelle ArrayDeque für den primitiven Typ

Bei der Implementierung der Suche nach Breitenpriorität und der Suche nach Tiefenpriorität in "Java" gibt es meines Erachtens viele Leute, die dies implementieren, indem sie die Scheitelpunktnummer in "ArrayDeque " speichern. Diese "ArrayDeque ", Da es "Integer" speichert, eine Wrapper-Klasse von "int", tritt das automatische Boxen / Entpacken häufig auf und die Geschwindigkeit ist nicht gut. Daher möchte ich dieses Mal einfach eine dedizierte Hochgeschwindigkeits-Deque (IntArrayDeque) implementieren. Sie wird empfohlen, da sie für ihre einfache Implementierung sehr effektiv ist.

Die minimal erforderlichen Funktionen zum Implementieren der IntArrayDeque-Klasse sind wie folgt.

--Erste / letzte Elemente abrufen (int getFirst (), int getLast ())

Dieses Mal werde ich zusätzlich zu diesen Funktionen diese Funktionen hinzufügen.

Daher möchte ich sagen, dass ich es hier implementiert habe, aber ich denke, dass diejenigen, die mit diesen Funktionen von Anfang an ihre eigenen Datenstrukturen erstellen können, nicht die beabsichtigten Leser dieses Artikels sind. Daher werde ich erklären, was Sie über die Implementierung denken sollten. Ich werde es tun, während ich es tue. Für diejenigen, die es kennen, mag es ziemlich langweilig erscheinen, aber bitte haben Sie Verständnis dafür, dass es für Anfänger gedacht ist (wenn Sie nur am Endprodukt interessiert sind, fahren Sie mit dem Abschnitt "Zusammenfassung" fort).

Bedienung bis zum Ende

Ich werde die Operation später am Anfang betrachten, aber hier werde ich nur die Operation bis zum Ende betrachten. Eines der Hauptmerkmale von "Deque" ist, dass die Größe umso größer ist, je mehr sie hinzugefügt wird. Betrachten wir jedoch den Fall, in dem diese Funktion vergessen wird und die maximale Größe von Anfang an bekannt ist. Wenn die maximale Größe "MAX" ist, ist die Größe "int []" type. Eine Variable (der Variablenname sei "deq") und eine Variable vom Typ "int" (der Variablenname sei "tail") geben die Anzahl der "deq" an, die beim nächsten Mal gespeichert werden sollen. Alles was Sie brauchen ist in Ordnung.

Ich werde erklären, wie man Elemente erhält / hinzufügt / löscht.

--Get: Die Stelle, an der das Element als nächstes hinzugefügt wird, ist "deq [tail]". Sie können also auf "deq [tail-1]" zugreifen, um das zuletzt eingefügte Element anzuzeigen.

Der Code, der das Obige zusammenfasst, lautet wie folgt (die Implementierung ist so, dass "MAX" an den Konstruktor übergeben wird).

IntArrayDeque.java


public class IntArrayDeque {
    private int[] deq;
    private int tail;

    public IntArrayDeque(int max) {
        this.deq = new int[max];
        this.tail = 0;
    }

    public int getLast() {
        return deq[tail - 1];
    }

    public void addLast(int v) {
        deq[tail] = v;
        tail++;
    }

    public int pollLast() {
        tail--;
        return deq[tail];
    }
}

Dies ist die Grundform der Deque. Als Nächstes werden wir sie so umschreiben, dass die Größe der Deque zunimmt, wenn mehr Elemente hinzugefügt werden.

Erhöhen Sie die Größe

Wenn Sie in der Implementierung des vorherigen Abschnitts versuchen, mehr als "MAX" einzufügen, befindet sich das Array außerhalb des Arrays. Tatsächlich ist die Lösung für dieses Problem einfach. Wenn Sie ein größeres Array vorbereiten und alles dort kopieren, ist dies in Ordnung. Die Methode für diesen Vorgang lautet "void grow ()". Sie müssen entscheiden, wie groß es sein soll, aber dieses Mal stellen wir sicher, dass Sie ein Array haben, das doppelt so groß ist wie das Original. Wenn diese Methode aufgerufen werden soll, sollte sie beim Hinzufügen eines Elements am Ende aufgerufen werden, wenn tail == deq.length (= wenn der nächste Platz außerhalb des Arrays liegt). Zum Löschen des Endes und zum Erfassen des Endes Sie müssen das nicht nennen.

Fügen Sie von oben zunächst die Methode "void grow ()" hinzu. Da wir dies nicht von außen aufrufen möchten, nennen wir sie die Methode "private".

IntArrayDeque.java


private void grow() {
    int[] newDeq = new int[deq.length * 2]; //Sichern Sie die doppelte Länge
    //Erstes Argument:Quellarray kopieren
    //Zweites Argument:Woher soll im Quellarray kopiert werden?
    //Drittes Argument:Zielarray kopieren
    //Viertes Argument:Welcher Speicherort im Zielarray als Startpunkt kopiert werden soll
    //Fünftes Argument:Länge zum Kopieren
    System.arraycopy(deq, 0, newDeq, 0, deq.length);
    deq = newDeq; //Dies verdoppelt die Länge von deq, während der Inhalt intakt bleibt
}

Und wenn Sie die Methode "void addLast (int v)" wie folgt umschreiben, sieht es so aus, als würde die Größe von außen automatisch zunehmen.

IntArrayDeque.java


public void addLast(int v) {
    if (tail == deq.length) {
        grow();
    }
    deq[tail] = v;
    tail++;
}

Jetzt können Sie alle Operationen bis zum Ende ausführen. Als Nächstes fügen wir die Operationen am Anfang hinzu.

Bedienung zum Anfang

Die Operation zum Anfang ist die gleiche wie die Operation zum Ende. Wie "tail" definieren wir eine Variable vom Typ "int" mit dem Namen "head", die die Position angibt, wenn wir sie das nächste Mal zum Anfang hinzufügen. Sie können sehen, dass "int getFirst ()", "void addFirst (int v)" und "int pollFirst ()" wie folgt geschrieben werden können.

IntArrayDeque.java


public class IntArrayDeque{
    private int[] deq;
    private int tail;
    private int head;

    public IntArrayDeque(int max) {
        this.deq = new int[max];
        this.tail = 0;
        this.head = -1;
    }

    /**
     *  getLast()Usw. entfallen
     */

    public int getFirst() {
        return deq[head + 1];
    }

    public void addFirst(int v) {
        deq[head] = v;
        head--;
    }

    public int pollFirst() {
        head++;
        return deq[head];
    }
}

Der Grund, warum der Anfangswert von "head" $ -1 $ ist, wird später erklärt.

Das Problem ist nun die Verarbeitung von "grow ()". Hier gibt es zwei mögliche Implementierungsrichtlinien.

  1. Erweitern Sie den Index in negativer Richtung wie eine gerade Linie mit Zahlen und haben Sie das negative Richtungsarray "ndeq" (das positive Richtungsarray ist "pdeq"). Und der "Kopf" befindet sich am Ende des negativen Richtungsarrays Wenn addFirst aufgerufen wird, während es erreicht ist, wird das negative Array auf die gleiche Weise wie das positive Array erweitert.

  2. Wie grow () am Ende erweitert head == -1 deq. Um jedoch am Anfang Platz zu schaffen, kopieren Sie das ursprüngliche Array an das Ende des neuen Arrays.

Persönlich denke ich, dass 1 leicht vorstellbar ist, daher werde ich dieses Mal Richtlinie 1 auswählen. Die Abbildung ist wie folgt.

npdeq

Hier stimmen in pdeq der Index und die Koordinate überein, aber in ndeq werden der Index und die Koordinate (absoluter Wert) um $ 1 $ verschoben, seien Sie also vorsichtig. Aus der obigen Abbildung geht hervor, dass der in der Koordinate $ x $ gespeicherte Wert "pdeq [x]" für $ x \ ge 0 $ und "ndeq [-x-1] für $ x \ lt 0 $ ist. Sie können sehen, dass Sie mit] `darauf zugreifen können.

Um spätere Implementierungen zu vereinfachen, implementieren Sie die "private" Methode "int getByX (int x)", die die Koordinate $ x $ verwendet und den gespeicherten Wert zurückgibt. Zusätzlich den Wert $ v $ an der Koordinate $ x $ Es implementiert auch die "private" Methode "void putByX (int x, int v)" zum Speichern.

Die Implementierung sieht folgendermaßen aus:

IntArrayDeque.java


private int getByX(int x) {
    if (x >= 0) {
        return pdeq[x];
    } else {
        return ndeq[- x - 1];
    }
}

private void putByX(int x, int v) {
    if (x >= 0) {
        pdeq[x] = v;
    } else {
        ndeq[- x - 1] = v;
    }
}

Übrigens berücksichtigen die bisher definierten Methoden wie "getLast ()" keine negativen Koordinaten. Mit "getByX" und "putByX" können diese Methoden jedoch präzise umgeschrieben werden. Masu.

Übrigens, wenn Sie die Erweiterung des Arrays auch in negativer Richtung schreiben, sieht die gesamte Klasse wie folgt aus.

IntArrayDeque.java


public class IntArrayDeque {
    private int[] pdeq;
    private int[] ndeq;
    private int tail;
    private int head;
    private int defaultSize = 64; //Weil MAX verschwunden ist,Legen Sie eine Standardgröße fest

    public IntArrayDeque() {
        this.pdeq = new int[defaultSize];
        this.ndeq = new int[defaultSize];
        this.tail = 0;
        this.head = -1;
    }

    public int getLast() {
        return getByX(tail - 1);
    }

    public void addLast(int v) {
        if (tail == pdeq.length) {
            growPositive();
        }
        putByX(tail, v);
        tail++;
    }

    public int pollLast() {
        tail--;
        return getByX(tail);
    }

    public int getFirst() {
        return getByX(head + 1);
    }

    public void addFirst(int v) {
        if (- head - 1 == ndeq.length) {
            growNegative();
        }
        putByX(head, v);
        head--;
    }

    public int pollFirst() {
        head++;
        return getByX(head);
    }

    private int getByX(int x) {
        if (x >= 0) {
            return pdeq[x];
        } else {
            return ndeq[- x - 1];
        }
    }

    private void putByX(int x, int v) {
        if (x >= 0) {
            pdeq[x] = v;
        } else {
            ndeq[- x - 1] = v;
        }
    }

    private void growPositive() {
        int[] newPdeq = new int[pdeq.length * 2];
        System.arraycopy(pdeq, 0, newPdeq, 0, pdeq.length);
        pdeq = newPdeq;
    }

    private void growNegative() {
        int[] newNdeq = new int[ndeq.length * 2];
        System.arraycopy(ndeq, 0, newNdeq, 0, ndeq.length);
        ndeq = newNdeq;
    }
}

Ich werde erklären, warum ich den Anfangswert von "Kopf" auf $ -1 $ gesetzt habe. Wenn "Kopf" und "Schwanz" den gleichen Wert haben, passiert tatsächlich etwas Falsches.

Als Beispiel sollten Sie "addLast (3)" und "addFirst (2)" ausführen, wenn "head = tail = 0".

Erstens speichert addLast (3) $ 3 $ in $ x = 0 $, was tail = 1 ergibt. Und wo speichert addFirst (2) $ 2 $? Jetzt ist head immer noch $ 0 $, also wird es so gespeichert, dass $ 2 $ $ x = 0 $ überschreibt.

Daher muss "Kopf" um $ 1 $ versetzt werden.

Nachdem alle Operationen am Anfang / Ende implementiert wurden, besteht die einzige verbleibende Grundfunktion darin, die Größe zu ermitteln (festzustellen, ob + deque leer ist).

Holen Sie sich Größe

Die Anzahl der in einer Deque enthaltenen Elemente kann leicht mit "Kopf" und "Schwanz" berechnet werden.

Wie im vorherigen Abschnitt erläutert, erhöht sich die Anzahl der Elemente um $ 0 $, "tail - head = 1". Wenn sich die Anzahl der Elemente um $ n $ erhöht, erhöht sich auch der Wert von "tail - head" um $ n $. Daher die Elemente Die Zahl $ n $ kann durch Berechnung von "tail --head --1" ermittelt werden.

Um festzustellen, ob die Deque leer ist, bestimmen Sie einfach, ob diese Größe $ 0 $ ist.

Die Methode zum Hinzufügen ist wie folgt.

IntArrayDeque.java


public int size() {
    return tail - head - 1;
}

public boolean isEmpty() {
    return size() == 0;
}

Damit ist die Implementierung der Grundfunktionen abgeschlossen. Als Nächstes werden zusätzliche Funktionen implementiert.

Holen Sie sich das i-te Element vom Anfang / Ende

Hier betrachten wir 0-indiziert. Das heißt, das $ 0 $ -te Element von Anfang an zeigt auf das erste Element. Das erste Element kann mit "getByX (head + 1)" erhalten werden, so dass das $ i $ -te Element von Anfang an mit "getByX (head + 1 + i)" erhalten werden kann. Wenn Sie auf die gleiche Weise denken, können Sie das $ i $ -te Element vom Ende mit getByX (tail -1 --i) erhalten.

Daher ist das hinzuzufügende Verfahren wie folgt.

IntArrayDeque.java


public int getFromHead(int index) {
    return getByX(head + 1 + index);
}

public int getFromTail(int index) {
    return getByX(tail - 1 - index);
}

Vorwärts-Iterator

Definieren Sie "IntArrayDequeIterator" als innere Klasse und implementieren Sie "PrimitiveIterator.OfInt". Geben Sie ihm die Koordinate "x", die Sie als Elementvariable betrachten, und der Anfangswert von "x" ist der Koordinatenkopf des ersten Elements. + 1. Die zu implementierenden Methoden sind boolean hasNext ()undint nextInt ()`.

hasNext sollte bestimmen, ob x kleiner oder gleich der nachfolgenden Koordinate tail -1 ist.

nextInt sollte getByX (x) zurückgeben und gleichzeitig x inkrementieren.

Von oben kann die innere Klasse "IntArrayDequeIterator" so implementiert werden.

IntArrayDeque$IntArrayDequeIterator.java


private class IntArrayDequeIterator implements PrimitiveIterator.OfInt {
    private int x = head + 1;

    public boolean hasNext() {
        return x <= tail - 1;
    }

    public int nextInt() {
        return getByX(x++); //Auswertungsreihenfolge ist getByX(x) -> x++Auftrag
    }
}

Definieren Sie dann auf der Seite "IntArrayDeque" eine Methode "PrimitiveIterator.OfInt iterator ()", die diesen "IntArrayDequeIterator" aufruft.

IntArrayDeque.java


public PrimitiveIterator.OfInt iterator() {
    return new IntArrayDequeIterator();
}

Iterator umkehren

Alles, was Sie tun müssen, ist die Richtung umzukehren, in der die Koordinaten gescannt werden. Definieren Sie eine innere Klasse namens "DescendingIntArrayDequeIterator", die "PrimitiveIterator.OfInt" implementiert.

IntArrayDeque$DescendingIntArrayDequeIterator.java


private class DescendingIntArrayDequeIterator implements PrimitiveIterator.OfInt {
    private int x = tail - 1;

    public boolean hasNext() {
        return x >= head + 1;
    }

    public int nextInt() {
        return getByX(x--);
    }
}

Definieren Sie "PrimitiveIterator.OfInt descendingIterator ()", das von der "IntArrayDeque" -Seite aufgerufen werden soll.

IntArrayDeque.java


public PrimitiveIterator.OfInt descendingIterator() {
    return new DescendingIntArrayDequeIterator();
}

Damit ist die Implementierung aller gewünschten Funktionen abgeschlossen.

Es gibt jedoch einige Dinge zu beachten, die sich auf PrimitiveIterator.OfInt beziehen.

Um die "IntArrayDeque" in die erweiterte "for" -Anweisung aufzunehmen, muss die "Iterable " "implementiert" sein, aber die "for" -Anweisung gilt in diesem Fall nur für die "Iterable ". Daher tritt am Ende ein automatisches Boxen / Entpacken auf, und die Bedeutung des Schreibens von "PrimitiveIterator.OfInt" zur Beschleunigung von "Iterator" geht verloren.

Eine Klasse wie "PrimitiveIterable.OfInt" ist in der Standardbibliothek implementiert und unterstützt die Anweisung "for", die dieses Problem wahrscheinlich beseitigt, aber im Moment gibt es so etwas nicht.

Um die Geschwindigkeit von "PrimitiveIterator.OfInt" zu nutzen, ist es daher erforderlich, "PrimitiveIterator.OfInt" wie folgt direkt zu betreiben.

public class Main{
    public static void main(String[] args){
        IntArrayDeque dq = new IntArrayDeque();
        // ...Operationen wie das Hinzufügen zu dq
        PrimitiveIterator.OfInt iter = dq.iterator();
        while (iter.hasNext()) {
            //Hier, iter.next()Beachten Sie, dass der Rückgabewert vom Typ Integer ist..
            int val = iter.nextInt(); 
            //Verarbeitung für jedes Element val von dq
        }
    }
}

Zusammenfassung

Schließlich beenden wir mit der gesamten IntArrayDeque-Klasse mit entsprechender Ausnahmebehandlung.

IntArrayDeque.java


import java.util.NoSuchElementException;
import java.util.PrimitiveIterator;

public class IntArrayDeque {
    private int[] pdeq;
    private int[] ndeq;
    private int tail;
    private int head;
    private int defaultSize = 64;

    public IntArrayDeque() {
        this.pdeq = new int[defaultSize];
        this.ndeq = new int[defaultSize];
        this.tail = 0;
        this.head = -1;
    }

    public int getLast() {
        if (size() == 0) {
            throw new NoSuchElementException();
        }
        return getByX(tail - 1);
    }

    public void addLast(int v) {
        if (tail == pdeq.length) {
            growPositive();
        }
        putByX(tail, v);
        tail++;
    }

    public int pollLast() {
        if (size() == 0) {
            throw new NoSuchElementException();
        }
        tail--;
        return getByX(tail);
    }

    public int getFirst() {
        if (size() == 0) {
            throw new NoSuchElementException();
        }
        return getByX(head + 1);
    }

    public void addFirst(int v) {
        if (- head - 1 == ndeq.length) {
            growNegative();
        }
        putByX(head, v);
        head--;
    }

    public int pollFirst() {
        if (size() == 0) {
            throw new NoSuchElementException();
        }
        head++;
        return getByX(head);
    }

    public int size() {
        return tail - head - 1;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public int getFromHead(int index) {
        return getByX(head + 1 + index);
    }

    public int getFromTail(int index) {
        return getByX(tail - 1 - index);
    }

    private int getByX(int x) {
        //IndexOutOfBoundsException wird in ein Array geworfen
        if (x >= 0) {
            return pdeq[x];
        } else {
            return ndeq[- x - 1];
        }
    }

    private void putByX(int x, int v) {
        //IndexOutOfBoundsException wird in ein Array geworfen
        if (x >= 0) {
            pdeq[x] = v;
        } else {
            ndeq[- x - 1] = v;
        }
    }

    private void growPositive() {
        int[] newPdeq = new int[pdeq.length * 2];
        System.arraycopy(pdeq, 0, newPdeq, 0, pdeq.length);
        pdeq = newPdeq;
    }

    private void growNegative() {
        int[] newNdeq = new int[ndeq.length * 2];
        System.arraycopy(ndeq, 0, newNdeq, 0, ndeq.length);
        ndeq = newNdeq;
    }

    public PrimitiveIterator.OfInt iterator() {
        return new IntArrayDequeIterator();
    }

    public PrimitiveIterator.OfInt descendingIterator() {
        return new DescendingIntArrayDequeIterator();
    }

    private class IntArrayDequeIterator implements PrimitiveIterator.OfInt {
        private int x = head + 1;

        public boolean hasNext() {
            return x <= tail - 1;
        }

        public int nextInt() {
            return getByX(x++);
        }
    }

    private class DescendingIntArrayDequeIterator implements PrimitiveIterator.OfInt {
        private int x = tail - 1;

        public boolean hasNext() {
            return x >= head + 1;
        }

        public int nextInt() {
            return getByX(x--);
        }
    }
}

Referenz

[Fallen und Techniken für wettbewerbsfähige Programmierung in Java](https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4#%E3%82%AA%E3%83%BC%E3%83%88%E3%83] % 9C% E3% 82% AF% E3% 82% B7% E3% 83% B3% E3% 82% B0 -% E3% 82% A2% E3% 83% B3% E3% 83% 9C% E3% 82 % AF% E3% 82% B7% E3% 83% B3% E3% 82% B0)

Recommended Posts

[Einführung in die Java-Datenstruktur] Erstellen Sie Ihre eigene schnelle ArrayDeque für den primitiven Typ
Erstellen Sie Ihre eigene Android-App für das Java-Lernen
Erstellen Sie Ihre eigenen Java-Anmerkungen
Erstellen Sie Ihre eigene Codierung für String.getBytes ()
[Einführung in Java] Informationen zu Variablen und Typen (Variablendeklaration, Initialisierung, Datentyp)
Einführung in Java zum ersten Mal # 2
[Einführung in Java] Informationen zu Variablendeklarationen und -typen
So erstellen Sie Ihre eigene Anmerkung in Java und erhalten den Wert
Informationen zu Java-Datentypen (insbesondere primitiven Typen) und Literalen
[Java] Erstellen wir einen Minecraft Mod 1.14.4 [Einführung]
[Java] Erstellen wir einen Minecraft Mod 1.16.1 [Einführung]
Erste Schritte mit Groovy für problematische Java-Ingenieure
[Einführung in Java] Grundlagen der Java-Arithmetik (für Anfänger)
[Java] Einführung in Java
Einführung in Java
So erstellen Sie einen Daten-URI (base64) in Java
Einführung in Java für Anfänger Grundkenntnisse der Java-Sprache ①
[Java] Hauptdatentypen
Einführung in den Java-Befehl
Java-Grunddatentypen
So lesen Sie Ihre eigene YAML-Datei (*****. Yml) in Java
So erstellen Sie ein leichtes Container-Image für Java-Apps