Лекция 4. Хэш таблицы. Set, frozenset. Dict. Tuple. Немного об импортах. Namedtuple, OrderedDict

Да здравствуют новые типы данных.

Tuple, он же кортеж

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

По сути, это еще одна коллекция у которой есть свои особенности.

# Создаем tuple из разнородных элементов
tuple_different_types = (1, 'abc', True)

# То же самое без скобок
tuple_different_types_another = 1, 'abc', True

# Создаем tuple из однотипных элементов
tuple_same_types = (1, 2, 3)

# Присваиваем трем переменным элементы tuple со скобками и без
(a, b, c) = tuple_different_types
print(a, b, c)
# 1 'abc' True

# То же самое без скобок
z, y, x = tuple_different_types

# Создаем tuple из одного элемента
one_element_tuple = 12,
# (12,)

# преобразование списка в кортеж
my_list = [1, 2, 3, 4]
my_tuple = tuple(my_list)
# Внимание, преобразовать в кортеж можно только то, что можно передать в for (итерируемые объекты, о них детально поговорим, очень сильно позже)

К кортежам применимы многие функции из тех, что применимы к спискам: получение длинны кортежа, конкатенация (склеивание) кортежа, срезы, методы index и count:

my_tuple = 1, 2, 3
my_tuple = my_tuple + (4, 5)
# (1, 2, 3, 4, 5)

my_tuple += 6,
# (1, 2, 3, 4, 5, 6)

# Применимы срезы

my_tuple[:-1]
# (1, 2, 3, 4, 5)

my_tuple[2:-1]
# (3, 4, 5)

len(my_tuple)
# 6

my_tuple.index(2)
# 1

my_tuple.count(3)
# 1

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

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

работа с ними быстрее(по сравнению со списками);
занимают в памяти меньше места;
могут выступать в качестве ключей для словаря (если не содержат нехешируемых значений); (О словарях чуть ниже)
имеют только два метода, count и index;
используются для массовой инициализации переменных и возврата сразу нескольких значений из функции;

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

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

a = 100
b = 200
a, b = b, a

Хэш таблицы

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

Для этого нам необходимо познакомиться с некоторыми терминами и понятиями.

Сначала нужно понять, что такое хэш.

Хеш (Hash)

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

Но мы туда не полезем :)

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

Условное A всегда превращается в B.

Из A получить B легко.

Из B получить A практически невозможно!

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

Что важно.

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

В питоне функция hash встроена, и работает без нашего участия.

Но если сильно хочется, то всегда можно позапускать её вручную

hash(1)
# 1
hash('abc')
# -1860157324224119549
hash([1, 2, 3])
# Traceback (most recent call last):
# File "<stdin>", line 1, in <module>
# TypeError: unhashable type: 'list'

Цифры до определённого размера будут преобразовываться сами в себя, но это нормально, не обращаем внимания.

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

Хэш таблицы

Зачем нам эта информация?

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

Кто такие хэш таблицы?

По сути это структуры данных которые позволяют нам реализовать связь "Ключ" - "Значение". Которые являются невероятно важными в программировании.

Как это работает под капотом?

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

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

Set (Множество)

Наконец к сути.

Первый тип данных основанный на хэш таблицах, это set, он же множество. Он является реализацией теории множеств из дискретной математики, если кто-то её когда-то учил :)

Сеты — это математическое множество - изменяемая, неотсортированная коллекция уникальных элементов.

В этом определении упомянуты три основные особенности сетов - изменяемость, уникальность и отсутствие сортировки.

Почему так?

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

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

Ну и изменяемость, в таблицу можно дописать ну или удалить из неё элементы, значит что таблица изменится.

Исходя из того что сет является по сути хеш таблицей, в него нельзя записать не хэшируемые типы данных (читай изменяемые, например список)

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

Множества поддерживают перебор всех элементов (итерацию), добавление и удаление элементов, но в силу отсутствия сортировки не поддерживают индексацию и срезы. Создание множеств:

