[Introduction à la structure de données Java] Créez votre propre ArrayDeque rapide pour le type primitif

Lors de l'implémentation de la recherche de priorité de largeur et de la recherche de priorité de profondeur dans Java, je pense que beaucoup de gens l'implémentent en stockant le numéro de sommet dans ʻArrayDeque . Cependant, ce ʻArrayDeque <Integer> , Puisqu'il stocke ʻInteger, qui est une classe wrapper de ʻint, le boxing / unboxing automatique se produit fréquemment et la vitesse n'est pas bonne. Par conséquent, cette fois, je voudrais implémenter facilement un deque (ʻIntArrayDeque) dédié au ʻint haute vitesse, recommandé car il est très efficace pour sa mise en œuvre facile.

«Les fonctions minimales requises pour implémenter la classe IntArrayDeque» sont les suivantes.

Cette fois, en plus de ces fonctions, j'ajouterai ces fonctions.

Donc, je voudrais dire que je l'ai implémenté ici, mais je pense que ceux qui peuvent créer leurs propres structures de données avec ces fonctions depuis le début ne sont pas les lecteurs prévus de cet article, donc je vais vous expliquer ce qu'il faut penser de sa mise en œuvre. Je le ferai en faisant. Cela peut sembler assez fastidieux pour ceux qui le connaissent, mais sachez que c'est pour les débutants (si vous n'êtes intéressé que par le produit final, passez à la section "Résumé").

Opération jusqu'au bout

Je considérerai l'opération au début plus tard, mais ici je ne considérerai que l'opération jusqu'à la fin. L'une des principales caractéristiques de Deque est que plus il est ajouté, plus la taille est grande. Cependant, considérons le cas où cette fonction est oubliée et la taille maximale est connue depuis le début. Si la taille maximale est «MAX», la taille est de type «MAX» «int []». Une variable (que le nom de la variable soit «deq») et une variable de type «int» (que le nom de la variable soit «tail») indiquant le nombre de «deq» à stocker la prochaine fois. Tout ce dont vous avez besoin est ok.

Je vais expliquer dans l'ordre comment obtenir / ajouter / supprimer des éléments.

--Get: L'endroit où l'élément est ajouté ensuite est deq [tail], donc vous pouvez accéder à deq [tail-1] pour voir le dernier élément que vous avez mis.

--Add: L'endroit suivant pour ajouter l'élément est deq [tail], donc vous pouvez stocker la valeur que vous voulez ajouter dans deq [tail]. Disons «tail ++».

--Delete: Dans l'opération de suppression, la valeur supprimée est la valeur de retour. Puisque le dernier élément est supprimé, la valeur de retour est deq [tail-1]. De plus, il y a un endroit pour placer l'élément suivant. Pour le renvoyer, utilisez tail --. Lors de l'implémentation, vous ne pouvez pas écrire une instruction return puis une tail --, donc le return deq [tail] ʻafter the tail --en premier. (Notez quetail` vaut d'abord -1).

Le code qui résume ce qui précède est le suivant (l'implémentation est telle que «MAX» est passé au constructeur).

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];
    }
}

C'est la forme de base de deque. Ensuite, nous allons la réécrire de sorte que plus vous ajoutez d'éléments, plus la taille de deque est grande.

Augmenter la taille

Dans l'implémentation de la section précédente, si vous essayez d'insérer plus de «MAX», il sera hors du tableau. En fait, la solution à ce problème est simple, si vous préparez un plus grand tableau et copiez tout ce qu'il y a, ce n'est pas grave. La méthode pour faire cette opération est void grow (). Vous devez décider de la taille souhaitée, mais cette fois, assurez-vous que vous disposez d'un tableau qui est deux fois la taille de l'original. Aussi, quand appeler cette méthode, elle doit être appelée if tail == deq.length (= si le prochain endroit à placer est en dehors du tableau) lors de l'ajout d'un élément à la fin. Pour la suppression de fin et l'acquisition de la queue Vous n'êtes pas obligé d'appeler ça.

De ce qui précède, ajoutez d'abord la méthode void grow (). Puisque nous ne voulons pas l'appeler de l'extérieur, nous l'appellerons la méthode private.

IntArrayDeque.java


private void grow() {
    int[] newDeq = new int[deq.length * 2]; //Fixez deux fois la longueur
    //Premier argument:Copier le tableau source
    //Deuxième argument:Où copier dans le tableau source
    //Troisième argument:Copier la matrice de destination
    //Quatrième argument:Quel emplacement dans le tableau de destination copier comme point de départ
    //Cinquième argument:Longueur à copier
    System.arraycopy(deq, 0, newDeq, 0, deq.length);
    deq = newDeq; //Cela double la longueur de deq tout en gardant le contenu intact
}

