В каких случаях deque работает быстрее чем list
Действительно ли deque из модуля collections в 100 раз быстрее при предварении, чем list в Python?
Что-то не так с моим кодом? Я получаю 100-кратное ускорение при синхронизации простой функции с использованием deque из модуля collections в отличие от обычного списка.
1 ответ
Мой вопрос породил в см. Этот тест jsperf здесь: http://jsperf.com/the-fastest-way-to-truncate-an-array/7 Код установки: Benchmark.prototype.setup = function() < var test_array = []; for (var j=0; j
Из Python документов:
Deques-это обобщение стеков и очередей (название произносится как “deck” и является сокращением от “двусторонней очереди”). Deques поддерживают потокобезопасные, эффективные для памяти добавления и всплывающие окна с обеих сторон deque с примерно одинаковой производительностью O(1) в любом направлении.
Хотя объекты списка поддерживают аналогичные операции, они оптимизированы для быстрых операций фиксированной длины и требуют затрат на перемещение памяти O(n) для операций pop(0) и insert(0, v), которые изменяют как размер, так и положение базового представления данных.
Deques поддерживают итерацию, травление, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), тестирование членства с помощью оператора in и ссылки на индексы, такие как d[-1]. Индексированный доступ равен O(1) на обоих концах, но замедляется до O(n) в середине. Для быстрого произвольного доступа вместо этого используйте списки.
Теперь разница заключается в том, что список реализован с блоками памяти фиксированного размера (массивами), в то время как deque реализован как двусвязный список.
Это означает, что списки должны перераспределять память и создавать копии данных в зависимости от того, куда вы вставляете новый элемент, за исключением случаев добавления.
Но произвольный доступ (индексация) для них очень быстрый.
У Deque нет таких проблем, потому что при вставке должны быть исправлены только указатели, чтобы вставить новый узел в заданную позицию.
Но поиск данных (позиция для вставки или индексации произвольного доступа) требует итерации по deque.
Deques также потокобезопасны, но если вам не приходится иметь дело с конечными точками, т. Е. Использовать свойство очереди, списки по-прежнему остаются вашими лучшими друзьями.
Deques используют немного больше памяти для каждого элемента, потому что они хранят по крайней мере еще два целых числа (указатели) с каждым элементом.
Есть также вопрос о нарезке дека. Это можно сделать вручную, переключив конечные точки деки с помощью метода поворота. Получение N элементов, а затем поворот назад.
См. из Python docs, как del реализован только для одного элемента:
Метод rotate() обеспечивает способ реализации среза и удаления deque. Например, чистая реализация Python del d[n] полагается на метод rotate() для позиционирования элементов, которые будут извлечены:
Я думаю, что для вас этого достаточно. BTW, ваш Q-почти дубликат:
Похожие вопросы:
Я видел, как другие программисты Python использовали defaultdict из модуля collections для следующего случая использования: from collections import defaultdict s = [(‘yellow’, 1), (‘blue’, 2).
Я играл с Python collection.deque и написал следующий бенчмарк: #!/usr/bin/python import timeit if __name__==’__main__’: number = 1000000 for r in (1,10,100,1000,5000,10000,100000): print r print.
Мой вопрос породил в см. Этот тест jsperf здесь: http://jsperf.com/the-fastest-way-to-truncate-an-array/7 Код установки: Benchmark.prototype.setup = function() < var test_array = []; for (var j=0;.
Мне трудно понять, как работает deque в приведенном ниже фрагменте кода, когда я пытаюсь воссоздать очередь и стек в Python. Пример Стека-Понятно stack = [a, b, c] # push operation stack.append(e).
Этот вопрос относится к тому, действительно ли list join быстрее, чем конкатенация строк в python? и https://waymoot.org/home/python_string / Я хотел продемонстрировать, что использование + для.
Я должен получить ImportError: не удается импортировать имя ‘deque’ из ‘collections’ Как решить эту проблему? Я уже изменил имя модуля (имя модуля- collections.py ), но это не сработало.
Попытка использовать структуру данных Deque для ответа на задачу программирования, чтобы найти все суб-массивы с продуктом меньше целевого. Как уже упоминалось, я хочу использовать структуру данных.
Задача состоит в том, чтобы повернуть список, перемещая числа справа, k раз. например, [1,2,3,4,5,6,7] с k=3 будет поворачивать числа справа по одному за раз и перемещать их в верхнюю часть списка.
Анализ производительности 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 in Python
Операции на деке:
1. append () : — Эта функция используется для вставки значения в его аргументе в правый конец deque.
2. appendleft () : — Эта функция используется для вставки значения аргумента в левый конец deque.
3. pop () : — Эта функция используется для удаления аргумента из правого конца deque.
4. popleft () : — Эта функция используется для удаления аргумента из левого конца deque.
# Python-код для демонстрации работы
# append (), appendleft (), pop () и popleft ()
# импорт «коллекций» для операций deque
# используя append () для вставки элемента в правый конец
# вставляет 4 в конце deque
# печать измененного бланка
print ( «The deque after appending at right is : » )
# используя appendleft () для вставки элемента в правый конец
# вставляет 6 в начале deque
# печать измененного бланка
print ( «The deque after appending at left is : » )
# использование pop () для удаления элемента с правого конца
# удаляет 4 из правого конца deque
de.pop()
# печать измененного бланка
print ( «The deque after deleting from right is : » )
# использование popleft () для удаления элемента с левого конца
# удаляет 6 из левого конца deque
de.popleft()
# печать измененного бланка
print ( «The deque after deleting from left is : » )
5. index (ele, beg, end) : — Эта функция возвращает первый индекс значения, указанного в аргументах, начиная поиск с начала до конца index.
6. insert (i, a) : — Эта функция вставляет значение, указанное в аргументах (a), по индексу (i), указанному в аргументах.
7. remove () : — Эта функция удаляет первое вхождение значения, указанного в аргументах.
8. count () : — Эта функция подсчитывает количество вхождений значения, указанного в аргументах.
# Python-код для демонстрации работы
# insert (), index (), remove (), count ()
# импорт «коллекций» для операций deque
# используя index (), чтобы напечатать первое вхождение 4
print ( «The number 4 first occurs at a position : » )
# используя insert () для вставки значения 3 в 5-ю позицию
# печать измененного бланка
print ( «The deque after inserting 3 at 5th position is : » )
# используя count () для подсчета вхождений 3
print ( «The count of 3 in deque is : » )
# используя remove (), чтобы удалить первое вхождение 3
# печать измененного бланка
print ( «The deque after deleting first occurrence of 3 is : » )
9. extension (итерируемый) : — Эта функция используется для добавления нескольких значений в правом конце deque. Переданный аргумент является итеративным.
10. exteleft (итерируемый) : — эта функция используется для добавления нескольких значений в левой части deque. Переданный аргумент является итеративным. Порядок отменяется в результате левого добавления.
11. reverse () : — Эта функция используется для изменения порядка элементов deque.
12. rotate () : — Эта функция вращает deque на число, указанное в аргументах. Если указанное число является отрицательным, вращение происходит влево. Остальное вращение направо.
# Python-код для демонстрации работы
# extended (), exteleft (), rotate (), reverse ()
# импорт «коллекций» для операций deque
# используя extend () для добавления чисел в правый конец
# добавляет 4,5,6 к правому концу
# печать измененного бланка
print ( «The deque after extending deque at end is : » )
# используя exteleft () для добавления чисел в левый конец
# добавляет 7,8,9 к правому концу
# печать измененного бланка
print ( «The deque after extending deque at beginning is : » )
# используя rotate () чтобы повернуть деку
# поворачивается на 3 влево
# печать измененного бланка
print ( «The deque after rotating deque is : » )
# с помощью reverse () повернуть деку
de.reverse()
# печать измененного бланка
print ( «The deque after reversing deque is : » )
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
В чем разница между deque и list STL контейнерами?
В чем разница между этими двумя? Я имею в виду, что методы все те же. Таким образом, для пользователя они работают одинаково.
Из (датированный, но все же очень полезный) SGI STL резюме deque :
Deque очень похож на вектор: подобно вектору, это последовательность, которая поддерживает произвольный доступ к элементам, постоянную вставку времени и удаление элементов в конце последовательности, а также линейную временную вставку и удаление элементов в средний.
Основной способ, с помощью которого deque отличается от вектора, заключается в том, что deque также поддерживает постоянную вставку времени и удаление элементов в начале последовательности. Кроме того, deque не имеет каких-либо функций-членов, аналогичных векторной емкости() и reserve(), и не предоставляет никаких гарантий по действительности итератора, связанных с этими функциями-членами.
Здесь сводка на list с того же сайта:
Список представляет собой двусвязный список. То есть, это последовательность, которая поддерживает как обратное, так и обратное перемещение и (амортизированное) постоянное время вставки и удаления элементов в начале или в конце или в середине. Списки имеют важное свойство, что вставка и сплайсинг не делают недействительными итераторы для перечисления элементов, и даже удаление исключает только итераторы, указывающие на удаляемые элементы. Порядок итераторов может быть изменен (т.е. Список:: итератор может иметь другого предшественника или преемника после операции списка, чем раньше), но сами итераторы не будут признаны недействительными или не будут указывать на разные элементы, если это недействительность или мутация явно.
В итоге контейнеры могут иметь общие процедуры, но гарантии времени для этих процедур отличаются от контейнера к контейнеру. Это очень важно при рассмотрении вопроса о том, какой из этих контейнеров следует использовать для задачи: с учетом того, как наиболее часто используется контейнер (например, больше для поиска, чем для вставки/удаления), идет длинный путь, направляя вас в правый контейнер.
Позвольте мне перечислить различия:
Сложность
std::list – это в основном двойной список.
Нет. Deque поддерживает только O (1) вставку и удаление спереди и сзади. Например, он может быть реализован в векторе с оберткой. Поскольку он также гарантирует произвольный доступ к O (1), вы можете быть уверены, что он не использует (просто) двунаправленный список.
Еще одна важная гарантия заключается в том, как каждый отдельный контейнер хранит свои данные в памяти:
Обратите внимание, что deque был разработан, чтобы попытаться сбалансировать преимущества как вектора, так и списка без их соответствующих недостатков. Это особый интересный контейнер на платформах с ограниченной памятью, например, микроконтроллеры.
Стратегия хранения памяти часто игнорируется, однако часто это одна из самых важных причин выбора наиболее подходящего контейнера для определенного приложения.
Различия в производительности были хорошо объяснены другими. Я просто хотел добавить, что подобные или даже идентичные интерфейсы являются общими для объектно-ориентированного программирования – частью общей методологии написания объектно-ориентированного программного обеспечения. Вы не должны допускать, что два класса работают одинаково, просто потому, что они реализуют один и тот же интерфейс, больше, чем вы должны предположить, что лошадь работает как собака, потому что они оба реализуют атаки() и make_noise().
IF (вы хотите вставить или удалить только в начале или в конце массива):