new_set = {1, 2, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 3}

# {1, 2, 3, 4, 5, 6}

another_set = {1, 2, 3, 'a', 'c', 0.34}

# {0.34, 1, 2, 3, 'a', 'c'}

incorrect_set = {1, 2, [1, 2]}
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: unhashable type: 'list'

Множества поддерживают некоторые операции:

Симметрическая разница - оператор -. Возвращает нам множество, которое содержит элементы, которые есть в первом множестве, но нет во втором.

Объединение множеств - оператор |. Возвращает нам множество, которое содержит все элементы, которые есть в первом множестве и во втором.

Пересечение множеств - оператор &. Возвращает нам множество, которое содержит все элементы, которые есть и первом множестве, и во втором.

set1 = {1, 2, 3, 4, 5, 6}
set2 = {5, 6, 7, 8, 9}
set1 - set2  # Разность множеств
# {1, 2, 3, 4}

set1 | set2  # Объединение множеств
# {1, 2, 3, 4, 5, 6, 7, 8, 9}

set1 & set2  # Пересечение множеств
# {5, 6}

Добавить элемент в множество можно при помощи функции add, а удалить из множества элемент - при помощи функции remove. В качестве параметра выступает сам элемент, поскольку индексов в множестве нет.

set1.add(7)

# {1, 2, 3, 4, 5, 6, 7}

set1.remove(1)
# {2, 3, 4, 5, 6, 7, 8}

# При добавлении дубликата проблем не возникнет, но и эффекта не будет

set1.add(5)
# {2, 3, 4, 5, 6, 7, 8}

# При удалении несуществующего объекта выпадет ошибка

set1.remove('a')
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# KeyError: 'a'

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

list_with_duplicates = [1, 2, 3, 4, 3, 2, 5, 6, 7, 5, 3, 2]
# [1, 2, 3, 4, 3, 2, 5, 6, 7, 5, 3, 2]
list_without_duplicates = list(set(list_with_duplicates))
# [1, 2, 3, 4, 5, 6, 7]

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

programmers = {'ivanov', 'petrov', 'sidorov'}
managers = {'ivanov', 'moxov', 'goroxov'}
# И программист, и менеджер:
programmers & managers
# {'ivanov'}
# Все, и программисты, и менеджеры:
programmers | managers
# {'ivanov', 'petrov', 'sidorov', 'goroxov', 'moxov'}
# Программисты, которые не менеджеры:
programmers - managers
# {'petrov', 'sidorov'}

frozenset

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

fs = frozenset([1, 2, 3, 4, 3, 2, 1])
# frozenset({1, 2, 3, 4})

Практика

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

Dict (Словарь)

Словарь (хэш, ассоциативный массив) – изменяемая структура данных, предназначенная для хранения элементов вида ключ: значение.

Если сет был "костылём" использования хэш таблиц, то словарь, является его полной реализаций

Значением элемента словаря может быть любой тип данных, ключом элемента - любой хэшируемый (читай неизменяемый) тип данных, т.е. str, int, float, tuple (с ограничениями, об этом дальше) и пр.

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

Создание словаря

Есть несколько способов создать словарь: Прямое создание, создание при помощи преобразования в тип (используя функцию dict), использую функцию fromkeys и через генератор словарей.

Рассмотрим все эти способы на примере:

d = {}  # Создание пустого словаря напрямую, обратите внимание это не сет, это словарь, что бы создать пустой сет нужно использовать s = set()

# {}
d1 = {'a': 1, 'b': 2}  # Создание словаря напрямую

# {'a': 1, 'b': 2}

# создание словаря при помощи функции dict, она же используется для приведения типов:
d = dict(short='dict', long='dictionary')
# {'short': 'dict', 'long': 'dictionary'}

d = dict([(1, 1), (2, 4)])
# {1: 1, 2: 4}

