Как хранятся множества в памяти python

Обновлено: 03.07.2024

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

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

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

Ну и вполне закономерно, что объекты можно классифицировать по их типам.

Что такое динамическая типизация

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

типизированные языки;
нетипизированные (бестиповые) языки.

Нетипизированные языки в основной своей массе сосредоточены на низком уровне, где большинство программ напрямую взаимодействует с железом. Так как компьютер "мыслит" нулями и единицами, различия между строкой и, допустим, классом для него будут заключаться лишь в наборах этих самых 0 и 1. В связи с этим, внутри бестиповых языков, близких к машинному коду, возможны любые операции над какими угодно данными. Результат на совести разработчика.

Python же — язык типизированный. А, раз в нём определено понятия "типа", то должен существовать и процесс распознания и верификации этих самых "типов". В противном случае вероятны ситуации, когда логика кода окажется нарушенной, а программа выполнится некорректно.

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

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

В языке со статической типизацией такой фокус не пройдёт:

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

👍 К плюсам динамической типизации можно отнести:

1 . Создание разнородных коллекций. Благодаря тому, что в Python типы данных проверяются прямиком во время выполнения программного кода, ничто не мешает создавать коллекции, состоящие их элементов разных типов. Причём делается это легко и просто:

2 . Абстрагирование в алгоритмах. Создавая на Питоне, предположим, функцию сортировки, можно не писать отдельную её реализацию для строк и чисел, поскольку она и так корректно отработает на любом компарируемом множестве.

3 . Простота изучения. Не секрет, что изучать Питон с нуля гораздо легче, чем, например, Java. И такая ситуация будет наблюдаться не только для этой пары. Языки с динамической типизацией в большинстве своём лучше подходят в качестве учебного инструмента для новичков в программировании.

🙁 К минусам же динамической проверки типов можно отнести такие моменты, как:

1 . Ошибки. Ошибки типизации и логические ошибки на их основе. Они достаточно редки, однако зачастую весьма сложно отлавливаемы. Вполне реальна ситуация, когда разработчик писал функцию, подразумевая, что она будет принимать числовое значение, но в результате воздействия тёмной магии или банальной невнимательности, ей на вход поступает строка и …функция отрабатывает без ошибок выполнения, однако её результат, — ошибка, сам по себе. Статическая же типизация исключает такие ситуации априори.

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

Так или иначе, сказать, что "одно лучше другого" нельзя. Иначе "другого" бы не было. Динамически типизированные языки экономят уйму времени при кодинге, но могут обернуться неожиданными проблемами на этапе тестирования или, куда хуже, продакшена. Однако вряд ли кто-то будет спорить с тем, что динамический Python куда более дружелюбный для новичков, нежели статический C++.

Разница между атомарными и структурными типы данных

По одной из классификаций все типы данных в Python делятся на атомарные и ссылочные.

списки;
кортежи;
словари;
функции;
классы;

Разница между этими двумя группами уходит глубоко в корни языка. Вкратце:

Атомарные объекты, при их присваивании, передаются по значению, а ссылочные — по ссылке

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

Посмотрим, как это работает для структурных типов:

Поскольку списки — это ссылочные объекты, то вполне закономерно, что после присваивания переменной link переменной alin передалась именно ссылка на объект list-а и, при печати, на экран были выведены две одинаковые надписи.

Собственно, в этом и вся разница.

Числовые типы

"Все сущее есть Число" — сказал однажды мудрый грек по имени Пифагор. Числа — важнейший и фундаментальнейший из всех типов данных для всех языков программирования. В Python для их представления служит числовой тип данных.

int (целое число)

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

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

float (число с плавающей точкой)

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

print(0.3 + 0.3 + 0.3) > 0.8999999999999999 print(0.3 * 3 == 0.9) > False

В плане записи, float ничем не отличаются от int :

В плане использования — тоже, разве что в любых мало-мальски серьёзных вычислениях без float никуда.

complex (комплексное число)

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

В Python комплексные числа задаются с помощью функции complex() :

Помните, что операция сравнения для комплексных чисел не определена:

Комплексные числа широко применяются, например, для решения дифференциальных уравнений.

