Skip to content
This repository was archived by the owner on Jul 2, 2024. It is now read-only.

Files

Latest commit

0f9e62a · Feb 27, 2023

History

History
576 lines (401 loc) · 27.5 KB

lesson6.md

File metadata and controls

576 lines (401 loc) · 27.5 KB

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

Хэш таблицы

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

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

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

Хеш (Hash)

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

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

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

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

Что важно.

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

В питоне функция 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})

Dict (Словарь)

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

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

Значением элемента словаря может быть любой тип данных, ключём элемента - любой хэшируемый (читай неизменяемый ( immutable)) тип данных, т.е. 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, если ключ был не найден, или значение по умолчанию, если вы указали его вторым параметром:

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)

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

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

calculator = {
    'plus': lambda x, y: x + y,
    'minus': lambda x, y: x - y,
    'mul': lambda x, y: x * y,
    'div': lambda x, y: x / y,
    'mod': lambda x, y: x % y
}
calculator['minus'](9, 3)
# 6

Словари до версии питона 3.7 были не упорядоченными (т.к. хэш таблица), по после 3.8 разработчики при помощи какой-то магии заставили словари быть упорядоченными, до этого если нужен был упорядоченный словарь приходилось использовать отдельный тип данных, о нём ниже.

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

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

Импорты

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

Одним из инструментов позволяющих сделать это являются ключевые слова 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)])

copy, deepcopy

Или например можно импортировать полезные функции такие как copy и deepcopy.

Как можно догадаться из названия, они копируют объекты. В чём же разница, зачем их два?

copy - скопирует только верхний уровень ключей, а остальное скопирует только ссылками

deepcopy - скопирует всё по значению

from copy import copy, deepcopy

d1 = {1: 2, 3: ['a', 'b', 'c']}

d2 = copy(d1)
# {1: 2, 3: ['a', 'b', 'c']}

d3 = deepcopy(d1)
# {1: 2, 3: ['a', 'b', 'c']}

d1[3].append('d')

d2
# {1: 2, 3: ['a', 'b', 'c', 'd']}
d3
# {1: 2, 3: ['a', 'b', 'c']}

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

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

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

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

Домашки нет, практикуемся, готовимся к модульным задачам, дальше уроки по git.