# создание словаря при помощи функции fromkeys:
d = dict.fromkeys(['a', 'b', 1, (1, 2)])
# {'a': None, 1: None, 'b': None, (1, 2): None}

# с заполнением одним значением
d = dict.fromkeys(['a', 'b', 1, (1, 2)], 4)
# {'a': 4, 1: 4, 'b': 4, (1, 2): 4}

# создание словаря при помощи генератора словарей (dict comprehension, по аналогии со списками) :
d = {a: a ** 2 for a in range(7)}
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36}

У функции dict есть одна особенность, с ее помощью можно быстро создавать словари с ключами-строками, опуская кавычки. Это показано в примере ниже. К сожалению, работает только с явными строками, принцип формирования которых такой же, как и принцип наименования переменных:

dict(a=1, b=2, c=3, d=13)
# {'a': 1, 'c': 3, 'b': 2, 'd': 13}
dict(a=1, b=2, c=3, d=13, 1 = 2)
# File "<stdin>", line 1
# SyntaxError: keyword can't be an expression

Операции со словарями

Со словарями доступны операции взятия элемента, удаления элемента, добавления элемента и его обновления:

d = dict(a=1, b=2, c=3, d=13)
# {'a': 1, 'c': 3, 'b': 2, 'd': 13}
d['a']
# 1
d[1] = 15
# {'a': 1, 1: 15, 'c': 3, 'b': 2, 'd': 13}
del d[1]
# {'a': 1, 'c': 3, 'b': 2, 'd': 13}
d['a'] = 111
d['a']
# 111

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

По ключу - небезопасный вариант

Через get - безопасный

Это не значит, что один правильный, а второй нет, это значит, что они по разному работают

d['a']
# 1
d['e']
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# KeyError: 'e'
d.get('e')
# Ничего не отпишет, но там будет None
d.get('e', 'No such element')
# 'No such element'

Методы и функции для работы со словарями

# Добавление элементов из другого словаря
d
# {'a': 1, 'c': 3, 'b': 2, 'd': 13}
d.update({'4': 4, '5': 5})
# {'a': 1, 'c': 3, 'b': 2, '5': 5, 'd': 13, '4': 4}

# Количество пар в словаре
len(d)
# 6

d.keys()  # Получить список ключей
# ['a', 'c', 'b', '5', 'd', '4']
d.values()  # Получить список значений
# [1, 3, 2, 5, 13, 4]
d.items()  # Получить список элементов - кортежей
# dict_items([('a', 1), ('c', 3), ('b', 2), ('d', 13), ('4', 4), ('5', 5)])

Словари прекрасно проходятся в цикле:

for key in d.keys():  # Цикл for по умолчанию идет по ключам 
    print(key, d[key])
for key, val in d.items():  # проход по парам (используем кортежи)
    print(key, val)

# При переборе самого объекта, будет вызван перебор ключей.

Практика

Перевернуть словарь (было {1:2, 3:4} стало {2:1, 4:3}). После этого сделать это же через компрешеншен
Есть два списка одинаковой длинны, создать словарь, где ключи из это элементы первого списка, а значения элементы второго. Например [1,2,3], [4,5,6], результат {1:4, 2:5, 3:6}
Есть строка с предложением, в котором есть повторяющиеся слова. Создать словарь, где ключи это слова из этого предложения, а значение, это кол-во раз которое встречается это слово, пример: "привет я хочу привет я", результат {" привет": 2, "я": 2, "хочу": 1}

Enumerate

Built-in функция enumerate в Python используется для добавления счетчика к итерируемому объекту, такому как список, строка или кортеж. Она возвращает объект enumerate, который вы можете использовать для получения индекса и значения каждого элемента в итерируемом объекте.

enumerate(iterable, start=0)

Где

iterable: Итерируемый объект, который вы хотите перебирать.
start: Начальный индекс, с которого будет начинаться счетчик (по умолчанию 0).

