Почему использование стека контейнера медленнее?

Question

Я пытаюсь решить проблему 739, Суточные температуры на LeetCode.https://leetcode.com/problems/daily-temperatures/

Мой код использовал стековый контейнер, предоставленный 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;
    }
}

Почему сборка стека с использованием массива происходит быстрее, чем с использованием контейнера стека?

Answer 1

Протестировано в среде leetcode:

1. для запуска первого решения Stack[Integer] требуется 80 мс, а для изменения Stack[Integer] на ArrayDeque[Integer] требуется 31 мс.Что является большим улучшением, которое может доказать, что Stack намного медленнее, чем сейчас ArrayDeque.

Обратите внимание, что только pop метод и peek равны synchronized, в то время какpush это не так.

второе array[] решение занимает 10 мс в моем прогоне.а для изменения Integer[] требуется 19 мс.Так что я думаю, что автобокс также является фактором.

Так что нет единой причины для этого.

Answer 2

Только профилирование покажет вам, какие именно эффекты являются источником медленного времени работы.

Моим лучшим гостем будет создание Boxing-Integer-Intances для значений int и гораздо более сложная реализация

stack.pop() / stack.peek() / stack.push() в отличие от доступа к элементарным массивам.

Вы можете попытаться изменить версию массива для использования Integer и посмотреть, как меняется производительность.

Answer 3

Java Stack - это очень старый класс, введенный еще в JDK 1.0. Он расширяет Vector, и все его методы манипулирования данными - synchronized, создавая очень существенное снижение производительности. Хотя это официально не считается устаревшим, оно устарело, и вы действительно не должны использовать его в наши дни. Современный ArrayDeque обеспечивает те же функции без дополнительных затрат на синхронизацию.