Почему использование контейнера стека медленнее?
Я пытаюсь решить проблему 739, Daily Temperatures на LeetCode. https://leetcode.com/problems/daily-temperatures/
В моем коде использовался контейнер Stack, предоставленный JAVA. Запуск занимает 60 мс. Это мой код:
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;
}
}
Вот код, запуск которого занимает всего 6 мс:
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;
}
}
Почему создание стека с использованием массива быстрее, чем с использованием контейнера стека?
@rjdkolb Ваше редактирование заменило первый код вторым, сделав их такими же. Откат.
Вы можете проверить, вызвано ли это автобоксингом, используя Integer[] для второго примера.
@Wentao Wang, какой вход вы используете? int [] input = {73, 74, 75, 71, 69, 72, 76, 73}; занимает 0 мс для обоих примеров на моем ПК с использованием Java 11
Ответы 3
Stack в Java - это старый класс очень, представленный еще в JDK 1.0. Он расширяет Vector, и все его методы обработки данных - это synchronized, что создает очень большие накладные расходы на производительность. Хотя он официально не устарел, он устарел, и вам действительно не следует использовать его в наши дни. Современный ArrayDeque предоставляет те же функции без дополнительных затрат на синхронизацию.
После того, как JIT разогреется, синхронизация не будет иметь никакого эффекта: анализ выхода определит, что в синхронизации нет необходимости.
Спасибо! Является ли класс ArrayDeque небезопасным в контексте многопоточности?
Протестировано в среде leetcode:
- запуск первого решения
Stack[Integer]занимает 80 мс, а изменениеStack[Integer]наArrayDeque[Integer]занимает 31 мс. Это большое улучшение, которое может доказать, чтоStackнамного медленнее, чем современныйArrayDeque.
Обратите внимание, что только метод pop и peek относятся к synchronized, а push - нет.
- второе решение
array[]занимает у меня 10 мсек. а переключение наInteger[]занимает 19 мс. Так что я думаю, что автобокс также играет важную роль.
Так что для этого нет единой причины.
Вы видите то же время на локальной JVM с помощью System.currentTimeMillis ()? Мои эксперименты показывают 0 мс для обоих с использованием int [] input = {73, 74, 75, 71, 69, 72, 76, 73};
Нет, leetcode проверяет код для нескольких входов и суммирует время выполнения.
Поскольку ваш ввод небольшой, разумно, что он будет стоить всего около 0 мс, возможно, мы сможем протестировать его с ОЧЕНЬ большим вводом на нашей локальной машине.
Чтобы улучшить ваш ответ, было бы неплохо смоделировать несколько входов в локальной JVM с помощью профилировщика и визуально показать это
Только профилирование покажет вам, какие именно эффекты являются причиной замедления времени работы.
Моим лучшим гостем было бы создание Boxing-Integer-Intances для значений int и гораздо более сложная реализация
stack.pop() / stack.peek() / stack.push() в отличие от доступа к элементарным массивам.
Вы можете попробовать изменить версию своего массива, чтобы вместо этого использовать Integer, и посмотреть, как изменится производительность.
Возможно автобокс.