Функция enumerate возвращает объект, который при итерации возвращает кортежи, каждый из которых содержит индекс и соответствующее значение из итерируемого объекта.

Пример:

fruits = ["apple", "banana", "cherry"]

for index, fruit in enumerate(fruits):
    print(f"Index {index}: {fruit}")

Вывод:

Index 0: apple
Index 1: banana
Index 2: cherry

Пример со сдвигом старта:

fruits = ["apple", "banana", "cherry"]

for index, fruit in enumerate(fruits, start=1):
    print(f"Index {index}: {fruit}")

Вывод:

Index 1: apple
Index 2: banana
Index 3: cherry

Импорты и некоторые специфические типы данных

Импорты

В питоне очень, нет ОЧЕНЬ много чего уже реализовано за нас, и требуется только использовать код, а не изобретать его заново.

Одним из инструментов позволяющих сделать это являются ключевые слова import и from которые позволяют нам " подключить" дополнительный функционал.

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

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

Как мы можем что-либо импортировать?

Ключевые слова import и from, если нам нужно импортировать весь модуль, мы просто пишем

import base64  # base64 это просто название одного из модулей

Если нужно импортировать только часть модуля, то мы можем указать это вот так

from parser import suite  # parser - название модуля, suite - название блока который я хочу импортировать

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

from datetime import datetime as dt

dt.now()
# datetime.datetime(2023, 2, 27, 16, 6, 32, 679427)

Что же мы можем импортировать?

namedtuple

Тип данных который работает как кортеж, но позволяет "именовать значения", например:

from collections import namedtuple

Student = namedtuple('Student', ['name', 'age', 'DOB'])
s = Student('Nandini', '19', '2541997')
s.name
# Nandini
s.age
# '19'

deque

Двухсторонняя очередь, еще один тип данных

from collections import deque

d = deque()
d.append('1')
d.appendleft('3')
d
# deque(['3', '1'])

Типов данных на самом деле очень много, но давайте пока разберёмся с основными

OrderedDict

Словарь, который гарантирует порядок ключей в любой версии питона

from collections import OrderedDict

d = OrderedDict(a=1, b=2)
# OrderedDict([('a', 1), ('b', 2)])

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

Практические задачи

Создать словарь оценок предполагаемых студентов (Ключ - ФИ студента, значение - список оценок студентов). Найти самого успешного и самого отстающего по среднему баллу.
Создать структуру данных для студентов из имен и фамилий, можно случайных. Придумать структуру данных, чтобы указывать, в какой группе учится студент (Группы Python, FrontEnd, FullStack, Java). Студент может учиться в нескольких группах. Затем вывести:

студентов, которые учатся в двух и более группах
студентов, которые не учатся на фронтенде
студентов, которые изучают Python или Java

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Лекция 4. Хэш таблицы. Set, frozenset. Dict. Tuple. Немного об импортах. Namedtuple, OrderedDict

Tuple, он же кортеж

Хэш таблицы

Хеш (Hash)

Хэш таблицы

Set (Множество)

Почему так?

frozenset

Практика

Dict (Словарь)

Создание словаря

Операции со словарями

Методы и функции для работы со словарями

Практика

Enumerate

Импорты и некоторые специфические типы данных

Импорты

namedtuple

deque

OrderedDict

Практические задачи

FilesExpand file tree

lesson4.md

Latest commit

History

lesson4.md

File metadata and controls

Лекция 4. Хэш таблицы. Set, frozenset. Dict. Tuple. Немного об импортах. Namedtuple, OrderedDict

Tuple, он же кортеж

Хэш таблицы

Хеш (Hash)

Хэш таблицы

Set (Множество)

Почему так?

frozenset

Практика

Dict (Словарь)

Создание словаря

Операции со словарями

Методы и функции для работы со словарями

Практика

Enumerate

Импорты и некоторые специфические типы данных

Импорты

namedtuple

deque

OrderedDict

Практические задачи