Et si vous réécrivez la méthode void addLast (int v) comme suit, il semble que la taille augmente automatiquement de l'extérieur.

IntArrayDeque.java


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

Vous pouvez maintenant effectuer toutes les opérations jusqu'à la fin, puis nous ajouterons les opérations au début.

Opération au début

L'opération au début est la même que l'opération à la fin. Comme tail, nous définissons une variable de type ʻint appelée head, qui indique la position lorsque nous l'ajoutons au début la prochaine fois. Vous pouvez voir que ʻint getFirst () ,void addFirst (int v), ʻint pollFirst ()` peut être écrit comme suit.

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()Etc. sont omis
     */

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

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

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

La raison pour laquelle la valeur initiale de head est $ -1 $ sera expliquée plus loin.

Maintenant, le problème est le traitement de "grow ()". Ici, il y a deux politiques d'implémentation possibles.

  1. Étendez l'index dans la direction négative comme une ligne droite numérique et ayez le tableau de direction négative ndeq (le tableau de direction positive est pdeq). Et la tête est à la fin du tableau de direction négative Lorsque ʻaddFirst` est appelé alors qu'il est atteint, le tableau négatif est développé de la même manière que le tableau positif.

  2. Comme grow () à la fin, head == -1 étend deq. Cependant, pour faire de la place au début, copiez le tableau d'origine à la fin du nouveau tableau.

Personnellement, je pense que 1 est facile à imaginer, je vais donc cette fois sélectionner la politique 1. Le chiffre est le suivant.

npdeq

Ici, dans pdeq, l'indice et la coordonnée correspondent, mais dans ndeq, l'indice et la coordonnée (valeur absolue) sont décalés de $ 1 $, donc soyez prudent. De plus, d'après la figure ci-dessus, la valeur stockée dans la coordonnée $ x $ est pdeq [x] pour $ x \ ge 0 $ et ndeq [-x-1] pour $ x \ lt 0 $. Vous pouvez voir que vous pouvez y accéder avec] .

Pour faciliter les implémentations ultérieures, implémentez la méthode private ʻint getByX (int x), qui prend la coordonnée $ x $ et renvoie la valeur stockée. De plus, la valeur $ v $ à la coordonnée $ x $ Il implémente également la méthode private`` void putByX (int x, int v)` to store.

La mise en œuvre ressemble à ceci:

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;
    }
}

Au fait, les méthodes que nous avons définies jusqu'à présent, telles que getLast (), ne prennent pas en compte les coordonnées négatives. Cependant, en utilisant getByX et putByX, nous pouvons réécrire ces méthodes de manière concise. Masu.

Au fait, si vous écrivez également l'extension du tableau dans le sens négatif, la classe entière sera comme suit.

IntArrayDeque.java


public class IntArrayDeque {
    private int[] pdeq;
    private int[] ndeq;
    private int tail;
    private int head;
    private int defaultSize = 64; //Parce que MAX a disparu,Choisissez une taille par défaut

    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;
    }
}

Je vais vous expliquer pourquoi j'ai défini la valeur initiale de head sur $ -1 $. En fait, si head et tail ont la même valeur, quelque chose d'un peu mal se produit.

Par exemple, envisagez d'exécuter ʻaddLast (3) et ʻaddFirst (2) quand head = tail = 0.

Premièrement, ʻaddLast (3) stocke $ 3 $ dans $ x = 0 $, ce qui donne tail = 1. Et où ʻaddFirst (2) stocke-t-il $ 2 $? Maintenant, head vaut toujours $ 0 $, donc il sera stocké de manière à ce que $ 2 $ écrase $ x = 0 $.

Par conséquent, head doit être décalé de 1 $ $.

Maintenant que toutes les opérations au début / à la fin ont été implémentées, la seule fonction de base qui reste est d'obtenir la taille (déterminer si + deque est vide).

Obtenir la taille

Le nombre d'éléments contenus dans un deque peut être facilement calculé en utilisant "head" et "tail".

Comme expliqué dans la section précédente, lorsque le nombre d'éléments est $ 0 $, tail --head = 1. Lorsque le nombre d'éléments augmente de $ n $, la valeur de tail --head augmente également de $ n $. Par conséquent, les éléments Le nombre $ n $ peut être trouvé en calculant tail --head --1.

Pour déterminer si le deque est vide, déterminez simplement si cette taille est de 0 $.

La méthode à ajouter est la suivante.

IntArrayDeque.java


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

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

Ceci termine l'implémentation des fonctions de base, puis nous implémenterons des fonctions supplémentaires.

Obtenez le i-ème élément du début / de la fin

Ici, nous considérons que l'indexation est 0. C'est-à-dire que l'élément $ 0 $ th du début pointe vers le premier élément. Le premier élément peut être obtenu avec getByX (head + 1), donc le $ i $ ème élément du début peut être obtenu avec getByX (head + 1 + i). Aussi, en pensant de la même manière, l'élément $ i $ ème de la fin peut être obtenu avec getByX (tail -1 --i).

Par conséquent, la méthode à ajouter est la suivante.

IntArrayDeque.java


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

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

Itérateur avant

Définissez ʻIntArrayDequeIterator comme classe interne et ʻimplements`` PrimitiveIterator.OfInt. Ayez la coordonnée x que vous regardez comme variable membre, et la valeur initiale de x est la coordonnée tête du premier élément. + 1. Les méthodes à implémenter sont boolean hasNext () et ʻint nextInt () `.