bool (логический тип данных)

В каком-то смысле наиболее простой и самый понятный из всех типов данных. У bool есть всего два значения:

Однако за этой простотой кроется колоссальный пласт теории в виде булевой алгебры.

Переменные логического типа нужны для реализации ветвлений, они применяются для установки флажков, фиксирующих состояния программы, а также используются в качестве возвращаемых значений для функций, названия которых, зачастую, начинаются на "is" (isPrime, isEqual, isDigit). То есть тех, которые, на человеческом языке, отвечали бы на вопрос одним словом "Да" или "Нет".

Последовательности

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

str (строка)

Строки, пожалуй, единственный объект, который может сравниться по степени своей используемости с числовым типом данных. Тавтологическое, но полное определение, справедливое для Python звучит так:

строка — это последовательность односимвольных строк.

Важность строк велика в первую очередь для людей, ведь понятно, что вся письменная речь может рассматриваться, как множество строк. А так как человеку свойственно обмениваться информацией именно в виде набора слов, то можно говорить о практически неограниченном количестве областей применения строкового типа данных. Строки, строки everywhere!

list (список)

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

Само название списков говорит об их предназначении быть объектами для хранения наборов данных. Список покупок, подарков, результатов матчей, ip клиентов или объектов типа Student. Списки в Python — это эдакие массивы из прочих языков "на максималках".

tuple (кортеж)

Кортежи в языке Python можно рассматривать, как неизменяемые списки со всеми вытекающими:

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

dict (словарь)

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

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

set (множество)

Ещё один "набор, но не последовательность".

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

Работа с файлами, хранящимися где-то на внешнем носителе, в Python реализована в виде объектов-файлов. Они относятся к объектам базового типа, но обладают весьма характерной чертой: нельзя создать экземпляр объекта-файла при помощи литералов.

Чтобы начать работу с файлами, нужно вызвать функцию open() и передать ей в качестве аргументов имя файла из внешнего источника и строку, описывающую режим работы функции:

Операции с файлами могут быть разными, а, следовательно, разными могут быть и режимы работы с ними:

r — выбирается по умолчанию, означает открытие файла для чтения;
w — файл открывается для записи (если не существует, то создаётся новый);
x — файл открывается для записи (если не существует, то генерируется исключение);
a — режим записи, при котором информация добавляется в конец файла, а не затирает уже имеющуюся;
b — открытие файла в двоичном режиме;
t — ещё одно значение по умолчанию, означающее открытие файла в текстовом режиме;
+ — читаем и записываем.

range object (a type of iterable)

Крутая особенность языка Python состоит в наличии в нём встроенной функции range() , которая способна генерировать непрерывную последовательность целых чисел:

Она крайне удобна для создания циклов for .

None — специальный объект внутри Питона. Он означает пустоту, всегда считается "Ложью" и может рассматриваться в качестве аналога NULL для языка C/С++. Помимо этого, None возвращается функциями, как объект по умолчанию.

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

Работа с типами в Python

Как проверить тип данных

Нет ничего проще, чем узнать тип данных объекта в Python:

Как поменять тип данных

В богатом арсенале Питона есть встроенные функции для приведения типов — int() , list() , set() , tuple() , str() , bin() .

☝️ Обратите внимание : встроенная функция для приведения типа не модифицирует переданное значение, а возвращает новое значение другого типа.

Отличие type() от isinstance()

В отличие от type() , функция isinstance() возвращает не тип данных аргумента, а булево значение, говорящее о том, принадлежит объект к определенному классу или нет:

num = 4.44 print(isinstance(num, float)) > True

А ещё isinstance() умеет проверять принадлежность объекта хотя к одному типу из кортежа, переданного в качестве второго аргумента:

Важным отличием также является то, что isinstance() "знает" о наследовании. Функция воспринимает объект производного класса, как объект базового.

class BaseExample: pass class DerivedExample(BaseExample): pass test = DerivedExample() print(isinstance(test, BaseExample)) > True

В Python есть очень полезный тип данных для работы с множествами – это set. Об этом типе данных, примерах использования, и небольшой выдержке из теории множеств пойдёт речь далее.

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

