Множества и словари в Python
Множество ( set ) — встроенная структура данных языка Python, имеющая следующие свойства:
- множество — это коллекция Множество содержит элементы
- множество неупорядоченно Множество не записывает (не хранит) позиции или порядок добавления его элементов. Таким образом, множество не имеет свойств последовательности (например, массива): у элементов множества нет индексов, невозможно взять срез множества.
- элементы множества уникальны Множество не может содержать два одинаковых элемента.
- элементы множества — хешируемые объекты (hashable objects) В Python множество set реализовано с использованием хеш-таблицы. Это приводит к тому, что элементы множества должны быть неизменяемыми объектами. Например, элементом множества может быть строка, число, кортеж tuple , но не может быть список list , другое множество set .
Эти свойства множеств часто используются, чтобы проверять вхождение элементов, удаление дубликатов из последовательностей, а также для математических операций пересечения, объединения, разности.
Создание и изменение множества
Запустите в терминале Python в интерпретируемом режиме и проработайте примеры ниже.
Пустое множество создаётся с помощью функции set
>>> A = set() >>> type(A) >>> len(A) 0 >>> A set()
Обратите внимание, что размер множества множества можно получить с помощью функции len .
Добавим несколько элементов
>>> A.add(1) >>> A >>> A.add(2) >>> A >>> A.add(2) >>> A
Заметьте, что повторное добавление не имеет никакого эффекта на множество.
Также, из вывода видно, что литералом множества являются фигурные скобки <>, в которых через запятую указаны элементы. Так, ещё один способ создать непустое множество — воспользоваться литералом
>>> B = 1, 2> >>> B
При попытке добавления изменяемого объекта возникнет ошибка
>>> B.add([3,4,5]) Traceback (most recent call last): File "", line 1, in TypeError: unhashable type: 'list'
Здесь произошла попытка добавить массив в множество B.
У операции добавления set.add существует обратная — операция удаления set.remove
>>> B >>> B.remove(1) >>> B >>> B.remove(3) Traceback (most recent call last): File "", line 1, in KeyError: 3
При попытке удаления элемента, не входящего в множество, возникает ошибка KeyError .
Однако, существует метод set.discard , который удаляет элемент из множества, только в том случае, если этот элемент присутствовал в нём.
Математические операции
Множества Python поддерживают привычные математические операции
Проверки
Чтобы проверить вхождение элемента в множество используйте логический оператор in
>>> B = 1, 2> >>> B >>> 3 in B False
Асимптотика x in set — O(1).
Стоит отметить, что оператор in работает и с другими коллекциями. Например, можно проверять вхождение подстроки в строку ‘AA’ in ‘bbAAcc’ или вхождение элемента в массив 5 in [1, 2, 5, 6] . Асимптотики в данном случае нужно уточнять в документации.
>>> A = 1, 2, 3> >>> B = 1, 2, 3> >>> A == B True >>> B.add(4) >>> A >>> B >>> A == B False
Проверка на нестрогое подмножество set.issubset
>>> A >>> B >>> A.issubset(B) True >>> B.issubset(A) False >>> A.issubset(A) True
Проверка на нестрогое надмножество set.issuperset
>>> A >>> B >>> A.issuperset(B) False >>> B.issuperset(A) True >>> B.issuperset(B) True
Операции получения новых множеств
>>> A = 1, 2, 4> >>> B = 1, 2, 3> >>> A.union(B) # union — объединение множеств >>> A.intersection(B) # intersection — пересечение >>> A.difference(B) # difference — разность множеств >>> B.difference(A) >>> A.symmetric_difference(B) # symmetric_difference — симметрическая разность >>> B.symmetric_difference(A)
Сводная таблица по множествам (cheatsheet)
Кроме того, у операций, порождающих новые множества, существует inplace варианты. Для методов это те же названия, только с префиксом _update, а для соответствующих операторов добавляется знак равенства =. Ниже показан вариант для операции разности множеств
>>> A = 1, 2, 3, 4> >>> B = 2, 4> >>> A.difference_update(B) >>> A >>> A = 1, 2, 3, 4> >>> B = 2, 4> >>> A -= B >>> A
Неизменяемые множества
В Python существует неизменяемая версия множества — frozenset . Этот тип объектов поддерживает все операции обычного множества set , за исключением тех, которые его меняют.
Неизменяемые множества являются хешируемыми объектами, поэтому они могут быть элементами множества set . Так можно реализовать, например, множество множеств, где множество set состоит из множеств типа frozenset .
Для создания frozenset используется функция frozenset(iterable) , в качестве аргумента принимающая итерирумый объект.
>>> FS = frozenset(1, 2, 3>) >>> FS frozenset() >>> A = 1, 2, 4> >>> FS & A frozenset() >>> A & FS
В этом примере показано создание frozenset из обычного множества . Обратите внимание на тип возвращаемого объекта для операции пересечения & . Возвращаемый объект имеет тип, соответствующий типу первого аргумента. Такое же поведение будет и с другими операциями над множествами.
Словари Python
Словарь (dictionary) в Python — это ассоциативный массив, реализовать который вы пробовали на прошлом занятии. Ассоциативный массив это структура данных, содержащая пары вида ключ:значение. Ключи в ассоциативном массиве уникальны.
В Python есть встроенный ассоциативный массив — dict . Его реализация основана на хеш-таблицах. Поэтому
- ключом может быть только хешируемый объект
- значением может быть любой объект
Создание и изменение словаря
Пустой словарь можно создать двумя способами:
>>> d1 = dict() >>> d2 = <> >>> d1 <> >>> d2 <> >>> type(d1) >>> type(d2)
Добавить элемент в словарь можно с помощью квадратных скобок:
>>> domains = <> >>> domains[‘ru’] = ‘Russia’ >>> domains[‘com’] = ‘commercial’ >>> domains[‘org’] = ‘organizations’ >>> domains
Из этого примера видно, что литералом словаря являются фигурные скобки, в которых через запятую перечислены пары в формате ключ:значение . Например, словарь domains можно было создать так domains = .
Доступ к элементу осуществляется по ключу:
>>> domains['com'] 'commercial' >>> domains['de'] Traceback (most recent call last): File "", line 1, in KeyError: 'de'
Удалить элемент можно с помощью оператора del . Если ключа в словаре нет, произойдет ошибка KeyError
>>> domains >>> del domains[‘de’] Traceback (most recent call last): File «», line 1, in KeyError: ‘de’ >>> del domains[‘ru’] >>> domains
Кроме того, для добавления, получения и удаления элементов есть методы dict.setdefault , dict.get , dict.pop , которые задействует дополнительный аргумент на случай, если ключа в словаре нет
>>> d1 = <> >>> d1.setdefault(‘a’, 10) 10 >>> d1.setdefault(‘b’, 20) 20 >>> d1 >>> d1.setdefault(‘c’) >>> d1 >>> d1.setdefault(‘a’, 123) 10 >>> d1 >>> d1.get(‘a’) 10 >>> d1.get(‘d’) # вернул None >>> d1.get(‘d’, ‘NoKey’) ‘NoKey’ >>> d1.pop(‘d’) Traceback (most recent call last): File «», line 1, in KeyError: ‘d’ >>> d1.pop(‘d’, 255) 255 >>> d1 >>> d1.pop(‘a’, 255) 10 >>> d1
Примечание о числовых ключах
Ключом может являться и число: int или float . Однако при работе со словарями в Python помните, что два ключа разные, если для них верно k1 != k2 # True .
>>> d = 0: 10> >>> d >>> d[0] = 22 >>> d >>> d[0.0] = 33 >>> d >>> 0.0 != 0 False
Поэтому при возможности избегайте в качестве ключей float -объектов.
Использование DictView: циклы и множественные операции
Если попробовать пройтись в цикле по словарю, то это будет проход по ключам
>>> d = 'a': 10, 'c': 30, 'b': 20> >>> for k in d: . print(k) . a c b
Зачастую необходимо пройтись в цикле по ключам, значениям или парам ключ:значение, содержащиеся в словаре. Для этого существуют методы dict.keys() , dict.values() , dict.items() . Они возвращают специальные DictView объекты, которые можно использовать в циклах:
>>> d = 'a': 10, 'c': 30, 'b': 20> >>> for k in d.keys(): . print(k) . a c b >>> for v in d.values(): . print(v) . 10 30 20 >>> for k, v in d.items(): . print(k, v) . a 10 c 30 b 20
Объекты DictView , содержащие только ключи, ведут себя подобно множествам. Кроме того, если DictView объекты для значений или пар содержат неизменяемые объекты, тогда они тоже ведут себя подобно множествам. Это означает, что привычные для множеств операции пересечения, вхождения и другие также работают с DictView .
>>> d >>> dkeys = d.keys() >>> ‘abc’ in dkeys False >>> ‘c’ in dkeys True >>> ‘a’, ‘b’, ‘c’> == dkeys True >>> dkeys & ‘b’, ‘c’, ‘d’>
Словарь с упорядоченными ключами OrderedDict
Это может понадобится для отправки задач на ejudge.
Если внимательно просмотреть примеры на циклы выше, то видно, что порядок итерирования в циклах совпадает с порядком добавления элементов в словарь.
Однако, такое поведение у стандартных словарей dict гарантируется, начиная с версии 3.7 (лабораторные примеры были сделаны из-под версии 3.7.4). Узнать свою версию Python можно, например, из терминала python3 --version или зайдя в интерпретируемый режим (версия будет написана сверху).
Если для вашей программы важно упорядочивание элементов, но вы не знаете, какой версии интерпретатор будет исполнять ваш скрипт, то вам нужно воспользоваться упорядоченной версией словарей OrderedDict .
Она находится в стандартной библиотеке collections .
Упорядоченный словарь поддерживает все операции, что и обычный словарь.
>>> import collections >>> od = collections.OrderedDict() >>> od OrderedDict() >>> od['a'] = 10 >>> od['c'] = 30 >>> od['b'] = 20 >>> od OrderedDict([('a', 10), ('c', 30), ('b', 20)])
Сайт построен с использованием Pelican. За основу оформления взята тема от Smashing Magazine. Исходные тексты программ, приведённые на этом сайте, распространяются под лицензией GPLv3, все остальные материалы сайта распространяются под лицензией CC-BY.
Словари и множества в 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).
Архимед Python 19/20
Множество в языке Питон — это структура данных, эквивалентная множствам в математике. Множество может состоять из различных элементов, порядок элементов в множестве неопределен. В множество можно добавлять и удалять элементы, можно перебирать элементы множества, можно выполнять операции над множествами (объединение, пересечение, разность). Можно проверять принадлежность элементу множества.
В отличии от массивов, где элементы хранятся в виде последовательного списка, в множествах порядок хранения элементов неопределен (более того, элементы множества храняться не подряд, как в списке, а при помощи хитрых алгоритмов). Это позволяет выполнять операции типа “проверить принадлежность элемента множеству” быстрее, чем просто перебирая все элементы множества.
Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи. Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (но можно сделать кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.
Задание множеств
Множество задается перечислением всех его элементов в фигурных скобках. Например:
Исключением явлеется пустое множество, которое можно создать при помощи функции set() . Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:
A = set('qwerty') print(A)
Каждый элемент может входить в множество только один раз, порядок задания элементов не важен. Например, программа:
A = B = print(A == B)
выведет True , так как A и B — равные множества.
Каждый элемент может входить в множество только один раз. set(‘Hello’) вернет множество из четырех элементов: .
Работа с элементами множеств
Узнать число элементов в множестве можно при помощи функции len .
Перебрать все элементы множества (в неопределенном порядке!) можно при помощи цикла for :
C = for elem in C: print(elem)
Проверить, принадлежит ли элемент множеству можно при помощи операции in , возвращающей значение типа bool :
i in A
Аналогично есть противоположная операция not in .
Для добавления элемента в множество есть метод add :
A.add(x)
Для удаления элемента x из множества есть два метода: discard и remove . Их поведение различается только в случае, когда удаляемый элемент отсутствует в множестве. В этом случае метод discard не делает ничего, а метод remove генерирует исключение KeyError .
Наконец, метод pop удаляет из множетсва один случайный элемент и возвращает его значение. Если же множество пусто, то генерируется исключение KeyError .
Из множества можно сделать список при помощи функции list .
Перебор элементов множества
При помощи цикла for можно перебрать все элементы множества:
Primes = for num in Primes: print(num)
Операции с множествами
С множествами в питоне можно выполнять обычные для математики операции над множествами.
A | B A.union(B)
A |= B A.update(B)
A & B A.intersection(B)
A &= B A.intersection_update(B)
A - B A.difference(B)
A -= B A.difference_update(B)
A ^ B A.symmetric_difference(B)
A ^= B A.symmetric_difference_update(B)
A >= B A.issuperset(B)
A > B
Обычные списки (массивы) представляют собой набор пронумерованных элементов, то есть для обращения к какому-либо элементу списка необходимо указать его номер. Номер элемента в списке однозначно идентифицирует сам элемент. Но идентифицировать данные по числовым номерам не всегда оказывается удобно. Например, маршруты поездов в России идентифицируются численно-буквенным кодом (число и одна цифра), также численно-буквенным кодом идентифицируются авиарейсы, то есть для хранения информации о рейсах поездов или самолетов в качестве идентификатора удобно было бы использовать не число, а текстовую строку.
Структура данных, позволяющая идентифицировать ее элементы не по числовому индексу, а по произвольному, называется словарем или ассоциативным массивом. Соответствующая структура данных в языке Питон называется dict .
Рассмотрим простой пример использования словаря. Заведем словарь Capitals , где индексом является название страны, а значением — название столицы этой страны. Это позволит легко определять по строке с названием страны ее столицу.
# Создадим пустой словать 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
Итак, каждый элемент словаря состоит из двух объектов: ключа и значения. В нашем примере ключом является название страны, значением является название столицы. Ключ идентифицирует элемент словаря, значение является данными, которые соответствуют данному ключу. Значения ключей — уникальны, двух одинаковых ключей в словаре быть не может.
В жизни широко распространены словари, например, привычные бумажные словари (толковые, орфографические, лингвистические). В них ключом является слово-заголовок статьи, а значением — сама статья. Для того, чтобы получить доступ к статье, необходимо указать слово-ключ.
Другой пример словаря, как структуры данных — телефонный справочник. В нем ключом является имя, а значением — номер телефона. И словарь, и телефонный справочник хранятся так, что легко найти элемент словаря по известному ключу (например, если записи хранятся в алфавитном порядке ключей, то легко можно найти известный ключ, например, бинарным поиском), но если ключ неизвествен, а известно лишь значение, то поиск элемента с данным значением может потребовать последовательного просмотра всех элементов словаря.
Особенностью ассоциативного массива является его динамичность: в него можно добавлять новые элементы с произвольными ключами и удалять уже существующие элементы. При этом размер используемой памяти пропорционален размеру ассоциативного массива. Доступ к элементам ассоциативного массива выполняется хоть и медленнее, чем к обычным массивам, но в целом довольно быстро.
В языке Питон как ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа frozenset : специальный тип данных, являющийся аналогом типа set , который нельзя изменять после создания. Значением элемента словаря может быть любой тип данных, в том числе и изменяемый.
Когда нужно использовать словари
Словари нужно использовать в следующих случаях:
- Подсчет числа каких-то объектов. В этом случае нужно завести словарь, в котором ключами являются объекты, а значениями — их количество.
- Хранение каких-либо данных, связанных с объектом. Ключи — объекты, значения — связанные с ними данные. Например, если нужно по названию месяца определить его порядковый номер, то это можно сделать при помощи словаря Num[‘January’] = 1; Num[‘February’] = 2; . .
- Установка соответствия между объектами (например, “родитель—потомок”). Ключ — объект, значение — соответствующий ему объект.
- Если нужен обычный массив, но при этом масимальное значение индекса элемента очень велико, но при этом будут использоваться не все возможные индексы (так называемый “разреженный массив”), то можно использовать ассоциативный массив для экономии памяти.
Создание словаря
Пустой словарь можно создать при помощи функции dict() или пустой пары фигурных скобок <> (вот почему фигурные скобки нельзя использовать для создания пустого множества). Для создания словаря с некоторым набором начальных значений можно использовать следующие конструкции:
Capitals = 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 , поэтому в этом случае ключи могут быть только строками, причем являющимися корректными идентификаторами. В третьем и четвертом случае можно создавать большие словари, если в качестве аргументов передавать уже готовые списки, которые могут быть получены не обязательно перечислением всех элементов, а любым другим способом построены по ходу исполнения программы. В третьем способе функции dict нужно передать список, каждый элемент которого является кортежем из двух элементов: ключа и значения. В четвертом способе используется функция zip , которой передается два списка одинаковой длины: список ключей и список значений.
Работа с элементами словаря
Основная операция: получение значения элемента по ключу, записывается так же, как и для списков: A[key] . Если элемента с заданным ключом не существует в словаре, то возникает исключение KeyError .
Другой способ определения значения по ключу — метод get : A.get(key) . Если элемента с ключом get нет в словаре, то возвращается значение None . В форме записи с двумя аргументами A.get(key, val) метод возвращает значение val , если элемент с ключом key отсутствует в словаре.
Проверить принадлежность элемента словарю можно операциями in и not in , как и для множеств.
Для добавления нового элемента в словарь нужно просто присвоить ему какое-то значение: A[key] = value .
Для удаления элемента из словаря можно использовать операцию del A[key] (операция возбуждает исключение KeyError , если такого ключа в словаре нет. Вот два безопасных способа удаления элемента из словаря. Способ с предварительной проверкой наличия элемента:
if key in A: del A[key]
Способ с перехватыванием и обработкой исключения:
try: del A[key] except KeyError: pass
Еще один способ удалить элемент из словаря: использование метода pop : A.pop(key) . Этот метод возвращает значение удаляемого элемента, если элемент с данным ключом отсутствует в словаре, то возбуждается исключение. Если методу pop передать второй параметр, то если элемент в словаре отсутствует, то метод pop возвратит значение этого параметра. Это позволяет проще всего организовать безопасное удаление элемента из словаря: A.pop(key, None) .
Перебор элементов словаря
Можно легко организовать перебор ключей всех элементов в словаре:
for key in A: print(key, A[key])
Следующие методы возвращают представления элементов словаря. Представления во многом похожи на множества, но они изменяются, если менять значения элементов словаря. Метод keys возвращает представление ключей всех элементов, метод values возвращает представление всех значений, а метод items возвращает представление всех пар (кортежей) из ключей и значений.
Соответственно, быстро проверить, если ли значение val среди всех значений элементов словаря A можно так: val in A.values() , а организовать цикл так, чтобы в переменной key был ключ элемента, а в переменной val было его значение можно так:
for key, val in A.items(): print(key, val)
Как переделать список в значении словаря во множество?
Нужно написать функцию friends, которая из списка пар друзей сделает словарь, в котором каждому человеку будет сопоставлено множество его друзей.
friends([("Ivan", "Maria"), ("Ella", "Ivan"), ("Ivan", "Oleg")]) == \ , "Ella":, "Maria": , "Oleg": > Вот мой код:
def friends(pairs): result = dict() for pair in pairs: if pair[0] not in result: result[pair[0]] = [] if pair[1] not in result: result[pair[1]] = [] if pair[1] not in result[pair[0]]: result[pair[0]].append(pair[1]) if pair[0] not in result[pair[1]]: result[pair[1]].append(pair[0]) return result res = friends([("Ivan", "Maria"), ("Ella", "Ivan"), ("Ivan", "Oleg")]) print(res) А надо, чтобы вместо списка в значении словаря было множество:
, 'Maria': , 'Ella': , 'Oleg': > как можно преобразовать?
Отслеживать
47.5k 17 17 золотых знаков 56 56 серебряных знаков 99 99 бронзовых знаков
задан 27 окт 2020 в 19:05
17 6 6 бронзовых знаков
= [] заменить на = set() и append заменить на add
27 окт 2020 в 19:08
Помогло, благодарю
27 окт 2020 в 19:10
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
@Danis сказал, что нужно множество, за что ему спасибо — тогда код такой:
res = dict() for pair in friends: res[pair[0]] = if pair[0] not in res else res[pair[0]] | res[pair[1]] = if pair[1] not in res else res[pair[1]] |
А так не устраивает (по сути в лоб):
friends = [("Ivan", "Maria"), ("Ella", "Ivan"), ("Ivan", "Oleg")] res = dict() for pair in friends: if pair[0] in res: res[pair[0]].append(pair[1]) else: res[pair[0]] = [pair[1]] if pair[1] in res: res[pair[1]].append(pair[0]) else: res[pair[1]] = [pair[0]] print(res) или чуть покороче:
res = dict() for pair in friends: if pair[0] not in res: res[pair[0]] = [] res[pair[0]].append(pair[1]) if pair[1] not in res: res[pair[1]] = [] res[pair[1]].append(pair[0]) или еще чуть покороче:
res = dict() for pair in friends: res[pair[0]] = [pair[1]] if pair[0] not in res else res[pair[0]] + [pair[1]] res[pair[1]] = [pair[0]] if pair[1] not in res else res[pair[1]] + [pair[0]]