#11 – Множества (set и frozenset)
Python содержит еще один формат списка, что позволяет хранить набор данных. Таким списком являются множества. В ходе урока мы научимся использовать множество «set», а также множество «frozenset».
Видеоурок
Множества схожи со списками, но имеют ряд отличий.
Во-первых, множества создаются в абсолютно случайном порядке. Вы можете разместить элементы как вам будет угодно, но они все равно будут расположены впоследствии в случайном порядке.
Во-вторых, множества не могут иметь повторяющихся элементов. Все элементы с одинаковым значением не будут выведены повторно.
Множества удобно использовать когда вы хотите удалить повторяющиеся элементы из списка, например:
some_list = [12, 56, 91, 12] set(some_list) # Результат: 12, 56, 91Также для множеств существует огромное количество операций, которые приведены ниже:
Frozenset
Frozenset — метод, что позволяет создать, которое нельзя изменять в ходе выполнения программы. Получается, что Frozenset это смесь множества и кортежа.
Весь код будет доступен после подписки на проект!Задание к уроку
Необходимо оформить подписку на проект, чтобы получить доступ ко всем домашним заданиям
Большое задание по курсу
Вам необходимо оформить подписку на сайте, чтобы иметь доступ ко всем большим заданиям. В задание входит методика решения, а также готовый проект с ответом к заданию.
PS: подобные задания доступны при подписке от 1 месяца
Исчерпывающее руководство по множествам в Python
Класс set (множество) — это одна из ключевых структур данных в Python. Она представляет собой неупорядоченную коллекцию уникальных элементов. Класс set , в некоторой степени, соответствует математическому множеству. Многие широко используемые математические операции, применимые к множествам, существуют и в Python. Часто вычисления, производимые над множествами, оказываются гораздо быстрее, чем альтернативные операции со списками. В результате, для того чтобы писать эффективный код, Python-программисту просто необходимо уметь пользоваться множествами. В этой статье я расскажу об особенностях работы с классом set в Python.
Инициализация множеств
Существует два способа создания объекта set : с использованием конструкции set(iterable) и путём помещения элементов, разделённых запятыми, в фигурные скобки — < . >. Если же при инициализации множества попытаться воспользоваться пустыми фигурными скобками — <> — тогда будет создан словарь, а не пустое множество. Для создания пустых множеств используется команда set() . Обратите внимание на то, что при инициализации множеств порядок элементов неважен, и на то, что дублирующиеся элементы в множество добавить не получится.
a = < "a", "b", "c", "d", "e", "f", "f" ># конструктору set можно передать любой итерируемый объект b = set(["a", "b", "c", "d", "e", "f"]) c = set(("a", "b", "c", "d", "e", "e", "f", "f")) # порядок элементов неважен d = set(["d", "e", "f", "a", "b", "c"]) # деструктурирование списка e = < *["a", "b", "c", "d", "e", "f"] >assert a == b == c == d == e # в одном множестве могут храниться значения разных типов f = set(["a", True, 123]) g = < "a", True, 123, True, 123 >assert f == g # set() - это множество, а <> - это словарь assert set() != <>Какие элементы можно включить в состав множества? Это могут быть только элементы иммутабельных типов. Сюда входят такие типы, как float , int , string , bool и прочие подобные. А вот мутабельные типы — списки, словари, да и сами множества, в состав множеств включать нельзя. Если вас интересуют подробности о типах данных в Python — рекомендую почитать эту статью. Учитывая вышесказанное — следующая конструкция вызовет ошибку:
< ["a", "b", "c"], True ># => TypeError: unhashable type: 'list'Но что если случается так, что в множествах надо хранить некие уникальные последовательности значений? Подробнее об этом мы поговорим в конце статьи.
Примечание об иммутабельности
Иммутабельность — это ограничение, касающееся лишь встроенных типов. На практике, чтобы объект можно было добавить в множество, или чтобы его можно было использовать в качестве ключа в словаре, этот объект всего лишь должен быть хешируемым. По умолчанию объекты пользовательских классов обладают хешем, основанным на их идентификаторах. Равенство объектов определяется по их идентификаторам. Это значит, что два объекта, идентичные в плане атрибутов, будут равны друг другу только тогда, когда они представляют один и тот же объект, или в том случае, если для них определён пользовательский оператор eq .
Если для некоего класса определён пользовательский оператор eq , то объекты этого класса перестают быть хешируемыми, если только для них не будет определён пользовательский оператор hash . Тут важно то, что если два объекта равны, то их хеши тоже должны быть равны. В противном случае при добавлении подобных объектов в словарь или в множество возникнут проблемы. Дело в том, что при проверке наличия значения в составе ключей словаря или в составе множества, проверяются и хеши и равенство объектов.
Единственный случай, когда в множестве имеет смысл хранить мутабельный объект, или когда такой объект может играть роль ключа словаря, это когда оператор проверки равенства объекта не использует его мутабельные атрибуты. Предположим, у некоего объекта имеется оператор равенства и соответствующая хеш-функция, основанные на атрибутах этого объекта. Если такой объект сначала добавить в множество, а потом поменять его, тогда хеш-значение, использованное при его сохранении, будет отличаться от текущего хеш-значения. Это — плохая практика.
Добавление элементов в множества
Существует множество способов добавления элементов в множество. Для того чтобы осуществить изменение (мутацию) множества, отдельный элемент в него можно добавить командой .add() . Итерируемый объект добавляют командой .update() , или, что то же самое, используя оператор |= :
a = set() # добавление строкового элемента a.add("hello") # Следующий код НЕ эквивалентен предыдущему. # Метод update ожидает поступления итерируемого объекта, поэтому # строка рассматривается как итерируемый объект, содержащий символы # которые и добавляются в множество a.update("hello") assert a == < 'hello', 'h', 'e', 'l', 'o' ># А тут в множество добавляются две строки, так как они размещены в списке a.update(["hi", "world"]) assert a ==
Под «мутацией» я понимаю изменение исходного объекта. Есть ещё команды, которые не изменяют исходное множество. Например — метод . union() , или его эквивалент — оператор | :
a = < "a", "b" , "c" >b = < "a", "c", "d" >assert a | b == a.union(b) == < "a", "b", "c", "d" ># исходные объекты не изменились assert a == < "a", "b" , "c" >and b ==
Явное различие поведения методов .update() и .union() можно продемонстрировать, разобрав следующий пример:
def add_to_set1(a, b): a.update(b) return a def add_to_set2(a, b): a = a.union(b) return a a = < "a", "b" , "c" >b = < "a", "c", "d" ># Исходный объект был модифицирован # и будет равен возвращённому объекту assert a == add_to_set1(a, b) a = < "a", "b" , "c" >b = < "a", "c", "d" ># Исходный объект НЕ был модифицирован # и не будет равен возвращённому объекту assert a != add_to_set2(a, b)И наконец — два множества можно конкатенировать, использовав деструктурирование:
a = < "a", "b" , "c" >b = < "a", "c", "d" >assert < *a, *b >==
Этот приём будет работать аналогично методу .union() , но я рекомендую пользоваться именно .union() .
Обратите внимание на то, что в предыдущих примерах я пользовался методом .update() , но в них можно было бы применить и оператор |= . Это значит, что a |= b ( .update() ) — это НЕ то же самое, что a = a | b (.union()) . Дело в том, что в первом фрагменте кода осуществляется изменение объекта, хранящегося в a , а во втором примере a назначается новое значение.
Удаление элементов множеств
Мы рассмотрели команды для добавления элементов в множества. Существуют похожие на них команды, применяемые при удалении элементов. Вот как эти команды можно соотнести с уже известными вам командами:
- Аналог .add() — .remove() .
- Аналог .update() — .difference_update() или -= .
- Аналог .union() — .difference() или — .
a = < "a", "b" , "c" >a.remove("b") assert a == < "a", "c" >a = < "a", "b" , "c" ># Так же, как .update(), эта команда ожидает итерируемый объект # В результате здесь удаляются "a" и "b", # а не целая строка "ab" a.difference_update("ab") assert a == < "c" >a = < "a", "b" , "c" >a.difference_update(["ab"]) # "ab" нет в составе элементов множества, поэтому ничего не удаляется assert a == < "a", "b", "c" ># Оператор -, эквивалент метода .difference(), # не модифицирует исходный объект a = < "a", "b" , "c" >b = a - < "b", "c" >assert a != b and b ==
Снова хочу обратить ваше внимание на то, что надо помнить о разнице между конструкциями вида a -= b (исходное множество изменяется) и a = a — b (исходное множество не изменяется).
Имеется и ещё несколько методов, которые могут пригодиться для удаления объектов:
- .clear() — очищает множество.
- .remove() — удаляет элемент лишь в том случае, если он существует (в противном случае выдаёт ошибку); .discard() — работает похожим образом, но, если элемента не существует, ошибку не возвращает.
- .pop() — удалит случайный элемент из множества и вернёт этот элемент.
Другие операции для работы с множествами
Одна из сильных сторон Python-множеств заключается в наличии большого количества стандартных операций, предназначенных для работы с ними. Мы обсудили команды для модификации множеств путём добавления и удаления элементов, но это — далеко не всё, что можно делать с множествами.
Пересечение множеств
Пересечением двух множеств является множество элементов, входящих в состав обоих множеств. Для выполнения этой операции используются следующие методы и операторы:
- Команды, при выполнении которых множество не меняется: .intersection() или & . Например — a.intersection(b) или a & b .
- Команды, при выполнении которых множество меняется: .intersection_update() или &= .
a = < "a", "b", "c" >b = < "b", "c", "d" >assert a & b ==
Симметрическая разность множеств или дизъюнктивное объединение
Симметрическая разность множеств — это противоположность их пересечению. Она даёт все элементы, которые не принадлежат одновременно обоим исходным множествам. Для нахождения симметрической разности множеств используются следующие методы и операторы:
- Команды, при выполнении которых множество не меняется: . symmetric_difference() или ^ . Например — a.symmmetric_difference(b) или a ^ b .
- Команды, при выполнении которых множество меняется: .symmetric_difference_update() или ^= .
a = < "a", "b", "c" >b = < "b", "c", "d" >assert a ^ b ==
Методы проверки наличия элементов в множествах, сравнение множеств
Я рассказал о том, как модифицировать множества, но они, в основном, используются для того, чтобы быстро проверять, имеются ли в них некие элементы, или нет. Подобные операции, выполняемые на списках, будут медленнее. Посмотрим на конструкции, используемые для проверки наличия элементов в множествах, и на некоторые другие полезные команды.
Проверка принадлежности элемента множеству
Вероятно, это — та операция, к которой вы будете прибегать чаще, чем к другим. Проверка наличия элемента в множестве выполняется с помощью оператора in . А проверка отсутствия элемента — с помощью оператора not in . Для таких операций над множествами, в отличие от подобных проверок, выполняемых в применении к спискам, характерна константная временная сложность — O(1). В результате, по мере роста размеров множества, не будет страдать скорость проверки наличия или отсутствия в нём неких элементов.
a = < "a", "b", "c" >assert "a" in a assert "d" not in aПроверка того, является ли одно множество подмножеством другого
Множество является подмножеством другого множества в том случае, если все элементы первого множества входят в состав второго. Например, (A, B, C) — это подмножество (A, B, C, D) . В Python подобную проверку можно провести, воспользовавшись методом .issubset() или оператором = и > .
a = < "a", "b", "c" >b = < "a", "b" >assert a.issubset(b) == (a = b and a > bПроверка того, что в двух множествах нет общих элементов
Если в множествах нет общих элементов, их называют непересекающимися множествами. В Python соответствующая проверка выполняется с помощью метода .isdisjoint() .
a = < "a", "b", "c" >b = < "a", "b" >c = < "d" ># без isdisjoint() assert len(a & c) == 0 and len(a & b) != 0 # с этим методом assert a.isdisjoint(c) and not a.isdisjoint(b)Абстракция множеств
Так же, как и в случае со списками и словарями, при работе с множествами можно воспользоваться так называемой абстракцией множеств (set comprehension). Делается это путём добавления обрабатываемого выражения в фигурные скобки и через возврат единственного мутабельного элемента на каждом проходе цикла: < for . in . > .
# преобразование списка в множество с добавлением 1 к каждому элементу assert < i+1 for i in [1, 2, 3, 4] >== < 2, 3, 4, 5 ># только чётные числа a = < i for i in range(10) if i % 2 == 0 >a.update(< -3, 100 >) # Преобразование множества в список с добавлением 1 к каждому элементу # ВНИМАНИЕ: перебирая множество, не рассчитывайте на то, что сохранится тот # порядок следования элементов, в котором они были в него добавлены print([i+1 for i in a]) # => [1, 3, 5, 101, 7, 9, -2]Хранение в множествах данных более сложных типов
Представьте, что у нас имеется цикл, на каждой итерации которого мы обходим некоторое количество узлов графа. Предположим, мы обошли граф два раза, у нас получились следующие пути:
A -> B -> D D -> C -> E -> BПотом надо быстро проверить, прошлись ли мы по определённому пути. Нужно, чтобы такая проверка проводилась бы быстро, поэтому совершенно естественным будет использовать для её реализации множество. Как это сделать, если список, из-за его мутабельности, нельзя добавить в множество? К нашему счастью, в подобных обстоятельствах можно воспользоваться кортежем, классом tuple , который, по сути, представляет собой иммутабельную версию списка. Рассмотрим пример.
Сначала создадим граф, используя словарь. Ключи словаря будут представлять узлы графа, а значения — списки узлов, в которые можно перейти из текущего узла.
# можно перейти от ключа к значениям graph =
Визуализировав это описание, я получил такой граф.
Если вы задаётесь вопросом о том, как я создал такой граф — знайте, что сделал я это, прибегнув к graphviz и написав следующий код:
from graphviz import Digraph dot = Digraph() for k in graph.keys(): dot.node(k, k) edges = [] for k, v in graph.items(): edges += [f"" for to in v] dot.edges(edges) dot.render(view=True)Теперь я займусь случайным блужданием по графу, проходя от 1 до 10 узлов, после чего сохраню результирующие пути в объекте set в виде кортежей. Посмотрим, сколько уникальных путей мы сможем сгенерировать за 100 проходов по графу:
import random def perform_random_walk(graph, n_steps): node = random.sample(list(graph), 1)[0] path = [node] for _ in range(n_steps): node = random.sample(graph[node], 1)[0] path.append(node) return tuple(path) paths = set() lengths = list(range(1, 10+1)) for _ in range(100): paths.add(perform_random_walk(graph, random.choice(lengths))) len(paths) # => 83Из 100 случайных проходов по графу 83 оказались уникальными.
А что если нас не волнует порядок узлов, а нужно лишь сохранить сведения о посещённых узлах? Тогда будет смысл хранить отдельные пути в множествах, но, как уже было сказано, множества мутабельны, помещать их в другие множества нельзя. В такой ситуации, вместо обычных множеств, описываемых классом set , можно прибегнуть к неизменяемым множествам, представленным классом frozenset . Чтобы это сделать — поработаем с кодом цикла из предыдущего примера:
paths = set() lengths = list(range(1, 10+1)) for _ in range(100): path = perform_random_walk(graph, random.choice(lengths)) paths.add(frozenset(path)) len(paths) # => 21Итоги
Множества — это полезный инструмент Python-разработчика. Они позволяют очень быстро выполнять определённые операции, что способно значительно повысить эффективность кода. Кроме того, в Python имеется немало простых и полезных методов для работы с множествами, применение которых способствует упрощению кода.
О, а приходите к нам работать? �� ��
Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.
Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.
Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.
Изучите структуру данных Python Set/Frozenset — часть 4
В этой Часть 4 серии статей о структуре данных Python мы обсудим, что такое набор, чем он отличается от других структур данных в Python, как создавать объекты набора, удалять объекты набора и методы объектов набора. .
- Набор объектов – это неупорядоченная коллекция отдельных объектов, которые можно хэшировать.
- Set автоматически удаляет повторяющиеся элементы из объекта.
- Поскольку установленные объекты неупорядочены, операции индексации и нарезки не поддерживаются.
В настоящее время существует два встроенных типа наборов.
- набор. Поскольку он является изменяемым, он не имеет хэш-значения и не может использоваться ни в качестве ключа словаря, ни в качестве элемента другого набора.
- frozenset — неизменяемый и хэшируемый — его содержимое нельзя изменить после его создания; поэтому его можно использовать как ключ словаря или как элемент другого набора.
Построить заданный объект
Создайте набор с помощью метода конструктора set() или с помощью фигурных скобок с запятой, разделяющей элементы .
ПРИМЕЧАНИЕ: вы не можете построить объект набора с помощью пустых фигурных скобок, так как это создаст объект словаря.
Установить методы
Используйте встроенную функцию dir(), чтобы вывести список доступных методов и атрибутов набора.
Добавить элементы в заданный объект
Как уже говорилось, set является изменяемым типом. Вы можете добавлять, удалять, обновлять установленный объект после его создания.
Давайте поговорим о двух установленных методах add и update.
- метод add(elem) — этот метод добавляет один элемент к заданному объекту.
- Метод update(*others). Этот метод добавляет несколько элементов к заданному объекту. Вы можете передавать изменяемые/неизменяемые объекты в качестве аргумента метода обновления.
ПРИМЕЧАНИЕ: дубликаты будут автоматически удалены.
Удалить/очистить элементы из заданного объекта
Как вы видели ранее в другой теме структуры данных (словарь), для набора также можно использовать встроенное ключевое слово del для удаления объекта набора из пространства имен (например, Память). >).
Ниже приведены методы установки объектов для удаления элементов.
- clear() — очищает все элементы, делая набор пустым. Этот метод clear() доступен в других структурах данных, обеспечивающих ту же функциональность.
- pop() — удаляет произвольные элементы.
- discard(elem) — если элемент не найден в заданном объекте, метод discard() не вызовет никаких ошибок.
- remove(elem) — то же, что и метод discard(), но вызывает KeyError, если элемент не найден.
Установить операции
Set предоставляет методы для выполнения математических операций, таких как пересечение, объединение, разность и симметричная разность. Помните «Диаграмму Венна» из школьных лет?
Мы рассмотрим приведенные ниже методы выполнения математических операций.
- союз
- перекресток
- intersection_update
- симметричная_разность
- симметричное_difference_update
- разница
- difference_update
- не пересекается
- подмножество
- выпускной набор
Союз, Пересечение, Разница, Симметричная_Разница
- union(*other) — возвращает новый набор с элементами из набора и всеми остальными.
- intersection(*other) — возвращает новый набор с элементами, общими для набора и всех остальных.
- difference(*others) — возвращает новый набор с элементами в наборе, которых нет в других.
- symmetric_difference(other) — возвращает новый набор с элементами либо из набора, либо из другого, но не из обоих.
Intersection_Update
intersection_update(*others) — обновить набор, сохранив только найденные в нем элементы и все остальные.
Обновление различий
difference_update(*others) – обновить набор, сохранив только элементы, найденные в нем, и все остальные.
Symmetric_Difference_Update
symmetric_difference_update(other) – обновляет набор, сохраняя только элементы, найденные в любом наборе, но не в обоих.
Isdisjoint, Issubset, Issuperset
- isdisjoint(other) — возвращает значение True, если в наборе нет элементов, общих с другими. Множества не пересекаются тогда и только тогда, когда их пересечение является пустым множеством.
- issubset() – проверяет, входит ли каждый элемент в набор в другой.
- issuperset() – проверяет, входит ли каждый элемент в другой в набор.
Метод Копировать()
Вы можете создать идентичную копию существующего объекта набора, используя метод copy(). Этот метод также доступен для других типов структур данных, таких как список, словарь и т. д.
Удалите заданный объект из пространства имен с помощью встроенного ключевого слова del.
Замороженный набор
- Замороженный набор является неизменяемым типом. После создания вы не можете добавлять, удалять или обновлять элементы из списка.
- Неизменяемый замороженный набор можно хешировать, его можно использовать в качестве ключа для словарей или элементов для другого объекта набора.
- Замороженный набор создается с помощью функции frozenset().
- Замороженный набор предоставляет тот же набор методов по сравнению с «набором», например union(), пересечение, копирование(), isdisjoint() и т. д.
Краткое содержание
В этой статье вы увидели, что такое набор, разницу между набором и фиксированным набором, как создавать и получать доступ к элементам набора, методы набора и т. д.
Все права защищены. © Linux-Console.net • 2019-2023
Словари и множества в Python и асимптотика стандартных операций
Понятие сложности алгоритмов уже было рассмотрено в первом семестре, в основном в работах, связанных с сортировками. Цель данной работы понять трудоемкость стандартных процедур в языке python а так же разобраться с думя мощными концепциями — множество(set) и словарь(dict).
Трудоемкость будет рассмотренна на примере встроенных методов и операций классов list, dict, set .
Список (list)
Для начала вспомним операции работы со списками.
| Операция | Пример | Трудоемкость | Замечания |
| Взятие индекса | l[i] | O(1) | |
| Сохранение элемента | l[i] = 0 | O(1) | |
| Длина | len(l) | O(1) | |
| Добавление в конец | l.append(5) | O(1) | |
| Извлечение с конца | l.pop() | O(1) | |
| Очистка списка | l.clear() | O(1) | Аналогично l = [] |
| Срез(Slice) | l[a:b] | O(b-a) | |
| Расширение | l.extend(A) | O(len(A)) | Зависит только от длины A |
| Создание | list(A) | O(len(A)) | Зависит от длины A (итерируемый объект) |
| Проверка ==, != | l1 == l2 | O(N) | |
| Присваивание в срез | [a:b] = . | O(N) | |
| Удаление элемента | del l[i] | O(N) | |
| Поиск элемента | x (not) in l | O(N) | Поиск работает за O(N) |
| Копирование списка | l.copy() | O(N) | То же самое что l[:], который O(N) |
| Удаление из списка | l.remove(..) | O(N) | |
| Извлечение элемента | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) (см. выше) |
| Экстремумы | min(l)/max(l) | O(N) | Поиск работает за O(N) |
| Обращение | l.reverse() | O(N) | |
| Итерирование | for v in l: | O(N) | |
| Сортировка | l.sort() | O(N Log N) | |
| Перемножение | k*l | O(k N) | 5*l будет за O(N), len(l)*l будет O(N**2) |
У разработчиков типа данных list Python было много вариантов каким сделать его во время реализации. Каждый выбор повлиял на то, как быстро список мог выполнять операции. Одно из решений было сделать список оптимальным для частых операций.
Индексирование и присваивание
Две частые операции — индексирование и присваивание на позицию индекса. В списках Python значения присваиваются и извлекаются из определенных известных мест памяти. Независимо от того, насколько велик список, индексный поиск и присвоение занимают постоянное количество времени и, таким образом их трудоемкость O(1).
Pop, Shift, Delete
Извлечение элемента(pop) из списка Python по умолчанию выполняется с конца, но, передавая индекс, вы можете получить элемент из определенной позиции. Когда pop вызывается с конца, операция имеет сложность O(1) , а вызов pop из любого места — O(n). Откуда такая разница?
Когда элемент берется из середины списка Python, все остальные элементы в списке сдвигаются на одну позицию ближе к началу. Это суровая плата за возможность брать индекс за O(1), что является более частой операцией.
По тем же причинам вставка в индекс — O(N); каждый последующий элемент должен быть сдвинут на одну позицию ближе к концу, чтобы разместить новый элемент. Неудивительно, что удаление ведет себя таким же образом.
Итерирование
Итерирование выполняется за O(N), потому что для итерации по N элементам требуется N шагов. Это также объясняет, почему оператор in, max, min в Python является O(N): чтобы определить, находится ли элемент в списке, мы должны перебирать каждый элемент.
Срезы
Чтобы получить доступ к фрагменту [a: b] списка, мы должны перебрать каждый элемент между индексами a и b. Таким образом, доступ к срезу — O(k), где k — размер среза. Удаление среза O(N) по той же причине, что удаление одного элемента — O(N): N последующих элементов должны быть смещены в сторону начала списка.
Умножение на int
Чтобы понять умножение списка на целое k, вспомним, что конкатенация выполняется за O(M), где M — длина добавленного списка. Из этого следует, что умножение списка равно O(N k), так как умножение k-размера списка N раз потребует времени k (N-1).
Разворот списка
Разворот списка — это O(N), так как мы должны переместить каждый элемент.
Упражнение №1
Допишите в следующем коде учаток функции, где repeat_count раз повторяется взятие операции pop по индексу pop_position. Сделается чтобы если pop_position == None то брался pop() без указания индекса. Допишите код получения массивов values1, values2, values3. Покажите преподавателю получившиеся графики.
import matplotlib.pyplot as plt import time def get_pop_time(size, repeat_count, pop_position=None): ''' size - размер списка из нулей на котором будем тестировать скорость операции pop repeat_count - количество повторений для усреднения pop_position - позиция с которой делаем pop ''' l = [0] * size start_time = time.time() # # code here # end_time = time.time() return (end_time - start_time) / repeat_count repeat_count = 1000 # code here values1 = [get_pop_time(. ) for size in range(10, 1000)] values2 = [get_pop_time(. ) for size in range(10, 1000)] values3 = [get_pop_time(. ) for size in range(10, 1000)] plt.plot(values1, label='Pop no args') plt.plot(values2, label='Pop start list') plt.plot(values3, label='Pop end list') plt.ylabel('pop time') ax = plt.subplot(111) ax.legend() plt.show()
Множество (set)
Множество в языке Python — это структура данных, эквивалентная множествам в математике. Элементы могут быть различных типов. Порядок элементов не определён.
Действия, которые можно выполнять с множеством:
- добавлять и удалять элементы,
- проверять принадлежность элемента множеству,
- перебирать его элементы,
- выполнять операции над множествами (объединение, пересечение, разность).
Операция “проверить принадлежность элемента” выполняется в множестве намного быстрее, чем в списке.
Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи.
Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (вместо этого используйте неизменяемый кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.
Задание множеств
Множество задается перечислением в фигурных скобках. Например:
A = 1, 2, 3>
Исключением явлеется пустое множество:
A = set() # A -- множество D = <> # D -- не пустое множество, а пустой словарь!
Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:
>>> A = set('qwerty') >>> print(A) 'e', 'q', 'r', 't', 'w', 'y'>.
Каждый элемент может входить в множество только один раз.
>>> A = 1, 2, 3> >>> B = 3, 2, 3, 1> >>> print(A == B) # A и B — равные множества. True >>> set('Hello') 'H', 'e', 'l', 'o'>
Работа с элементами множеств
| Операция | Значение | Трудоемкость |
|---|---|---|
| x in A | принадлежит ли элемент x множеству A (возвращают значение типа bool ) | O(1) |
| x not in A | то же, что not x in A | O(1) |
| A.add(x) | добавить элемент x в множество A | O(1) |
| A.discard(x) | удалить элемент x из множества A | O(1) |
| A.remove(x) | удалить элемент x из множества A | O(1) |
| A.pop() | удаляет из множества один случайный элемент и возвращает его | O(1) |
Как мы видим, по времени стандартные оперцаии с одним элементом множества выполняются за O(1).
Поведение discard и remove различается тогда, когда удаляемый элемент отсутствует в множестве: discard не делает ничего, а метод remove генерирует исключение KeyError . Метод pop также генерирует исключение KeyError , если множество пусто.
При помощи цикла for можно перебрать все элементы множества:
Primes = 2, 3, 5, 7, 11> for num im Primes: print(num)
Из множества можно сделать список при помощи функции list :
>>> A = 1, 2, 3, 4, 5> >>> B = list(A) [1, 2, 3, 4, 5]
Упражнение №2
Вывести на экран все элементы множества A, которых нет в множестве B.
A = set('bqlpzlkwehrlulsdhfliuywemrlkjhsdlfjhlzxcovt') B = set('zmxcvnboaiyerjhbziuxdytvasenbriutsdvinjhgik') for x in A: .
Операции с множествами, обычные для математики
| Операция | Значение | Трудоемкость |
| A | B A.union(B) | Возвращает множество, являющееся объединением множеств A и B. | O(len(A)+len(B)) |
| A | = B A.update(B) | Записывает в A объединение множеств A и B. | O(len(A)+len(B)) |
| A & B A.intersection(B) | Возвращает множество, являющееся пересечением множеств A и B. | O(min(len(A), len(B)) |
| A &= B A.intersection_update(B) | Записывает в A пересечение множеств A и B. | O(min(len(A), len(B)) |
| A — B A.difference(B) | Возвращает разность множеств A и B (элементы, входящие в A, но не входящие в B). | O(len(A)+len(B)) |
| A -= B A.difference_update(B) | Записывает в A разность множеств A и B. | O(len(A)+len(B)) |
| A ^ B A.symmetric_difference(B) | Возвращает симметрическую разность множеств A и B (элементы, входящие в A или в B, но не в оба из них одновременно). | O(len(A)+len(B)) |
| A ^= B A.symmetric_difference_update(B) | Записывает в A симметрическую разность множеств A и B. | O(len(A)+len(B)) |
| A | Возвращает True, если A является подмножеством B. | O(len(A)) |
| A >= B A.issuperset(B) | Возвращает True, если B является подмножеством A. | O(len(B)) |
| A < B | Эквивалентно A | O(len(A)) |
| A > B | Эквивалентно A >= B and A != B | O(len(B)) |
В случае, если нужно провести процедуру, затрагивающую все элементы множества, то его трудоемкость будет O(N).
Упражнение №3
Даны четыре множества:
A = set('0123456789') B = set('02468') C = set('12345') D = set('56789')
Найти элементы, принадлежащие множеству E :
Словарь (ассоциативный массив, dict)
В массиве или в списке индекс — это целое число. Традиционной является следующая ситуация:
>>> Days = ['Sunday', 'Monday', 'Tuesday', 'Wednessday', 'Thursday', 'Friday', 'Saturday'] >>> Days[0] 'Sunday' >>> Days[1] 'Monday'
А как реализовать обратное соответствие?
>>> Days['Sunday'] 0 >>> Days['Monday'] 1
При помощи списка или массива это сделать невозможно, нужно использовать ассоциативный массив или словарь.
В словаре индекс может быть любого неизменяемого типа! Индексы, как и сами хранимые значения, задаются явно:
Days = 'Sunday': 0, 'Monday': 1, 'Tuesday': 2, 'Wednessday': 3, 'Thursday': 4, 'Friday': 5, 'Saturday': 6 > >>> Days['Sunday'] 0 >>> Days['Monday'] 1 >>> Days['Yesterday'] Traceback (most recent call last): File "", line 1, in module> KeyError: 'Yesterday'
При попытке обратиться к несуществующему элементу ассоциативного массива мы получаем исключение KeyError .
Особенностью ассоциативного массива является его динамичность: в него можно добавлять новые элементы с произвольными ключами и удалять уже существующие элементы.
>>> Days['Yesterday'] = -1 >>> print(Days['Yesterday']) -1
При этом размер используемой памяти пропорционален размеру ассоциативного массива. Доступ к элементам ассоциативного массива выполняется хоть и медленнее, чем к обычным массивам, но в целом довольно быстро.
Значения ключей уникальны , двух одинаковых ключей в словаре быть не может. А вот значения могут быть одинаковыми.
>>> Days['Tomorrow'] = -1 >>> Days['Yesterday'] == Days['Tomorrow'] True
Ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа frozenset: специальный тип данных, являющийся аналогом типа set, который нельзя изменять после создания. Значением элемента словаря может быть любой тип данных, в том числе и изменяемый.
Создание словаря
Пустой словарь можно создать при помощи функции dict() или пустой пары фигурных скобок <> (вот почему фигурные скобки нельзя использовать для создания пустого множества).
Для создания словаря с некоторым набором начальных значений можно использовать следующие конструкции:
Capitals = 'Russia': 'Moscow', 'Ukraine': 'Kiev', 'USA': 'Washington'> Capitals = dict(Russia = 'Moscow', Ukraine = 'Kiev', USA = 'Washington') Capitals = dict([("Russia", "Moscow"), ("Ukraine", "Kiev"), ("USA", "Washington")]) Capitals = dict(zip(["Russia", "Ukraine", "USA"], ["Moscow", "Kiev", "Washington"]))
Также можно использовать генерацию словаря через Dict comprehensions:
Cities = ["Moscow", "Kiev", "Washington"] States = ["Russia", "Ukraine", "USA"] CapitalsOfState = state: city for city, state in zip(Cities, States)>
Это особенно полезно, когда нужно «вывернуть» словарь наизнанку:
StateByCapital = CapitalsOfState[state]: state for state in CapitalsOfState>
Операции с элементами словарей
| Операция | Значение | Трудоемкость |
| value = A[key] | Получение элемента по ключу. Если элемента с заданным ключом в словаре нет, то возникает исключение KeyError. | O(1) |
| value = A.get(key) | Получение элемента по ключу. Если элемента в словаре нет, то get возвращает None. | O(1) |
| value = A.get(key, default_value) | То же, но вместо None метод get возвращает default_value. | O(1) |
| key in A | Проверить принадлежность ключа словарю. | O(1) |
| key not in A | То же, что not key in A. | O(1) |
| A[key] = value | Добавление нового элемента в словарь. | O(1) |
| del A[key] | Удаление пары ключ-значение с ключом key. Возбуждает исключение KeyError, если такого ключа нет. | O(1) |
| if key in A: del A[key] | Удаление пары ключ-значение с предварительной проверкой наличия ключа. | O(1) |
| try: del A[key] except KeyError: pass | Удаление пары ключ-значение с перехватыванием и обработкой исключения. | O(1) |
| value = A.pop(key) | Удаление пары ключ-значение с ключом key и возврат значения удаляемого элемента.Если такого ключа нет, то возбуждается KeyError. | O(1) |
| value = A.pop(key, default_value) | То же, но вместо генерации исключения возвращается default_value. | O(1) |
| A.pop(key, None) | Это позволяет проще всего организовать безопасное удаление элемента из словаря. | O(1) |
| len(A) | Возвращает количество пар ключ-значение, хранящихся в словаре. | O(1) |
Перебор элементов словаря по ключу
for key in A: print(key, A[key])
Представления элементов словаря
Представления во многом похожи на списки, но они остаются связанными со своим исходным словарём и изменяются, если менять значения элементов словаря.
- Метод keys возвращает представление ключей всех элементов.
- Метод values возвращает представление всех значений.
- Метод items возвращает представление всех пар (кортежей) из ключей и значений.
>>> A = dict(a='a', b='b', c='c') >>> k = A.keys() >>> v = A.values() >>> k, v (dict_keys(['c', 'b', 'a']), dict_values(['c', 'b', 'a'])) >>> A['d'] = 'a' >>> k, v (dict_keys(['d', 'c', 'b', 'a']), dict_values(['a', 'c', 'b', 'a']))
Учтите что итерироваться по представлениям изменяя словарь нельзя
>>> for key in A.keys(): . del A[key] . Traceback (most recent call last): File "", line 1, in module> RuntimeError: dictionary changed size during iteration
Можно, если в начале скопировать представление в список
>>> for key in list(A.keys()): . del A[key] . >>> A <>
Пример использования словаря
# Создадим пустой словать Capitals Capitals = dict() # Заполним его несколькими значениями Capitals['Russia'] = 'Moscow' Capitals['Ukraine'] = 'Kiev' Capitals['USA'] = 'Washington' # Считаем название страны print('В какой стране вы живете?') country = input() # Проверим, есть ли такая страна в словаре Capitals if country in Capitals: # Если есть - выведем ее столицу print('Столица вашей страны', Capitals[country]) else: # Запросим название столицы и добавим его в словарь print('Как называется столица вашей страны?') city = input() Capitals[country] = city
Трудоемкость стандартных операций
Второй основной тип данных Python — это словарь. Как вы помните, словарь отличается от списка возможностью доступа к элементам по ключу, а не позиции. На данный момент наиболее важной характеристикой является то, что получение и присваивание элемента в словаре являются операциями за O(1).
Мы не будем пытаться пока дать интуитивное объяснение этому, но будьте уверены, что позже мы обсудим реализации словарей. Пока просто помните, что словари были созданы специально для того, чтобы как можно быстрее получить и установить значения по ключу.
Другая важная операция словаря — проверка наличия ключа в словаре. Операция contains также работает за O(1) (в случае со списками это занимало O(N)), потому что проверка для данного ключа подразумевает простое получение элемента по ключу, которое делается за O(1).
Когда нужно использовать словари
Словари нужно использовать в следующих случаях:
- Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
- Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря Num[‘January’] = 1; Num[‘February’] = 2; .
- Установка соответствия между объектами (например, “родитель—потомок”). Ключ — объект, значение — соответствующий ему объект.
- Если нужен обычный массив, но при этом масимальное значение индекса элемента очень велико, но при этом будут использоваться не все возможные индексы (так называемый “разреженный массив”), то можно использовать ассоциативный массив для экономии памяти.
Практическая работа по использованию словарей
Упражнение №4. Подсчет слов
Дан текст на некотором языке. Требуется подсчитать сколько раз каждое слово входит в этот текст и вывести десять самых часто употребяемых слов в этом тексте и количество их употреблений.
В качестве примера возьмите файл с текстом лицензионного соглашения Python /usr/share/licenses/python/LICENSE .
Подсказка №1: Используйте словарь, в котором ключ — слово, а знчение — количество таких слов.
Подсказка №2: Точки, запятые, вопросы и восклицательные знаки перед обработкой замените пробелами(используйте punctuation из модуля string).
Подсказка №3: Все слова приводите к нижнему регистру при помощи метода строки lower() .
Подсказка №4: По окончании сбора статистики нужно пробежать по всем ключам из словаря и найти ключ с максимальным значением.
Упражнение №5. Перевод текста
Дан словарь task4/en-ru.txt с однозначным соответствием английских и русских слов в таком формате:
cat — кошка
dog — собака
mouse — мышь
house — дом
eats — ест
in — в
too — тоже
Здесь английское и русское слово разделены двумя табуляциями и минусом: ‘\t-\t’ .
В файле task4/input.txt дан текст для перевода, например:
Mouse in house. Cat in house.
Cat eats mouse in dog house.
Dog eats mouse too.
Требуется сделать подстрочный перевод с помощью имеющегося словаря и вывести результат в output.txt . Незнакомые словарю слова нужно оставлять в исходном виде.
Упражнение №6. Страны и Языки
Дан список стран и языков на которых говорят в этой стране в формате : . в файле task5/input.txt. На ввод задается N — длина списка и список языков. Для каждого языка укажите, в каких странах на нем говорят.
| Ввод | Вывод |
|---|---|
| 3 | |
| азербайджанский | Азербайджан |
| греческий | Кипр Греция |
| китайский | Китай Сингапур |
Упражнение №7*. Сделать русско-английский словарь
В файле task6/en-ru.txt находятся строки англо-русского словаря в таком формате:
cat — кошка
dog — собака
home — домашняя папка, дом
mouse — мышь, манипулятор мышь
to do — делать, изготавливать
to make — изготавливать
Здесь английское слово (выражение) и список русских слов (выражений) разделены двумя табуляциями и минусом: ‘\t-\t’ .
Требуется создать русско-английский словарь и вывести его в файл ru-en.txt в таком формате:
делать — to do
домашняя папка — home
изготавливать — to do, to make
кошка — cat
манипулятор мышь — mouse
мышь — mouse
собака — dog
Порядок строк в выходном файле должен быть словарным с человеческой точки зрения (так называемый лексикографический порядок слов). То есть выходные строки нужно отсортировать.
Упражнение №8*. Синхронизация словарей
Даны два файла словарей: task7/en-ru.txt и task7/ru-en.txt (в формате, описанном в упражнении №6).