В каких случаях коллекция deque работает быстрее чем list
В чем разница между контейнерами deque и list STL?
Какая разница между двумя? То есть методы у всех одинаковые. Итак, для пользователя они работают одинаково.
9 ответов
Из (устаревшего, но все же очень полезного) SGI STL резюме deque :
Двухсторонняя очередь очень похожа на вектор: как и вектор, это последовательность, которая поддерживает произвольный доступ к элементам, постоянную вставку и удаление элементов в конце последовательности, а также линейную вставку и удаление элементов в середине.
Основное отличие deque от вектора заключается в том, что deque также поддерживает вставку и удаление элементов с постоянным временем в начале последовательности. Кроме того, deque не имеет никаких функций-членов, аналогичных функциям vector capacity () и reserve (), и не предоставляет никаких гарантий действительности итератора, связанных с этими функциями-членами.
Вот сводка по list с того же сайта:
Позвольте мне перечислить различия:
Сложность
Обратите внимание, что двухсторонняя очередь была разработана, чтобы попытаться уравновесить преимущества как вектора, так и списка без их соответствующих недостатков. Это особенно интересный контейнер для платформ с ограниченным объемом памяти, например микроконтроллеров.
Стратегия хранения в памяти часто упускается из виду, однако часто это одна из наиболее важных причин для выбора наиболее подходящего контейнера для определенного приложения.
Нет. Двухсторонняя очередь поддерживает только вставку и удаление O (1) спереди и сзади. Это может быть, например, реализовано в векторе с циклическим переходом. Поскольку он также гарантирует произвольный доступ O (1), вы можете быть уверены, что он не использует (просто) двусвязный список.
Среди выдающихся различий между deque и list
Предметы хранятся рядом;
Оптимизирован для добавления данных с двух сторон (спереди, сзади);
Элементы индексируются числами (целыми числами).
Может просматриваться итераторами и даже индексом элемента.
Время доступа к данным быстрее.
Элементы хранятся в памяти «случайным образом»;
Доступен для просмотра только итераторами;
Оптимизирован для вставки и удаления посередине.
Доступ по времени к данным медленнее, медленнее для итерации из-за очень плохой пространственной локализации.
Очень хорошо справляется с крупными элементами
Надеюсь, я поделился полезной информацией.
Двусторонняя очередь
Элементы коллекции хранятся в блоках памяти. Количество элементов в блоке зависит от размера элемента: чем больше элементы, тем меньше в блоке. Основная надежда заключается в том, что если блоки имеют одинаковый размер независимо от типа элементов, это должно помочь распределителю в большинстве случаев.
Двусвязный список
Двусвязные списки, пожалуй, более обычны. Каждый элемент хранится в собственном блоке памяти, выделенном независимо от других элементов. В каждом блоке у вас есть значение элемента и два указателя: один на предыдущий элемент, один на следующий элемент. Это позволяет очень легко вставить элемент в любую позицию в списке или даже переместить подцепочку элементов из одного списка в другой (операция, называемая сплайсинг ): вам просто нужно обновить указатели в начало и конец точки вставки. Обратной стороной является то, что чтобы найти один элемент по его индексу, вам нужно пройти по цепочке указателей, поэтому произвольный доступ имеет линейную стоимость в количестве элементов в списке.
Вот доказательство концепции использования кода списка, неупорядоченной карты, которая дает O (1) поиск и O (1) точное обслуживание LRU. Требуются (не стертые) итераторы, чтобы выдержать операции стирания. Запланируйте использование в O (1) произвольно большом программном управляемом кэше для указателей ЦП в памяти графического процессора. Указывает на планировщик Linux O (1) (LRU очередь выполнения на процессор). Unordered_map имеет постоянный доступ по времени через хеш-таблицу.
Анализ производительности std::vector, std::list & std::deque
В этой статье рассматривается тестирование производительности стандартных STL-контейнеров C++: std::vector, std::list и std::deque. Тестирование скорости работы контейнеров проводится для операций вставки, поиска и удаления.
Эта статья является переводом, оригинальная статья находится здесь.
Добавление в конец
Вектор с предварительно выделенной память немного быстрее всех, а список в три раза медленнее, чем вектор.
Теперь возьмем тип с большим размером (4096 байт):
Здесь ситуация меняется. Вектор и список имеют схожую скорость. Двусвязная очередь немного быстрее, чем вектор и список. Вектор с заранее выделенной памятью по-прежнему выигрывает.
Наконец, если использовать нетривиальный тип данных:
Вывод: Для операций добавления в конец контейнера (push_back) наиболее хорошо подходят векторы с заранее выделенной памятью.
Линейный поиск
Для осуществления линейного поиска контейнеры заполняются числами от 0 до N. Затем все элементы контейнера перемешиваются и используется функция std::find(), которая и осуществляет линейный поиск в контейнере.
Из графика видно, что список (std::list) имеет очень низкую производительность поиска данных.
Если взять тип данных большего размера:
Список по-прежнему намного медленнее других контейнеров. Но интересно то, что разница между вектором и двусвязной очередью уменьшается. Еще увеличим размер:
Вывод: список очень плохо справляется с линейным поисков данных. Двусвязная очередь показывает лучшие результаты на данных большего размера, в то время, как вектор работает наиболее быстро на данных меньшего размера.
Случайная вставка с линейным поиском
Контейнер заполняется числами от 0 до N, затем данные перемешиваются. После этого в контейнер вставляется 1000 элементов в случайные позиции. Случайные позиции ищутся с помоью линейного поиска. В предыдущих тестах было видно, что список работает очень медленно при линейном поиске, поэтому имеет смысл оценить, насколько помогает исправить ситуацию быстрая вставка.
И снова список оказывается значительно медленне, чем другие контейнеры. Это происходит из-за медленного линейного поиска. Даже если другим контейнерам приходится перемещать много данных, эта операция дешевая для данных небольших размеров.
Увеличим размер типа данных:
Результат довольно интересен. Недостаток производительности списка уменьшается по сравнению с другими контейнерами, а двусвязная очередь оказывается быстрее всех. Еще увеличим размер:
Список более чем в 20 раз быстрее вектора. В случае с двусвязной очередью элементы можно добавлять в начало или конец, вставка в середину является наиболее дорогой операцией составляющей по сложности O(n/2). Однако, даже в этом случае, вставка в двусвязную очередь работает быстрее, чем вставка в вектор.
Последний тест можно провести с использованием нетривиального типа данных:
Случайное удаление
В теории случайное удаление в плане производительности приближается к случайной вставке.
Контейнер заполняется числами от 0 до N и перемешивается. Затем 1000 случайных элементов удаляется из случайных позиций контейнера.
Действительно, по графикам видно, что операция удаления показывает ту же производительность, что и вставка.
Заключение
Несколько фактов о каждом контейнере:
Соответственно, заключение о том, где использовать контейнеры:
deque.popleft () и list.pop (0). Есть ли разница в производительности?
deque.popleft() и list.pop(0) вернуть тот же результат. Есть ли разница в производительности между ними и почему?
3 ответа
deque.popleft () быстрее, чем list.pop (0), потому что deque был оптимизирован для выполнения popleft () приблизительно в O (1), а list.pop (0) принимает O (n) (см. объекты deque ).
Для Python 2.7 и 3.5 URL-адреса этих файлов исходного кода:
При использовании% timeit разница в производительности между deque.popleft () и list.pop (0) составляет примерно 4 раза, когда и deque, и список имеют одинаковые 52 элемента и увеличиваются более чем в 1000 раз, когда их длина составляет 10 ** 8. Результаты теста приведены ниже.
Есть ли разница в производительности?
deque() использует двусвязный список. Независимо от того, насколько велика очередь, deque.popleft() требует постоянного (ограниченного выше) количества операций.
Да, и это важно, если у вас длинный список или очередь. Все элементы в списке размещаются в памяти последовательно, поэтому, если вы удаляете какой-либо элемент, все последующие элементы должны быть смещены на одну позицию влево, поэтому время, необходимое для удаления или вставки элемента в начале списка, пропорционально длина списка. Deque, с другой стороны, специально сконструирован, чтобы обеспечить быструю вставку или удаление на конце либо (как правило, позволяя «пустым» ячейкам памяти в начале deque, или оборачивать так, чтобы конец сегмента памяти, занятого deque, может содержать элементы, которые фактически считаются в начале deque).
Сравните производительность этих двух фрагментов:
В чем разница между deque и list STL контейнерами?
В чем разница между этими двумя? Я имею в виду, что методы все те же. Таким образом, для пользователя они работают одинаково.
Из (датированный, но все же очень полезный) SGI STL резюме deque :
Deque очень похож на вектор: подобно вектору, это последовательность, которая поддерживает произвольный доступ к элементам, постоянную вставку времени и удаление элементов в конце последовательности, а также линейную временную вставку и удаление элементов в средний.
Основной способ, с помощью которого deque отличается от вектора, заключается в том, что deque также поддерживает постоянную вставку времени и удаление элементов в начале последовательности. Кроме того, deque не имеет каких-либо функций-членов, аналогичных векторной емкости() и reserve(), и не предоставляет никаких гарантий по действительности итератора, связанных с этими функциями-членами.
Здесь сводка на list с того же сайта:
Список представляет собой двусвязный список. То есть, это последовательность, которая поддерживает как обратное, так и обратное перемещение и (амортизированное) постоянное время вставки и удаления элементов в начале или в конце или в середине. Списки имеют важное свойство, что вставка и сплайсинг не делают недействительными итераторы для перечисления элементов, и даже удаление исключает только итераторы, указывающие на удаляемые элементы. Порядок итераторов может быть изменен (т.е. Список:: итератор может иметь другого предшественника или преемника после операции списка, чем раньше), но сами итераторы не будут признаны недействительными или не будут указывать на разные элементы, если это недействительность или мутация явно.
В итоге контейнеры могут иметь общие процедуры, но гарантии времени для этих процедур отличаются от контейнера к контейнеру. Это очень важно при рассмотрении вопроса о том, какой из этих контейнеров следует использовать для задачи: с учетом того, как наиболее часто используется контейнер (например, больше для поиска, чем для вставки/удаления), идет длинный путь, направляя вас в правый контейнер.
Позвольте мне перечислить различия:
Сложность
std::list – это в основном двойной список.
Нет. Deque поддерживает только O (1) вставку и удаление спереди и сзади. Например, он может быть реализован в векторе с оберткой. Поскольку он также гарантирует произвольный доступ к O (1), вы можете быть уверены, что он не использует (просто) двунаправленный список.
Еще одна важная гарантия заключается в том, как каждый отдельный контейнер хранит свои данные в памяти:
Обратите внимание, что deque был разработан, чтобы попытаться сбалансировать преимущества как вектора, так и списка без их соответствующих недостатков. Это особый интересный контейнер на платформах с ограниченной памятью, например, микроконтроллеры.
Стратегия хранения памяти часто игнорируется, однако часто это одна из самых важных причин выбора наиболее подходящего контейнера для определенного приложения.
Различия в производительности были хорошо объяснены другими. Я просто хотел добавить, что подобные или даже идентичные интерфейсы являются общими для объектно-ориентированного программирования – частью общей методологии написания объектно-ориентированного программного обеспечения. Вы не должны допускать, что два класса работают одинаково, просто потому, что они реализуют один и тот же интерфейс, больше, чем вы должны предположить, что лошадь работает как собака, потому что они оба реализуют атаки() и make_noise().
IF (вы хотите вставить или удалить только в начале или в конце массива):
Контейнеры STL C++: в чем разница между deque и list?
в чем разница между ними? Я имею в виду, что все методы одинаковы. Для пользователя они работают одинаково.
6 ответов
от (датированный, но все еще очень полезный)SGI STL итог deque :
deque очень похож на вектор: как и вектор, это последовательность, поддерживающая произвольный доступ к элементам, постоянную временную вставку и удаление элементов в конце последовательности и линейную временную вставку и удаление элементов в середине.
основной способ, которым deque отличается от вектора, заключается в том, что deque также поддерживает постоянное время вставка и удаление элементов в начале последовательности. Кроме того, deque не имеет функций-членов, аналогичных capacity() и reserve () вектора, и не предоставляет каких-либо гарантий достоверности итератора, связанных с этими функциями-членами.
вот резюме на list С того же сайта:
список-это дважды связанный список. То есть, это последовательность, которая поддерживает как вперед, так и обратный обход, и (амортизированный) ввод постоянного времени и удаление элементов в начале или конце, или в середине. Списки имеют важное свойство, что вставка и сращивание не делают недействительными итераторы для элементов списка, и что даже удаление делает недействительными только итераторы, указывающие на удаляемые элементы. Порядок итераторов может быть изменен (то есть list::iterator может иметь другой предшественник или преемник после операции списка, чем раньше), но сами итераторы не будут признаны недействительными или сделаны для указания на разные элементы, если это недействительность или мутация не явны.
в итоге контейнеры могут иметь общие процедуры, но гарантии времени для этих процедур отличаются от контейнера к контейнеру. Это очень важно при рассмотрении того, какой из этих контейнеров использовать для задачи: с учетом как контейнер будет наиболее часто использоваться (например, больше для поиск, чем для вставки / удаления) проходит долгий путь, направляя вас к правильному контейнеру.
позвольте мне перечислить различия:
сложности
нет. Deque поддерживает только O (1) вставку и удаление спереди и сзади. Например, он может быть реализован в векторе с обтеканием. Поскольку он также гарантирует O (1) случайный доступ, вы можете быть уверены, что он не использует (просто) дважды связанный список.
другой важной гарантией является то, как каждый контейнер хранит свои данные в памяти:
обратите внимание, что deque был разработан для попытаться баланс преимуществ как векторные, так и без их недостатков. Это особенно интересный контейнер в памяти ограниченных платформ, например, микроконтроллеров.
стратегия хранения памяти часто упускается из виду, однако часто Это одна из самых важных причин для выбора наиболее подходящего контейнера для определенного приложения.