hasNext devrait déterminer si x est inférieur ou égal à la coordonnée de fin tail -1.

nextInt doit retourner getByX (x) ʻet en même temps incrémenter x`.

De ce qui précède, la classe interne ʻIntArrayDequeIterator` peut être implémentée comme ceci.

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++); //L'ordre d'évaluation est getByX(x) -> x++Commande
    }
}

Ensuite, du côté ʻIntArrayDeque, définissez une méthode PrimitiveIterator.OfInt iterator () qui appelle cela ʻIntArrayDequeIterator.

IntArrayDeque.java


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

Itérateur inversé

Tout ce que vous avez à faire est d'inverser la direction dans laquelle les coordonnées sont scannées. Définissez une classe interne appelée DescendingIntArrayDequeIterator qui rend PrimitiveIterator.OfInt ʻimplements`.

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--);
    }
}

Définissez PrimitiveIterator.OfInt descendingIterator () à appeler du côté ʻIntArrayDeque`.

IntArrayDeque.java


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

Ceci termine la mise en œuvre de toutes les fonctions souhaitées.

Cependant, il y a certaines choses à savoir concernant PrimitiveIterator.OfInt.

Afin d'incorporer ʻIntArrayDeque dans l'instruction étendue for, ʻIterable <Integer> doit être ʻimplements, mais l'instruction for dans ce cas est uniquement pour ʻIterable <Integer>. Par conséquent, à la fin, un boxing / unboxing automatique se produira, et la signification d'écrire PrimitiveIterator.OfInt pour accélérer ʻIterator` sera perdue.

Une classe comme PrimitiveIterable.OfInt est implémentée dans la bibliothèque standard et prend en charge l'extension for, ce qui élimine probablement ce problème, mais cela n'existe pas pour le moment.

Par conséquent, afin de profiter de la vitesse de "PrimitiveIterator.OfInt", il est nécessaire de faire fonctionner directement "PrimitiveIterator.OfInt" comme suit.

public class Main{
    public static void main(String[] args){
        IntArrayDeque dq = new IntArrayDeque();
        // ...Opérations telles que l'ajout à dq
        PrimitiveIterator.OfInt iter = dq.iterator();
        while (iter.hasNext()) {
            //ici, iter.next()Notez que la valeur de retour sera de type Integer..
            int val = iter.nextInt(); 
            //Traitement à effectuer pour chaque élément val de dq
        }
    }
}

Résumé

Enfin, nous terminons avec la classe entière ʻIntArrayDeque` avec une gestion des exceptions appropriée.

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 est jeté dans un tableau
        if (x >= 0) {
            return pdeq[x];
        } else {
            return ndeq[- x - 1];
        }
    }

    private void putByX(int x, int v) {
        //IndexOutOfBoundsException est jeté dans un tableau
        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--);
        }
    }
}

référence

[Traps and Techniques for Competitive Programming 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

[Introduction à la structure de données Java] Créez votre propre ArrayDeque rapide pour le type primitif
Créez votre propre application Android pour l'apprentissage Java
Créez vos propres annotations Java
Créez votre propre encodage pour String.getBytes ()
[Introduction à Java] À propos des variables et des types (déclaration de variable, initialisation, type de données)
Introduction à Java pour la première fois # 2
[Introduction à Java] À propos des déclarations et des types de variables
Comment créer votre propre annotation en Java et obtenir la valeur
À propos des types de données Java (en particulier des types primitifs) et des littéraux
[Java] Créons un Minecraft Mod 1.14.4 [Introduction]
[Java] Créons un Minecraft Mod 1.16.1 [Introduction]
Premiers pas avec Groovy pour les ingénieurs Java gênants
[Introduction à Java] Bases de l'arithmétique Java (pour les débutants)
[Java] Introduction à Java
Introduction à Java
Comment créer un URI de données (base64) en Java
Introduction à Java pour les débutants Connaissance de base du langage Java ①
[Java] Principaux types de données
Introduction à la commande java
Types de données de base Java
Comment lire votre propre fichier YAML (*****. Yml) en Java
Comment créer une image de conteneur légère pour les applications Java