Что такое deque python

​​collections.deque – очередь Python

deque – коллекция двухсторонней очереди, которая похожа на список, за исключением того, что добавлять и удалять элементы можно либо в начало (слева), либо в конец (справа). Можно использовать и как стек. Реализована через двусвязный список. Благодаря этому, операции добавления или удаления элемента с любого конца deque имеют сложность O(1). Доступ к произольному элементу – O(n).

Методы

Метод append(x) – добавить элемент в конец.

Метод appendleft(x) – добавить элемент в начало.

Метод pop(x) – удалить и вернуть элемент с конца.

Метод popleft(x) – удалить и вернуть элемент с начала.

Метод clear() – очистить очередь.

Метод reverse() – развернуть очередь наоборот:

Метод rotate(n) – последовательно переносит n элементов с конца в начало (если n отрицательно, то из начала в конец):

Метод extend(iterable) – добавляет в конец все элементы iterable.

Метод extendleft(iterable) – добавляет в начало все элементы iterable (начиная с последнего элемента iterable):

Метод insert(index, x) – вставить элемент x в индекс i (медленно).

d[index] – доступ к элементу по индексу (медленно).

len(d) – число элементов в очереди (тоже работает медленно).

Метод remove(value) – удаляет первое вхождение значения value (слева направо). Остальные элементы не трогаются.

Метод count(value) – количество элементов со значением value в очереди.

Максимальная длина

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈

Источник

Не изобретать велосипед, или Обзор модуля collections в Python

Leo Matyushkin

Это доступный «из коробки» родной модуль Python – те самые батарейки, что идут в комплекте. Уверенное владение инструментарием collections, itertools и других модулей стандартной библиотеки – одна из черт, отличающих продвинутых питонистов от новичков.

Рассмотрим на примерах самые популярные составляющие модуля collections для Python 3 (проверено на 3.6). Для начала импортируйте библиотеку:

Счётчик (Counter)

Одна из распространённых задач, для которой начинающие питонисты придумывают собственные решения, – подсчёт элементов последовательности: списка, строки символов и т. д.

Функция принимает итерируемый аргумент и возвращает словарь, в котором ключами служат индивидуальные элементы, а значениями – количества повторений элемента в переданной последовательности. Посчитаем, сколько раз встречается каждая буква в слове «абракадабра»:

Обращение к ключам происходит аналогично обычному словарю:

Если элемент отсутствовал в последовательности, при обращении по ключу счётчик не вызовет исключение, а вернет нулевое значение:

Присвоение нуля ключу не удаляет это значение, а создаёт соответствующую пару:

В качестве аргумента конструктор принимает не только последовательность, но и словарь, содержащий результаты подсчёта:

Метод elements() преобразует результаты подсчета в итератор:

Метод most_common(n) ищет n самых повторяющихся элементов. Найдём для примера три наиболее частых символа:

Счётчики складываются и вычитаются друг из друга:

Операнд & даст минимальные значения для одних и тех же подсчитываемых элементов, операнд | – максимальные:

Как видно из примера, счётчику можно передавать отрицательные значения. Однако для перечисленных операций хранятся только положительные подсчеты. Нулевые или отрицательные значения обычно приходится хранить при вычитании, что реализовано в методе subtract() :

Обратите внимание, что метод subtract() обновляет сам счётчик, а не создает новый.

Распространненные шаблоны применения Counter :

Унарные операции оставляют только положительные или отрицательные подcчёты:

Счетчик в сочетании с регулярными выражениями используется для частотного анализа текста. Давайте узнаем, какие десять слов чаще прочих встречаются в тексте «Евгения Онегина»:

Словарь со значением по умолчанию (defaultdict)

Что будет, если обратиться к словарю по ключу, которого в нем ещё нет?

Верно, исключение KeyError :

Соответствующему конструктору в качестве аргумента передается тип элемента по умолчанию:

Таким образом, для ключей, к которым происходит обращение, конструктор поставит в соответствие дефолтный элемент данного типа. В случае str – пустая строка, для целых чисел – 0 и т. д.

Можно видеть, что при таком подходе нет необходимости ни проверять наличие соответствующих ключей, ни создавать предварительно пустые списки.