Множество

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

Множество – это не более чем неупорядоченная коллекция уникальных элементов.

Что значит неупорядоченная? Это значит, что два множества эквивалентны, если содержат одинаковые элементы.

Элементы множества должны быть уникальными, множество не может содержать одинаковых элементов. Добавление элементов, которые уже есть в множестве, не изменяет это множество.

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

Множества в Python

Множество в Python можно создать несколькими способами. Самый простой – это задать множество перечислением его элементов в фигурных скобках:

Единственное ограничение, что таким образом нельзя создать пустое множество. Вместо этого будет создан пустой словарь:

Для создания пустого множества нужно непосредственно использовать set() :

Также в set() можно передать какой-либо объект, по которому можно проитерироваться (Iterable):

Ещё одна возможность создания множества – это использование set comprehension. Это специальная синтаксическая конструкция языка, которую иногда называют абстракцией множества по аналогии с list comprehension (Списковое включение).

Хешируемые объекты

Существует ограничение, что элементами множества (как и ключами словарей) в Python могут быть только так называемые хешируемые (Hashable) объекты. Это обусловлено тем фактом, что внутренняя реализация set основана на хеш-таблицах. Например, списки и словари – это изменяемые объекты, которые не могут быть элементами множеств. Большинство неизменяемых типов в Python (int, float, str, bool, и т.д.) – хешируемые. Неизменяемые коллекции, например tuple, являются хешируемыми, если хешируемы все их элементы.

Объекты пользовательских классов являются хешируемыми по умолчанию. Но практического смысла чаще всего в этом мало из-за того, что сравнение таких объектов выполняется по их адресу в памяти, т.е. невозможно создать два "равных" объекта.

Скорее всего мы предполагаем, что объекты City("Moscow") должны быть равными, и следовательно в множестве cities должен находиться один объект.
Этого можно добиться, если определить семантику равенства для объектов класса City :

Чтобы протокол хеширования работал без явных и неявных логических ошибок, должны выполняться следующие условия:

Хеш объекта не должен изменяться, пока этот объект существует
Равные объекты должны возвращать одинаковый хеш

Свойства множеств

Тип set в Python является подтипом Collection (про коллекции), из данного факта есть три важных следствия:

Определена операция проверки принадлежности элемента множеству
Можно получить количество элементов в множестве
Множества являются iterable-объектами

Принадлежность множеству

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

Мощность множества

Мощность множества – это характеристика множества, которая для конечных множеств просто означает количество элементов в данном множестве. Для бесконечных множеств всё несколько сложнее.

Перебор элементов множества

Как уже было отмечено выше, множества поддерживают протокол итераторов, таким образом любое множество можно использовать там, где ожидается iterable-объект.

Отношения между множествами

Между множествами существуют несколько видов отношений, или другими словами взаимосвязей. Давайте рассмотрим возможные отношения между множествами в этом разделе.

Равные множества

Тут всё довольно просто – два множества называются равными, если они состоят из одних и тех же элементов. Как следует из определения множества, порядок этих элементов не важен.

Непересекающиеся множества

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

Подмножество и надмножество

Подмножество множества S – это такое множество, каждый элемент которого является также и элементом множества S. Множество S в свою очередь является надмножеством исходного множества.

Пустое множество является подмножеством абсолютно любого множества.

Само множество является подмножеством самого себя.

Операции над множествами

Рассмотрим основные операции, опредяляемые над множествами.

Объединение множеств

Объединение множеств – это множество, которое содержит все элементы исходных множеств. В Python есть несколько способов объединить множества, давайте рассмотрим их на примерах.

Добавление элементов в множество

Добавление элементов в множество можно рассматривать как частный случай объединения множеств за тем исключением, что добавление элементов изменяет исходное множество, а не создает новый объект. Добавление одного элемента в множество работает за O(1) .

Пересечение множеств

Пересечение множеств – это множество, в котором находятся только те элементы, которые принадлежат исходным множествам одновременно.

При использовании оператора & необходимо, чтобы оба операнда были объектами типа set . Метод intersection , в свою очередь, принимает любой iterable-объект. Если необходимо изменить исходное множество, а не возращать новое, то можно использовать метод intersection_update , который работает подобно методу intersection , но изменяет исходный объект-множество.

