2
votes

Pourquoi l'utilisation du conteneur empilé est-elle plus lente?

J'essaye de résoudre le problème 739, Températures quotidiennes sur LeetCode. https://leetcode.com/problems/daily-temperatures/

Mon code utilisé Stack container fourni par le JAVA. Il faut 60 ms pour fonctionner. Voici mon code:

class Solution {
    public int[] dailyTemperatures(int[] T) {

        int[] temperatures = T;
        if(temperatures == null) return null;

        int[] result = new int[temperatures.length];
        int[] stack = new int[temperatures.length];
        int top = 0;
        stack[top] = -1;

        for(int i = 0; i < temperatures.length; i++) {
            while(stack[top] != -1 && temperatures[i] > temperatures[stack[top]]) {
                int index = stack[top--];
                result[index] = i - index;
            }

            stack[++top] = i;
        }

        return result;
    }
}

Voici un code qui ne prend que 6ms pour s'exécuter:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ret = new int[T.length];
        Stack<Integer> stack = new Stack<Integer>();
        for(int i=0; i < T.length; i++){
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
                int index = stack.pop();
                ret[index] = i - index;             
            }
            stack.push(i);
        }
        return ret;
    }
}

Pourquoi construire la pile l'utilisation d'un tableau est-elle plus rapide que l'utilisation du conteneur de pile?


4 commentaires

Autoboxing, peut-être.


@rjdkolb Votre modification a remplacé le premier code par le second, ce qui les rend identiques. Annulées.


Vous pouvez tester si elle est causée par une boîte automatique en utilisant un Integer [] pour le deuxième exemple.


@Wentao Wang, quelle entrée utilisez-vous? int [] entrée = {73, 74, 75, 71, 69, 72, 76, 73}; prend 0 ms pour les deux exemples sur mon PC utilisant Java 11


3 Réponses :



1
votes

Testé dans l'environnement leetcode:

  1. la première solution Stack [Integer] prend 80 ms pour s'exécuter, et le changement de Stack [Integer] en ArrayDeque [Integer] prend 31 ms. Ce qui est une grande amélioration, qui peut prouver que Stack est beaucoup plus lent que le morden ArrayDeque .

Notez que seuls la méthode pop et peek sont synchronisés , alors que le push ne l'est pas.

  1. la deuxième solution array [] prend 10 ms dans mon exécution. et changer en Integer [] prend 19 ms. Je pense donc que la boxe automatique est également un facteur.

Il n'y a donc pas une seule raison à cela.


4 commentaires

Voyez-vous les mêmes heures sur une machine virtuelle Java locale à l'aide de System.currentTimeMillis ()? Mes expériences montrent 0 ms pour les deux en utilisant int [] input = {73, 74, 75, 71, 69, 72, 76, 73};


Non, leetcode teste le code pour plusieurs entrées et additionne le temps d'exécution.


Comme votre entrée est petite, il est raisonnable qu'elle ne coûte que près de 0 ms, peut-être pourrons-nous la tester avec une TRES grande entrée sur notre machine locale.


Pour améliorer votre réponse, il serait bien de simuler plusieurs entrées dans une JVM locale avec un profileur et de le montrer visuellement



0
votes

Seul le profilage vous montrera exactement quels effets sont à l'origine du temps d'exécution plus lent.

Mon meilleur invité serait la création de Boxing-Integer-Intances pour les valeurs int et l'implémentation beaucoup plus complexe de

stack.pop () / stack.peek () / stack.push () contrairement aux accès élémentaires aux tableaux. < / p>

Vous pouvez essayer de changer la version de votre tableau pour utiliser à la place Integer et voir comment les performances changent.


0 commentaires