Словарь с памятью порядка добавления элементов (OrderedDict)

Так как OrderedDict это упорядоченная последовательность, объекты содержат соответствующие методы, реорганизующие структуру:

Контейнер словарей (ChainMap)

При обращении к ChainMap по ключу одного из словарей, происходит поиск значения среди всех словарей, при этом нет необходимости указывать конкретный словарь:

При поиске ChainMap выводит первое найденное значение (проходя словари по очереди добавления). В том числе если в словарях несколько одинаковых ключей:

Так как ChainMap это комбинация словарей, логично, что у неё есть методы keys() и values() :

При необходимости расширить составленный ранее ChainMap можно методом new_child() :

Обратите внимание, что метод не обновляет старую структуру, а создаёт новую.

Двусторонняя очередь (deque)

Чтобы добавлять не одиночный элемент, а группу итерируемого объекта iterable используйте соответственно extend(iterable) и extendleft(iterable ).

Аналогично методу append() метод pop() для deque работает с обоих концов:

Если нужно посчитать число вхождений элемента в последовательность, применяем метод count() :

Кроме перечисленных, доступны следующие методы:

Другой шаблон применения deque – хранение последних добавленных элементов с выбрасыванием более старых. Пример компактной и быстрой реализации функции скользящего среднего:

Именованный кортеж и функция namedtuple()

namedtuple() – функция-фабрика для создания именованных кортежей. Этот тип данных похож на struct в других языках программирования:

Именованные кортежи делают код яснее – вместо индексирования составляющие объекта вызываются по явным именам. Остаётся доступной и численная индексация:

Именованные кортежи часто используются для назначения имён полей кортежам, возвращаемым модулями csv или sqlite3 :

Структура namedtuple похожа на словарь. Посредством метода _asdict можно представить те же данные в виде OrderedDict :

Чтобы вызвать значение через строковый ключ, необязательно преобразовывать namedtuple – подходит стандартная функция getattr() :

Чтобы преобразовать словарь в именованный кортеж заданного типа, достаточно распаковать его оператором ** :

Имена полей namedtuple перечислены в _fields :

С версии 3.7 можно присвоить полям значения по умолчанию.

Поскольку именованный кортеж является обычным классом Python, в него легко привнести новую функциональность или изменить старую. Например, добавим к Point расчёт гипотенузы и формат вывода данных:

Резюме

Подведём итог нашему рассказу об основных составляющих модуля collections:

А вы уже используете collections в своих проектах?

Источник

collections — Контейнерные типы данных¶

Объекты ChainMap ¶

Добавлено в версии 3.3.

Класс может использоваться для имитации вложенных областей видимости и полезен в шаблонах.

class collections. ChainMap ( *maps ) ¶

ChainMap группирует несколько dict’ов или других сопоставлений вместе для создания единого обновляемого представления. Если никакие maps не указаны, предоставляется единственный пустой словарь, так что новая цепочка всегда содержит хотя бы одно отображение.

Базовый отображения хранятся в списке. Этот список общедоступен и может быть получен или обновлён с помощью атрибута maps. Другие состояния отсутствуют.

Поисковые запросы последовательно ищут базовые сопоставления, пока не будет найден ключ. Напротив, записи, обновления и удаления работают только с первым отображением.

Поддерживаются все стандартные методы словаря. Кроме того, есть атрибут maps и метод для создания новых подчинённых контекстов и свойство для доступа всех, кроме первого отображения:

Список обновляемый пользователем отображений. Список упорядочен от первого найденного до последнего-найденного. Он единственный хранит состояние и может быть изменён для изменения найденных сопоставлений. Списки всегда должны содержать по крайней мере одно отображение.

Обратите внимание, порядок итерации ChainMap() определяется путём сканирования отображения последнего к первому:

ChainMap примеры и рецепты¶

В этом разделе приведены различные подходы к работе с цепочечными отображениями.

Пример моделирования Python’а внутреннего поиска цепи:

Пример передачи указанного пользователем параметров командной строки имеют приоритет над переменными окружения, которые, в свою очередь, имеют приоритет над значениями по умолчанию:

Пример шаблона для использования класса ChainMap для имитации вложенных контекстов:

Класс ChainMap обновляет (записывает и удаляет) только первое отображение в цепочке, в то время как поиск будет выполнять поиск по всей цепочке. Однако, если желательны глубокие записи и удаления, легко создать подкласс, который обновляет ключи, находящиеся глубже в цепочке:

Объекты Counter ¶

Инструмент счётчика предоставляет возможность удобного и быстрого подсчёта. Например:

В Counter является подклассом dict для подсчета хэшируемых объектов. Это коллекции, где элементы хранятся в качестве ключей словаря и их подсчёты хранятся в виде значений словаря. Счётчики допускают любое целое число, включая ноль или отрицательные счётчики. Класс Counter похож на мешки или мультимножества в других языках.

Элементы подсчитываются от iterable или инициализиуются другим mapping (или счётчиком):

У счётчика объектов интерфейс словаря за исключением того, что они возвращают нулевое число отсутствующих элементов вместо того, чтобы вызывать KeyError :

Установка счётчика нулём не удаляет элемент из счётчика. Чтобы удалить его используется del :

Добавлено в версии 3.1.

Счётчик объектов реализует три метода помимо тех, которые доступны для всех словарей:

Возвращает итератор над элементами, повторяющим каждый из них столько раз, сколько их количество. Элементы возвращаются в порядке первого встречного. Если количество элементов меньше, чем один, elements() будет игнорировать его.

Добавлено в версии 3.2.

Обычные методы словаря доступны для Counter объектов, за исключением двух, которые для счётчиков работают по-другому.

Метод класса не применяется для Counter объектов.

Общие шаблоны для работы с объектами Counter :

Для объединения предусмотрено несколько математических операций над Counter объектами производящих мультимножества (счётчики, которые содержат количество подсчётов больше нуля). Сложение и вычитание комбинирует счётчики, путём добавления или убаления количества соответствующих элементов. Пересечение и объединение возвращают минимум и максимум соответствующих отсчётов. Каждая операция может принимать входные данные с со знаком подсчёта, но на выходе будут исключены результаты с количеством ноль или меньше.

Унарное сложение и вычитание являются ярлыками для добавления пустого счётчика или вычитая из пустого счётчика.

Добавлено в версии 3.3: Добавлена поддержка унарного плюса, унарного минуса и мультимножественных операций.

Счётчики были в первую очередь предназначены для работы с целыми положительными числами для представления запущенных подсчётов; однако была предпринята забота о том, чтобы без необходимости не исключать их использование в случаях, требующие других типов или отрицательных значений. Чтобы помочь с этими вариантами использования, этот раздел документируют минимальные ограничения по диапазону и типу.

Статья в Wikipedia для Мультимножеств.

Для математических операций над мультимножествами и их использование, см. Knuth, Donald. The Art of Computer Programming Volume II, Section 4.6.3, Exercise 19.

Для перечисления всех различных мультимножеств определенного размера по заданному набору элементов, см. itertools.combinations_with_replacement() :

deque объектов¶

Возвращает новый объект, инициализированный двусторонней очередью (используя append() ) с данными из iterable. Если iterable не указан, новая двухсторонняя очередь будет пустой.

Двусторонние очереди являются обобщением стеков и очередей (название произносится как «дек» и является сокращением от «двухсторонняя очередь»). Поддержка двусторонней очереди потокобезопасена и является эффективным по памяти при добавлении элементов с обеих сторон с примерно одинаковой сложности O(1) в любом направлении.

Объекты Deque поддерживают следующие методы:

Добавить x к правой стороне deque.

Добавить x к левой стороне deque.

Удалить все элементы из deque, оставив его с 0 длиной.

Создать поверхностную копию deque.

Добавлено в версии 3.5.

Подсчитать количество элементов deque, равное x.

Добавлено в версии 3.2.

Расширить правую часть deque, добавив элементы из итерационного аргумента.

Расширить левую часть deque, добавляя элементы из iterable. Обратите внимание, при добавлении последовательности с левой стороны приводит к обратному порядку следования элементов в итерируемом аргументе.

Вернуть позиции x в deque (или после индекса start и до индекса stop). Возвращает первое совпадение или поднимает ValueError если не найдено.