Разность множеств

Разность двух множеств – это множество, в которое входят все элементы первого множества, не входящие во второе множество.

Удаление элементов из множества

Удаление элемента из множества можно рассматривать как частный случай разности, где удаляемый элемент – это одноэлементное множество. Следует отметить, что удаление элемента, как и в аналогичном случае с добавлением элементов, изменяет исходное множество. Удаление одного элемента из множества имеет вычислительную сложность O(1) .

Также у множеств есть метод differenсe_update , который принимает iterable-объект и удаляет из исходного множества все элементы iterable-объекта. Этот метод работает аналогично методу difference , но изменяет исходное множество, а не возвращает новое.

Симметрическая разность множеств

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

Как видно из примера выше, число 0 принадлежит обоим исходным множествам, и поэтому оно не входит в результирующее множество. Для операции симметрической разности, помимо оператора ^ , также существует два специальных метода – symmetric_difference и symmetric_difference_update . Оба этих метода принимают iterable-объект в качестве аргумента, отличие же состоит в том, что symmetric_difference возвращает новый объект-множество, в то время как symmetric_difference_update изменяет исходное множество.

Заключение

Я надеюсь, мне удалось показать, что Python имеет очень удобные встроенные средства для работы с множествами. На практике это часто позволяет сократить количество кода, сделать его выразительнее и легче для восприятия, а следовательно и более поддерживаемым. Я буду рад, если у вас есть какие-либо конструктивные замечания и дополнения.

Множество (Set) — структура данных, которая позволяет достаточно быстро (в зависимости от реализации) применить операции add , erase и is_in_set . Но иногда этого не достаточно: например, невозможно перебрать все элементы в порядке возрастания, получить следующий / предыдущий по величине или быстро узнать, сколько элементов меньше данного есть в множестве. В таких случаях приходится использовать Упорядоченное множество (ordered_set). О том, как оно работает, и какие реализации есть для питона — далее.

Стандартный Set

В языке Python есть стандартная стукрура set, реализованная с помощью хэш-таблиц. Такую структуру обычно называют unordered_set . Данный метод работает так: каждый элемент присваивается какому-то классу элементов (например, класс элементов, имеющих одинаковый остаток от деления на модуль). Все элементы каждого класса хранятся в отдельном списке. В таком случае мы заранее знаем, в каком списке должен находиться элемент, и можем за короткое время выполнить необходимые операции. Равновероятность каждого остатка от деления случайного числа на модуль позволяет сказать, что к каждому классу элементов будет относиться в среднем size / modulo элементов.

Но хэш-таблица не позволяет выполнить операцию count_lower или подобные, поэтому придётся использовать другие структуры данных.

Что есть в других языках

В языке c++ есть структура std::set , которая поддерживает операции изменения, проверку на наличие, следующий / предыдущий по величине элемент, а также for по всем элементам. Но тут нет операций получения элемента по индексу и индекса по значению, так что надо искать дальше (индекс элемента — количество элементов, строго меньших данного)

И решение находится достаточно быстро: tree из pb_ds . Эта структура в дополнение к возможностям std::set имеет быстрые операции find_by_order и order_of_key , так что эта структура — именно то, что мы ищем.

Таким образом, целью этой статьи станет поиск аналога этой структуры в Python.

Как будем тестировать скорость работы структур данных

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

