#8 – Функции строк. Индексы и срезы
Язык Питон обладает обширным набором функций для работы со строками. В ходе урока мы научимся использовать множество из этих функций, а также изучим тему индексов и срезов в языке Python.
Видеоурок
Индексы
Нумерация в списках начинается с нуля, так как список по большей части это просто массив, то как в обычном массиве отсчет ведется от 0. Первый элемент по индексу будет 0, второй — 1, третий — 2 и так далее. Если мы попытаемся взять несуществующий элемент, то это приведет к ошибке.
a = [0, 23, "Hi"] # Список print (a[4]) # Выдаст ошибку, так как элемента не существуетУдобной функцией языка Python является возможность брать элементы с конца при помощи отрицательных индексов. К примеру, если нам нужен второй элемент с конца, то мы можем записать это так:
a = [0, 23, "Hi", 1.56, 9] # Список print (a[-2]) # Будет выведено 1.56Срезы
Срезы позволяют обрезать список, взяв лишь те элементы, которые нужны. Они работают по следующей схеме: list[НАЧАЛО:КОНЕЦ:ШАГ] .
- Начало — с какого элемента стоит начать (по умолчанию равно 0);
- Конец — по какой элемент мы берем элементы (по умолчанию равно длине списка);
- Шаг — с каким шагом берем элементы, к примеру каждый 2 или 3 (по умолчанию каждый 1).
В срезах один, несколько или даже все параметры могут быть пропущены.
list[::3] # Берем каждый третий элемент list[2::2] # Начиная со второго элемента берем каждый второй элемент list[4:6:] # Начиная с 4 элемента берем все элементы по 6 элемент list[::] # Берем все элементыТакже могут быть использованы отрицательные числа для срезов.
Функции по работе со строками
word = 'FootBALL, baskeTball, skate' # print(word.count('!')) # print(word.capitalize()) # print(word.find('pr')) hobby = word.split(', ') for i in range(len(hobby)): hobby[i] = hobby[i].capitalize() result = ", ".join(hobby) print(result)Посмотреть остальной код можно после подписки на проект!Задание к уроку
Необходимо оформить подписку на проект, чтобы получить доступ ко всем домашним заданиям
Большое задание по курсу
Вам необходимо оформить подписку на сайте, чтобы иметь доступ ко всем большим заданиям. В задание входит методика решения, а также готовый проект с ответом к заданию.
PS: подобные задания доступны при подписке от 1 месяца
Также стоит посмотреть
Комментарии (8)
Николай 15 марта 2023 в 18:59
Какое отношение первое задание имеет к этой тем. В уроке функция enumate вообще не рассматривалась.
Anna 10 февраля 2023 в 17:06
Выведите в списке третий элемент с конца
list_2 = [3.4, 56, «Some», «Hi», 7, 3.8, 44]
print(list_2[-3])
Anna 10 февраля 2023 в 17:03
используйте функцию enumerate.
Anna 10 февраля 2023 в 17:03
Выведите каждый 3 элемент списка начиная с первого и заканчивая предпоследним.
list = [3.4, 56, «Some», «Hi», 7, 3.8, 44]
print(list[:-1:3])
Муса 04 февраля 2023 в 19:44
У вас написано list[2::2] # Начиная со ВТОРОГО элемента. А там с третьего
Zakhar 21 января 2023 в 22:50
import random print("Welcome to casino XBET!") user_logins = [''] user_passwords = [''] user_choose = input(('Choose registration or log into: ')) if user_choose == 'registration': user_logins.append(input('Create your login: ')) user_passwords.append(input('Create your password: ')) user_enter_login = input('Enter your login: ') if user_enter_login in user_logins: print('The login is Wright') else: print('The login is wrong') user_enter_password = input('Enter your password: ') if user_enter_password in user_passwords: print("The password is right") else: print('The password is wrong') elif user_choose == 'log into': user_enter_login = input('Enter your login: ') if user_enter_login in user_logins: print('The login is Wright') else: print('The login is wrong') user_enter_password = input('Enter your password: ') if user_enter_password in user_passwords: print("The password is right") else: print('The password is wrong') else: exit() balance = 100 print('Your balance = ', balance) while balance > 0: user_num = int(input("Enter your number 1-10: ")) if user_num == random.randrange(1,10): balance += 10 print('You won 10 USD') print('Your balnce is: ', balance) else: balance -= 10 print("You lose 10 USD") print("Your balance is: ", balance)
Сделал мини казино с тех знаний которые получил
Борис 18 июля 2023 в 15:39
Антон 12 ноября 2023 в 21:42
Shakhboz 24 декабря 2022 в 17:35
What is enumerate? At least, explain in text. There is nothing about it in the video. Thanks!
Андрей 20 октября 2022 в 12:19
enumerate вообще никак не объясняется в видео. Чтобы решить задание, нужно искать инфу в инете. Странный подход к обучению)
Списки, словари и множества в Python
У разработчиков типа данных 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), так как мы должны переместить каждый элемент.
2. Множества
Множество (set)
Множество в языке Python — это структура данных, эквивалентная множествам в математике. Элементы могут быть различных типов. Порядок элементов не определён.
Действия, которые можно выполнять с множеством:
- добавлять и удалять элементы,
- проверять принадлежность элемента множеству,
- перебирать его элементы,
- выполнять операции над множествами (объединение, пересечение, разность).
Операция “проверить принадлежность элемента” выполняется в множестве намного быстрее, чем в списке.
Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи.
Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (вместо этого используйте неизменяемый кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.
Задание множеств
Множество задается перечислением в фигурных скобках. Например:
Исключением явлеется пустое множество:
A = set() # A -- множество D = <> # D -- не пустое множество, а пустой словарь!
Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:
>>> A = set('qwerty') >>> print(A) .
Каждый элемент может входить в множество только один раз.
>>> A = >>> B = >>> print(A == B) # A и B — равные множества. True >>> set(‘Hello’)
Работа с элементами множеств
| Операция | Значение | Трудоемкость |
|---|---|---|
| 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 = for num im Primes: print(num)
Из множества можно сделать список при помощи функции list :
>>> A = >>> 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 A.issubset(B) | Возвращает 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. Словари
Словарь (ассоциативный массив, 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 KeyError: 'Yesterday'
При попытке обратиться к несуществующему элементу ассоциативного массива мы получаем исключение KeyError .
Особенностью ассоциативного массива является его динамичность: в него можно добавлять новые элементы с произвольными ключами и удалять уже существующие элементы.
>>> Days['Yesterday'] = -1 >>> print(Days['Yesterday']) -1
При этом размер используемой памяти пропорционален размеру ассоциативного массива. Доступ к элементам ассоциативного массива выполняется хоть и медленнее, чем к обычным массивам, но в целом довольно быстро.
Значения ключей уникальны , двух одинаковых ключей в словаре быть не может. А вот значения могут быть одинаковыми.
>>> Days['Tomorrow'] = -1 >>> Days['Yesterday'] == Days['Tomorrow'] True
Ключом может быть произвольный неизменяемый тип данных: целые и действительные числа, строки, кортежи. Ключом в словаре не может быть множество, но может быть элемент типа frozenset: специальный тип данных, являющийся аналогом типа set, который нельзя изменять после создания. Значением элемента словаря может быть любой тип данных, в том числе и изменяемый.
Создание словаря
Пустой словарь можно создать при помощи функции 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 comprehensions:
Cities = [«Moscow», «Kiev», «Washington»] States = [«Russia», «Ukraine», «USA»] CapitalsOfState =
Это особенно полезно, когда нужно «вывернуть» словарь наизнанку:
StateByCapital =
Операции с элементами словарей
| Операция | Значение | Трудоемкость |
| 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 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. Задача №3768. Контрольная по ударениям
Вариант 1. Используем множество
Вариант 2. Используем словарь
Множества и словари в 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)
- elem — Python-объект
- A — множество set
- B, C. 1. В случае использования в методахA.method_name(B, C. ) : B, C. являются любыми итерируемыми объектами. Методы допускают такие аргументы, например, .union(range(2)) == вернёт True . 2. В случае использования c операторами, например, A > B или A & B & C & . : B, C. являются множествами. Дело в том, что эти операторы определены для операндов типа set (и также frozenset , о которых речь позже).
| Операция | Синтаксис | Тип результата |
|---|---|---|
| Вхождение элемента | elem in A | bool |
| Равенство | A == B | bool |
| Является нестрогим подмножеством | A.issubset(B) или A | bool |
| Является строгим подмножеством | A < B | bool |
| Является нестрогим надмножеством | A.issuperset(B) или A >= B | bool |
| Явяляется строгим надмножеством | A > B | bool |
| Объединение множеств | A.union(B, C. ) | set |
| A | B | C | . | set | |
| Пересечение множеств | A.intersection(B, C. ) | set |
| A & B & C & . | set | |
| Разность множеств | A.difference(B, C. ) | set |
| A - B - C - . | set | |
| Симметрическая разность множеств | A.symmetric_difference(B, C. ) | set |
| A ^ B ^ C ^ . | set |
Кроме того, у операций, порождающих новые множества, существует 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: разбираемся с теорией и выбираем лучшую реализацию
Множество (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 , так что эта структура — именно то, что мы ищем.
Она реализована с помощью красно-чёрных деревьев. Смысл этой струкруты в том, что все элементы образуют собой двоичное дерево поиска, которое балансируется так, чтобы высота не превышала логарифм. Нам это даёт возможность с помощью одного спуска по дереву выполнить необходимые операции. Также с этой задачей может справиться Декартово дерево (Дерамида) по неявному ключу или AVL дерево.
Таким образом, целью этой статьи станет поиск аналога этой структуры в Python.
Как будем тестировать скорость работы структур данных
Для оценки времени работы я написал программу, которая будет выполнять последовательно несколько типов операций:
- Добавление в множество миллиона случайных чисел (при данном сиде среди них будет 999'936 различных)
- Проверка миллиона случайных чисел на присутствие в множестве
- Прохождение циклом по всем элементам в порядке возрастания
- В случайном порядке для каждого элемента массива узнать его индекс (а, соответственно, и количество элементов, меньше данного)
- Получение значения i-того по возрастанию элемента для миллиона случайных индексов
- Удаление всех элементов множества в случайном порядке
from SomePackage import ordered_set import random import time random.seed(12345678) numbers = ordered_set() # adding 10 ** 6 random elements - 999936 unique last_time = time.time() for _ in range(10 ** 6): numbers.add(random.randint(1, 10 ** 10)) print("Addition time:", round(time.time() - last_time, 3)) # checking is element in set for 10 ** 6 random numbers last_time = time.time() for _ in range(10 ** 6): is_element_in_set = random.randint(1, 10 ** 10) in numbers print("Checking time:", round(time.time() - last_time, 3)) # for all elements last_time = time.time() for elem in numbers: now_elem = elem print("Cycle time:", round(time.time() - last_time, 3)) # getting index for all elements last_time = time.time() requests = list(numbers) random.shuffle(requests) for elem in requests: answer = numbers.index(elem) print("Getting indexes time:", round(time.time() - last_time, 3)) # getting elements by indexes 10 ** 6 times requests = list(numbers) random.shuffle(requests) last_time = time.time() for _ in range(10 ** 6): answer = numbers[random.randint(0, len(numbers) - 1)] print("Getting elements time:", round(time.time() - last_time, 3)) # deleting all elements one by one random.shuffle(requests) last_time = time.time() for elem in requests: numbers.discard(elem) print("Deleting time:", round(time.time() - last_time, 3))SortedSet.sorted_set.SortedSet
Пакет с многообещающим названием. Используем pip install sortedset
К сожалению, автор не приготовил нам функцию add и erase в каком-либо варианте, поэтому будем использовать объединение и вычитание множеств
from SortedSet.sorted_set import SortedSet as ordered_set numbers = ordered_set() numbers |= ordered_set([random.randint(1, 10 ** 10)]) # добавление numbers -= ordered_set([elem]) # удалениеПротестируем пока на множествах размера 10'000:
| Задача | Время работы |
|---|---|
| Добавление | 16.413 |
| Проверка на наличие | 0.018 |
| Цикл по всем элементам | 0.001 |
| Получение индексов | 0.008 |
| Получение значений по индексам | 0.015 |
| Удаление | 30.548 |
Как так получилось? Давайте загляем в исходный код:
def __init__(self, items=None): self._items = sorted(set(items)) if items is not None else [] def __contains__(self, item): index = bisect_left(self._items, item)Как оказалось, это обычный массив, в котором наличие элемента определяется бинпоиском. Это действительно отсортированное множество, но очень ленивое.
Вывод: почти бесполезно, несколько строчек кода завернули в класс
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 , что мы ищем.
import bintrees numbers = bintrees.FastAVLTree() numbers.insert(value, None) # второй параметр - значение, как в словареЧто же выбрать
Мои рекомендации звучат так: если вам нужны операции find_by_order и order_of_key , то ваш единственный вариант — sortedcontainers.SortedSet . Если вам нужен только аналог std::map , то выбирайте на своё усмотрение между SortedSet и любым из fast контейнеров из bintrees , опираясь на то, каких операций ожидается больше.
Можно ли сделать что-то быстрее
Скорее нет, чем да. Использование Cython — один из самых мощных способов оптимизации, а AVL считается очень быстрым решением исходной задачи. Про остальные операции ordered_set можно сказать, что модификация красно-чёрного дерева так, чтобы оно поддерживало эти операции, вряд ли будет быстрее SortedContainers , так что смысла изобретать велосипед я не вижу.
Облачные VPS серверы от Маклауд быстрые и безопасные.
Зарегистрируйтесь по ссылке выше или кликнув на баннер и получите 10% скидку на первый месяц аренды сервера любой конфигурации!