Добавлено в версии 3.5.

Вставить x в deque в позиции i.

Добавлено в версии 3.5.

Добавлено в версии 3.2.

Повернуть deque n шагов вправо. Если n отрицательный, повернуть налево.

Объекты deque также предоставить один атрибут только для чтения:

Максимальный размер deque или None если неограниченно.

Добавлено в версии 3.1.

deque рецепты¶

В этом разделе приведены различные подходы к работе с двусторонней очередью.

Ограниченная длина двусторонней очередью обеспечить функциональность, аналогичную фильтру tail в Unix:

Ещё один подход к использованию двусторонней очереди — сохранить последовательность недавно добавленные элементы, добавляя справа и выталкивая слева:

Метод rotate() предоставляет возможность реализовать deque нарезки и удаления. Например, чистая реализация Python del d[n] опирается на rotate() метод для установки элементов, чтобы быть очищеными:

Объекты defaultdict ¶

Возвращает новый словарь-объект. defaultdict является подклассом встроенного dict класса. Он переопределяет один метод и добавляет одну записываемою переменную сущности. Остальные функции такие, как для dict класс и здесь не рассматриваются.

defaultdict объекты поддерживают следующий метод в дополнение к стандартным операциям dict :

Если вызов default_factory поднимает исключение, это исключение распространяется без изменений.

defaultdict объекты поддерживают следующую переменную экземпляра:

Примеры defaultdict ¶

Установка default_factory в int делает defaultdict полезной для подсчёта (например, пакеты или мультимножество в других языках):

Когда символ появился впервые, он отсутствует в отображении, поэтому функция default_factory вызывает int() установив счётчик по умолчанию, равное нулю. Операции инкремента затем увеличивает счётчик для каждой буквы.

Установка default_factory в set делает defaultdict полезным для построения словаря множеств:

Функция фабрика namedtuple() для кортежей с именованными полями¶

Именованные кортежи присваивают значение каждой позиции в кортеже и позволяют сделать его более читабельным и самодокументируемым кодом. Их можно использовать везде, где используются обычные кортежи, и они добавляют возможность доступа к полям по имени, а не по индексу позиции.

collections. namedtuple ( typename, field_names, *, rename=False, defaults=None, module=None ) ¶

Любой допустимый идентификатор Python может быть использован для имени поля, за исключением имён, начинающиеся с подчеркивания. Допустимые идентификаторы состоят из букв, цифр и символов подчеркивания, но не начинаться с цифры или знака подчеркивания и не может быть keyword таким как class, for, return, global, pass или raise.

Если module определяет атрибут __module__ именованный кортеж становится равным этому значению.

Им сущности кортежа не содержат словарей для каждого экземпляра, поэтому они лёгкие и не требуют много памяти, чем обычные кортежи.

Изменено в версии 3.1: Добавлена поддержка для rename.

Изменено в версии 3.6: Добавлен параметр module.

Именованные кортежи особенно полезны для присвоения имён полей в результирующем кортеже, возвращаемого модулей csv или sqlite3 :

В дополнение к методам, унаследованным от кортежей, именовынные кортежи поддерживают три дополнительных метода и два атрибута. Чтобы избежать конфликтов с именами полей, методы и имена атрибутов начинаются с символа подчеркивания.

classmethod somenamedtuple. _make ( iterable ) ¶

Метод класса создаёт новыую сущность из существующей последовательности или итерируемости.

Возвращает новую сущность именованного кортежа заменив указанные поля новыми значениями:

Кортеж строк с перечислением имён полей. Полезно для интроспекции, а также для создания новых именованных типов кортежей из существующих именованных кортежей.

Словарь сопоставляет имена полей со значениями по умолчанию.

Для получения поля, имя которого хранится в строке, используйте getattr() функции:

Преобразовать словарь в именованный кортеж, используя оператор двойные звезды (как описано в Распаковка списка аргументов ):

Поскольку именованный кортеж — регулярный Python класс, легко добавить или изменить функциональность с подклассом. Далее добавлено вычисляемое поле и с фиксированной шириной формата печати:

В подкласс, приведённый выше, устанавливает __slots__ в пустой кортеж. Это помогает держать низкие требование памяти, предотвращая создание сущностей словарей.

Подклассы — не являются полезными для добавления новых, хранимых полей. Вместо этого, просто создайте новый именованный тип кортежа из атрибута _fields :

Докстринги могут быть настроены путём прямого присвоения поля __doc__ :

Изменено в версии 3.5: Свойство докстринг становятся доступными для записи.

См. typing.NamedTuple для того, чтобы добавить тип подсказки для кортежей. Он также обеспечивает элегантную запись используя ключевое слово class

См. types.SimpleNamespace() для изменяемых имён, основанных на базовых словарях, а не кортежах.

Модуль dataclasses предоставляет декоратор и функции для автоматического добавления генерируемой специальным методами пользовательских классов.

Объекты OrderedDict ¶

Упорядоченные словари как обычные словари, но содержат некоторые дополнительные возможности, связанные с операциями упорядочевания. Они стали менее актуальными в настоящее время, т.к. встроенный dict класс обрёл способность запоминать порядок вставки (это новое поведение стало гарантировано в Python 3.7).

Некоторые отличия от dict по-прежнему остаются:

Возвращает сущность dict подкласса, который содержит методы специализированных на перестановке упорядочивания словаря.

Добавлено в версии 3.1.

Метод popitem() упорядоченных словарей возвращает и удаляет пару (ключ, значение). Пары возвращаются в порядке LIFO если last True или порядок FIFO если false.

Переместить существующий key в любой конец упорядоченного словаря. Элемент перемещается в правый конец если last содержит значение true (по умолчанию) или к началу, если last является ложным. Поднимает KeyError если key не существует:

Добавлено в версии 3.2.

OrderedDict примеры и рецепты¶

Создать упорядоченный вариант словаря очень просто, запомнив порядок добавления ключей последний раз. Если новая запись перезаписывает существующую запись, исходное положение курсора изменяется и перемещается в конец:

В OrderedDict также будет полезен для реализации вариантов functools.lru_cache() :

UserDict объектов¶

Класс, UserDict действует как обёртка вокруг объектов словаря. Необходимость в этом классе была частично вытеснена возможностью прямого подкласса от dict ; однако, с этим классом может быть легче работать, потому что базовый словарь доступен в качестве атрибута.

class collections. UserDict ( [ initialdata ] ) ¶

В дополнение к поддержке методов и операций отображения, UserDict сущности предоставляют следующие атрибуты:

Объекты UserList ¶

Класс действует как обёртка вокруг списка объектов. Это полезный базовый класс для вашего собственного списка-как класса, который может от них наследоваться и переопределять существующие методы или добавить новые. Таким образом, можно добавлять новые варианты поведения в списках.

Потребность в этом классе была частично заменена возможностью создания подкласса непосредственно от list ; однако с этим классом может быть проще работать, поскольку базовый список доступен как атрибут.

class collections. UserList ( [ list ] ) ¶

В дополнение к поддержке методов и операций изменяемых последовательностей, UserList сущности предоставляют следующие атрибуты:

Используется настоящий list объект для хранения содержимого UserList класса.

Требования к подклассам: ожидается, что подклассы UserList будут предлагать конструктор, который может быть вызван либо без аргументов, либо с одним аргументом. Список операций, возвращающих новую последовательность, пытается создать экземпляр фактического класса реализации. Для этого предполагается, что конструктор может быть вызван с одним параметром, который представляет собой объект последовательности, используемый в качестве источника данных.

Если производный класс не желает выполнять такое требование, то все методы поддерживаемые этим классом должны быть переопределены; пожалуйста, обратитесь к информационным источникам о методах, которые нужно предоставить.

Объекты UserString ¶

Класс UserString действует как оболочка для строковых объектов. Потребность в этом классе была частично заменена возможностью непосредственного наследования от str ; однако с этим классом может быть проще работать, поскольку базовая строка доступна как атрибут.

class collections. UserString ( seq ) ¶

В дополнение к поддержке методов и операций строки, сущности UserString предоставляют следующие атрибуты:

Настоящий str объект, используемый для хранения содержимого UserString класса.

Источник