Добавление в множество миллиона случайных чисел (при данном сиде среди них будет 999'936 различных)
Проверка миллиона случайных чисел на присутствие в множестве
Прохождение циклом по всем элементам в порядке возрастания
В случайном порядке для каждого элемента массива узнать его индекс (а, соответственно, и количество элементов, меньше данного)
Получение значения i-того по возрастанию элемента для миллиона случайных индексов
Удаление всех элементов множества в случайном порядке

SortedSet.sorted_set.SortedSet

Пакет с многообещающим названием. Используем pip install sortedset

К сожалению, автор не приготовил нам функцию add и erase в каком-либо варианте, поэтому будем использовать объединение и вычитание множеств

Протестируем пока на множествах размера 10'000:

Задача	Время работы
Добавление	16.413
Проверка на наличие	0.018
Цикл по всем элементам	0.001
Получение индексов	0.008
Получение значений по индексам	0.015
Удаление	30.548

Как так получилось? Давайте загляем в исходный код:

Как оказалось, это обычный массив, в котором наличие элемента определяется бинпоиском. Это действительно отсортированное множество, но очень ленивое.

Вывод: почти бесполезно, несколько строчек кода завернули в класс

sortedcontainers.SortedSet

Внеший пакет, для установки можно использовать pip install sortedcontainers . Посмотрим же, что он нам покажет

Задача	Время работы
Добавление	3.924
Проверка на наличие	1.198
Цикл по всем элементам	0.162
Получение индексов	3.959
Получение значений по индексам	4.909
Удаление	2.933

Но, не смотря на это, кажется мы нашли то, что искали! Все операции выполняются за приличное время. По сравнению с ordered_set некоторые операции выполняются дольше, но зато операция discard выполняется не за o(n), что очень важно для возможности использования этой структуры.

Также пакет нам предлагает SortedList и SortedDict , что тоже может быть полезно.

И как же оно работает?

На странице пакета мы можем прочитать, что реализована структура не так, как мы предполагали в начале статьи.

Из-за особенностей реализации языка Python, в нём быстро работают list , а также bisect.insort (найти бинарным поиском за o(log n) место, куда нужно вставить элемент, а потом вставить его туда за o(n) ). Insert работает достаточно быстро на современных процессорах. Но всё-таки в какой-то момент такой оптимизации не хватает, поэтому структуры реализованы как список списков. Создание или удаление списков происходит достаточно редко, а внутри одного списка можно выполнять операции даже за быструю линию.

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

Проблема с ordered_set

Что вообще такое упорядоченное множество? Это множество, в котором мы можем сравнить любые 2 элемента и найти среди них больший / меньший. В течение всей статьи под операцией сравнения воспринималась операция сравнения двух элеметнов по своему значению. Но все пакеты называющиеся ordered_set считают что один элемент больше другого, если он был добавлен раньше в множество. Так что с формулировкой ordered_set нужно быть аккуратнее и уточнять, имеется ввиду ordered set или sorted set .

Bintrees

Так есть же модуль bintrees! Это же то, что нам нужно? И да, и нет. Его разработка была приостановлена в 2020 году со словами Use sortedcontainers instead .

Пакет предлагает нам несколько структур. К сожалению, ни одна из них не поддерживает операции find_by_order и подобные, так что эти струкруты являются аналогами std::set . Посмотрим же, на что они способны:

pip install bintrees

Название AVLTree говорит само за себя, RBTree — красно-чёрное дерево, BinaryTree — несбалансированное двоичное дерево, префикс Fast означает реализацию на Cython (соответственно, необходимо наличие Visual C++ , если используется на Windows).

Задача	AVLTree	FastAVLTree	RBTree	FastRBTree	BinaryTree	FastBinaryTree
Добавление	21.946	2.285	20.486	2.373	11.054	2.266
Проверка на наличие	5.86	2.821	6.172	2.802	6.775	3.018
Цикл по всем элементам	0.935	0.297	0.972	0.302	0.985	0.295
Удаление	12.835	1.509	25.803	1.895	7.903	1.588

Результаты тестирования отчётливо показывают нам, почему использовать деревья поиска на Python — плохая идея в плане производительности. А вот в интеграции с Cython всё становится намного лучше.

Оказывается, эта структура и SortedSet очень похожи по производительности. Все 3 Fast версии структур bintrees достаточно близки, поэтому будем считать, что оттуда мы используем FastAVLTree .

Задача	SortedSet	FastAVLTree
Добавление	3.924	2.285
Проверка на наличие	1.198	2.821
Цикл по всем элементам	0.162	0.297
Получение индексов	3.959	n/a
Получение значений по индексам	4.909	n/a
Удаление	2.933	1.509

Как мы видим, AVL в полтора раза быстрее в скорости добавления элементов и почти в 2 раза быстрее в операциях удаления. Но он в те же 2 раза медленнее в проверке на наличие и цикле по всем элементам. К тому же не стоит забывать, что 2 операции он выполнять не умеет, то есть не является тем ordered_set , что мы ищем.

Что же выбрать

Мои рекомендации звучат так: если вам нужны операции find_by_order и order_of_key , то ваш единственный вариант — sortedcontainers.SortedSet . Если вам нужен только аналог std::map , то выбирайте на своё усмотрение между SortedSet и любым из fast контейнеров из bintrees , опираясь на то, каких операций ожидается больше.

Можно ли сделать что-то быстрее

Скорее нет, чем да. Использование Cython — один из самых мощных способов оптимизации, а AVL считается очень быстрым решением исходной задачи. Про остальные операции ordered_set можно сказать, что модификация красно-чёрного дерева так, чтобы оно поддерживало эти операции, вряд ли будет быстрее SortedContainers , так что смысла изобретать велосипед я не вижу.

Облачные VPS серверы от Маклауд быстрые и безопасные.

Зарегистрируйтесь по ссылке выше или кликнув на баннер и получите 10% скидку на первый месяц аренды сервера любой конфигурации!

Не слишком строгое определение множества, однако, с ним возникали проблемы даже у великих математиков.

В широком смысле, элементами множеств могут быть даже нематериальные вещи: чётные числа, несданные задачи по термодинамике, алгоритмы сортировки, любимые фильмы Юлии и Алексея и даже мысли об эклерах.

🐱 Возьмите в руки кота. Взяли? Хорошо. Теперь множество котов в ваших руках насчитывает ровно один мурлыкающий элемент. Если же пушистику вдруг не понравится, что вы его тискаете, и он выскочит из рук, то элементов внутри множества не останется. Множество, в котором нет ни одного элемента, называется пустым. Но что же там в Python?

Назначение в Python

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

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

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

Пример set-ов в Python:

Особенности set

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

👉 Немаловажным является и тот факт, что при литеральном объявлении, итерируемые объекты сохраняют свою структуру.

Отдельное python множество может включать в себя объекты разных типов:

Здесь нет никакого противоречия с математической дефиницией, так как все составляющие we_are_the_py_objects имеют вполне конкретное общее свойство, являясь объектами языка Питон.

Но не стоит забывать и внутреннее определение set-ов. Важно помнить, что list-ы и dict-ы не подходят на роль элементов множества, из-за своей изменяемой природы.

Функция set() , тем не менее, корректно обрабатывает случаи, когда ей на вход подаются списки или словари.

Однако в списках не должно быть вложенных изменяемых элементов.

Работа с set-ами

Создание

Объявим Python-множество S . Существует два способа это сделать:

Способ №1 . Воспользовавшись литералом:

Способ №2 . Применив встроенную функцию set() :

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

👉 Замечание: пустое множество создаётся исключительно через set()

Если же сделать так:

То получим пустой словарь. А если внутри фигурных скобок поместить пустую строку:

То на выходе увидим множество, состоящее из одного элемента — этой самой пустой строки.

Вполне естественно, что пустое множество, при приведении его к логическому типу, тождественно ложно:

true_or_false = set() print(bool(true_or_false)) > False

Пересечение

В программировании нередки задачи, в которых требуется найти совпадающие элементы двух коллекций. Классическое решение основано на цикле for , но нас интересует другое — то, что строится на использовании set-ов.

Добавление элемента

Для добавления нового элемента в существующий набор используем метод add(x) .

Если среди исходных объектов, составляющих set, "x" уже был, то ничего не произойдёт, и начальное множество не изменится.

Удаление и очистка

Очистить и свести уже существующий сет к пустому не составит никаких проблем благодаря методу сlear() :

Для удаления одного единственного компонента из набора в Питоне определены аж три способа.

Способ №1 . Метод remove() . Метод удаляет элемент elem из set -а. В случае отсутствия elem в наборе интерпретатор выбрасывает исключение.

Способ №2 . Метод discard() . Производит предельно схожую с remove() операцию с той лишь разницей, что, в случае отсутствия элемента в коллекции, исключение не возникает:

triangle_coord = <(0, 4), (3, 0), (-3, 0)>print(triangle_coord) > <(3, 0), (-3, 0), (0, 4)>triangle_coord.discard((0, 4)) print(triangle_coord) > <(3, 0), (-3, 0)>triangle_coord.discard((54, 55)) print(triangle_coord) >

Способ №3 . Метод pop() .

Удаляет и возвращает случайный элемент множества:

Перебор элементов

Множество, как и любую другую коллекцию, итерируем циклом for :

iterate_me = for num in iterate_me: print(num) > 1.1 1.4 1.3 1.2 1.5

Принадлежность объекта set-у

Оператор in даёт возможность проверить наличие элемента в наборе:

Сортировка множеств

Операция сортировки отсутствует для множеств Python по определению. Множество — неупорядоченный набор. Но не нужно расстраиваться. С помощью функции sorted() , вы всегда можете получить отсортированный список:

Длина множества

Размеры определенного set -а получаем функцией len() :

Операции на множествах

Самое важное в этой теме. Математические теоретико-множественные операции, что не доступны никаким другим коллекциям языка. Поехали.

Объединение

(оператор | , логическое ИЛИ )

Объединением двух множеств "X" и "Y" является такое третье множество "Z", каждый элемент которого принадлежит либо множеству "X", либо "Y".

Пересечение

(оператор & , логическое И )

Пересечением двух множеств "A" и "B" является такое третье множество "C", каждый элемент которого принадлежит и множеству "A", и множеству "B".

Разность множеств

Разностью двух множеств "O" и "P" является такое третье множество "S", каждый элемент которого принадлежит множеству "O" и не принадлежит множеству "P".

Симметрическая разность

Симметрической разностью двух множеств "M" и "N" является такое третье множество "L", каждый элемент которого принадлежит либо множеству "M", либо "N", но не их пересечению.

Помимо теоретико-множественных операций, в питоне существуют и сугубо утилитарные производные методы.

isdisjoint()

Метод определяет, есть ли у двух set-ов общие элементы:

В Python нет оператора, который бы соответствовал этому методу.

issubset()

Показывает, является ли "I" подмножеством "J" (Метод вернет True, если все элементы "I" принадлежат "J"):

Оператор < определяет, является ли одно множество строгим подмножеством другого. В большинстве ситуаций, он ведёт себя точно так же, как и <= , кроме последнего случая. Сравниваемые наборы не должны быть идентичными. Таким образом, для данного оператора не существует соответствующего метода.

issuperset()

Показывает, является ли "F" надмножеством "G":

Особенности оператора строгого надмножества > идентичны таковым у < .

print(poor_small_guy > poor_small_guy) > False

И для него в языке Python тоже не существует соответствующего метода.

Квартет методов, которые присваивают set -у результат его объединения с другим множеством. "Другое множество" передаётся методу в качестве аргумента.

update()

Изменяет исходное множество по объединению:

intersection_update()

difference_update()

symmetric_difference_update()

И, наконец, по симметрической разности:

Свойства методов и операторов

Как показано выше, данные операции, за некоторым исключением, выполнятся двумя способами: при помощи метода или соответствующего ему оператора (например union() и оператор | ). Главным и основным их различием является то, что метод может принимать в качестве аргумента не только set , но и любой итерируемый объект, в то время, как оператор требует в качестве операндов наличие фактических множеств.

Но есть и сходства. Например, важным является то, что некоторые операторы и методы позволяют совершать операции над несколькими сетами сразу:

Тем интереснее, что оператор ^ симметрической разности позволяет использовать несколько наборов, а метод symmetric_difference() — нет.

Преобразования

Конвертация строки во множество

Чтобы перевести строку во множество, достаточно представить её в виде литерала этого множества.

Конвертация списка во множество

Со списком подобный трюк не пройдет, но здесь на помощь спешит функция set() :

my_list = [2, 4, 8, 16, 32] list_to_set = set(my_list) print(list_to_set) >

Frozenset

Закончим статью описанием такой структуры данных, что максимально близка Python-множествам. Она называется Frozenset .

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

Читайте также: