Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
Я так и не понял почему не стек? Это классическое решение для такой задачи, насколько я знаю.
Ответила ниже, но продублирую - Deque использовала потому, что Stack является устаревшим по спеке.
ArrayList реализует структуру на которой можно сделать стек (структуру данных)
Можно, но зачем? Если имеется готовый java.util.ArrayDeque?
Потому, что ArrayList для этой задачи достаточно, он быстрее и лучше по памяти. Это только алгоритмические параметру у них одинаковые.
Преждевременная оптимизация - корень всех бед. Доказательства будут?
Обе структуры имеют больше методов чем нужно для стека. То есть нет идеального совпадения по API. Очевидного кандидата я не вижу.
Алгоритмический стек часто реалтзуют через Array. ArrayList внутренне устроих очень близко к Array.
По производительности логика такая, что в ArrayList удаление последнего элемента будет очень быстрым так как это замена одного элемента в памяти. Вставка в основном такая же, но иногда надо сделать ресайз. Это настолько частые операции, что они оптимизированны на разных уровнях, в том числе и на железе.
Что внутри ArrayDeque нагуглить с наскока не удалось, но там явно есть двунаправленные ссылочки. А значит их надо добавлять, удалять. Работа не с единым кусом пямяти, а с разными это уже будет медленее. Хотя в рамках этой задачи она может быть и ниже погрешности измерений.
Ну и косвенные наблюдения, если бы ArrayDeck был быстрее Array на стековых задачах, то его бы чаще использовали. А так я редко вижу его вне алгоритмических задач.
Преждевременной оптимизацией это будет, если вы меня убедите, что код с использованием ArrayList будет сложнее.
Понятно. Теоретик. Судя по статьям в профиле, Вы питонист.
Что внутри ArrayDeque нагуглить с наскока не удалось
А зачем гуглить, если исходники классов стандартной библиотеки идут в комплекте с jdk? Но даже если jdk нет, то простой запрос четвёртой ссылкой выдаёт исходник на гитхабе. В котором мы видим, что внутри ArrayDeque, ВНЕЗАПНО, всё тот же массив.
А так я редко вижу его вне алгоритмических задач.
Потому что если спросить среднестатистического разработчика про фреймворк java-коллекций, то крайне редко вспоминают про очереди, прескорбно очень сие, но факт. Поэтому и не видно, потому что тупо не знают.
Понятно. Теоретик. Судя по статьям в профиле, Вы питонист.
Питон это любовь, а так много на чем проходилось код писать, в том числе на на Джаве.
Но даже если jdk нет, то простой запрос четвёртой ссылкой выдаёт исходник на гитхабе.
Ваш поисковик выиграл у моего.
В котором мы видим, что внутри ArrayDeque, ВНЕЗАПНО, всё тот же массив.
Тогда да, по скорости так-же будет. Вы правы.
Забавно, что в плане сравнения производительности в документации нет ArryList, а сравнивают c синхронизированной коллекцией.
Потому что если спросить среднестатистического разработчика про
фреймворк java-коллекций, то крайне редко вспоминают про очереди,
прескорбно очень сие, но факт. Поэтому и не видно, потому что тупо не
знают.
Я со структурами знаком и стараюсь проверять есть ли подходящяя в библиотеке языка которым я пользуюсь, но вот струкрура Deque у меня со стеком не ассоциируется никак.
Кстати это один из аргументов за использование ArrayList, потому, что все его знают.
Потому что стэк - это LIFO-очередь, чем, собственно, Deque и является.
Потому что в java.util.Stack присутствует ненужная в данном случае синхронизация, что сказывается на производительности.
Разбор неплохой, но в данной задаче у класса Deque используются только те методы, которые есть у класса Stack. Получается, решается она не только через двунаправленную очередь, для решения подошёл бы и экземпляр стека, какого-то удобства одного относительно другого тут не видно. Интереснее было бы включить еще немного информации про различия и показать, когда лучше использовать Stack, а когда имплементацию Deque, раз уж на то пошло :)
Спасибо:)
Deque использовала потому, что Stack является устаревшим по спеке.
Именно так. Кроме того, неверно (неполно, по крайней мере) описано отличие Deque от Queue. Главное отличие (что отражено и в названии) - это возможность вставлять и брать элементы с обоих концов, а не то, что это и стек. Стек тут идёт до кучи, как подмножество функционала просто с общепринятыми для стека названиями методов.
Если рассматривать структуры данных в плане алгоритмов, то неплохо бы еще и добавить что-то про сложность.
Мне очень нравится формат использующийся в этом документе для Python.
https://wiki.python.org/moin/TimeComplexity
Не совсем корректный пример, как мне кажется.
Здесь оптимальнее было бы использовать не очереди, а простой проход по массиву с получением значения «с другой стороны» до первого нарушения условия.
Думаю, лучше бы зашел пример с организацией кэша.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Использование очередей (Queue/Deque) для решения алгоритмических задач на Java