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?
3 Réponses :
Stack
de Java est une très ancienne classe, introduite dans JDK 1.0. Il étend Vector
a>, et toutes ses méthodes de manipulation de données sont synchronisées
, créant une surcharge de performance très importante. Bien qu'il ne soit pas officiellement obsolète, il est obsolète et vous ne devriez vraiment pas l'utiliser de nos jours. Le ArrayDeque
a> fournit la même fonctionnalité sans la surcharge de synchronisation.
Une fois le JIT réchauffé, la synchronisation n'aurait pas d'effet: l'analyse d'échappement déterminerait que la synchronisation est inutile.
Merci! La classe ArrayDeque est-elle dangereuse dans le contexte multithreads?
@WentaoWang Non, ce n'est pas le cas. Vous pouvez utiliser LinkedBlockingDeque code >
si vous avez besoin d'une implémentation thread-safe.
Testé dans l'environnement leetcode:
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. p>
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.
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
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.
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