Язык программирования Python является одним из самых простых в освоении и популярных языков программирования. Целью курса является изучение основных конструкций языка Python, которые пригодятся при решении широкого круга задач – от анализа данных до разработки новых программных продуктов. В результате освоения курса слушатели научатся обрабатывать и хранить числа, тексты и их наборы, освоят стандартную библиотеку языка Python и смогут автоматизировать задачи по сбору и обработке данных. Курс дает необходимую базу для освоения более специализированных областей применения языка Python, таких как машинное обучение, статистическая обработка данных, визуализация данных и многих других. Также слушатели познакомятся с основами различных парадигм программирования: процедурным, функциональным и объектно-ориентированным программированием. Для качественного освоения курса достаточно знания математики на уровне средней школы, опыта программирования не требуется. В курсе предлагается большое количество задач по программированию, расположенных по нарастанию сложности, что позволяет закреплять на практике изучаемый материал. К каждому занятию прилагается полный конспект, это делает изучение курса удобнее. Курс проводился в оффлайн варианте для студентов бакалавриата факультета компьютерных наук НИУ ВШЭ.
Множества и хеш-функции
Loading...
From the course by National Research University Higher School of Economics
Основы программирования на Python
467 оценки
From the lesson
Множества и словари
Модуль посвящен изучению новых структур данных – множеств и словарей, которые позволяют эффективно сопоставлять различные объекты и широко используются в самых разных задачах.
Meet the Instructors
Густокашин Михаил СергеевичПриглашенный преподаватель
Департамент больших данных и информационного поиска, Факультет компьютерных наук
[МУЗЫКА] [МУЗЫКА]
Тема нашего сегодняшнего занятия: «Множества и словари».
Множество – это такой математический объект,
где некоторые элементы могут присутствовать или не присутствовать.
То есть максимум он там может быть в одном экземпляре.
Перед тем как изучать программирование, собственно,
с использованием новшеств на Python, давайте попробуем их придумать и
сделать множество руками, с помощью тех знаний, которые у нас есть.
Начнем с очень простой задачи.
К нам приходят запросы вида: добавь число, проверь,
есть ли число в множестве и удалить число из множество.
При этом числа не превосходят 5, то есть от 0 до 4.
Как мы можем это сделать?
Сделать мы это можем очень и очень легко.
Сделаем список длиной 5,
то есть по количеству возможных значений,
которые могут содержаться в нашем множестве.
Элементы списка будут иметь индексы от 0 до 4.
Давайте я запишу.
И сам список будет состоять из переменных типа bool.
То есть логического типа.
Сначала все переменные имеют значения false.
Если там лежит true в каком-то индексе, то это означает,
что такой элемент присутствует в множестве.
Например, нам на вход подается запрос: добавь число 2 в множество.
Какие наши действия?
Просто превратить переменную с индексом 2 в true.
Я нарисую это в виде галочки.
Если нам приходит следующий запрос: проверь,
например, число 3, есть оно в множестве или нет.
Мы смотрим на значение этой переменной, оно у нас false.
И поэтому мы говорим, что такого элемента в множестве нету.
Если же мы хотим проверить 2, то мы увидим здесь true и ответим,
что такой элемент есть.
Давайте добавим еще какой-нибудь элемент, например 4.
Она у нас тоже появилась в множестве и для нее будет выполняться все то же самое.
Если мы захотим проверить, что она там есть,
то просто посмотрим на значение этой переменной.
Удаление тоже происходит очень просто.
Если мы хотим удалить некоторые элементы из множества, то мы превращаем элемент
списка с соответствующим индексом, где индекс равен этому значению, в false.
Например удаляем 4.
И при следующей проверке у нас уже 4 в нашем множестве не будет.
Это очень удобно делать, если мы знаем максимальное значение,
которое нам может быть передано в ход.
Но пусть у нас задача, что подается абсолютно любое целое число и опять
же нужно каким-то образом реализовать множество.
Что мы можем сделать?
Мы можем придумать функцию,
которая отображает элемент из большого множества, из множества всех чисел,
в какое-то маленькое множество, например, в наш список длиной 5.
Такая функция называется хеш-функцией от числа x переданного,
и она может быть, в принципе, любой.
Главное, чтобы она имела область значений в нашем случае от 0 до 4.
Часто используется функция «остаток от деления».
Очень простая и быстро вычисляемая функция.
В нашем случае k = 5.
И в результате выполнения вычисления такой
функции у нас будут получаться числа как раз от 0 до 4.
Давайте посмотрим как это позволяет нам
заполнять такой небольшой массив большими числами.
Точно так же мы создаем список,
состоящий из пяти элементов с индексами от 0 до 4.
И, допустим, теперь нам говорится: добавь в множество число 7.
Если мы добавляем число 7,
то мы считаем остаток от деления на 5, получается он равен 2.
И мы записываем уже сюда не галочку, а конкретное число.
Если, например, мы добавим число 4, то оно запишется сюда.
И проверка становится чуть сложнее.
Теперь нужно посчитать хеш-функцию, пойти в элемент с соответствующим индексом
и проверить, содержится ли там ровно то число, которое было в нашем запросе.
Так мы можем, например, поискать 2.
Пойти по индексу 2 (хеш-функция от двойки равна 2) и обнаружить там 7.
Значит 2 в нашем множестве нет.
Естественно, поскольку наше множество маленькое, а чисел очень много,
у нас иногда будет возникать коллизия.
Что это такое?
Это когда два разных элемента имеют одну и ту же хеш-функцию.
Эту проблему мы тоже можем решить.
Для этого достаточно вместо одной ячейки, то есть списка чисел,
делать список списков.
То есть теперь по индексу 2 в
нашем списке содержится не одно значение, а уже список со всеми значениями,
которые содержатся в множестве и имеют хеш-функцию 2.
Нам достаточно пробежаться по всему списку и проверить есть ли там наше число.
Таким образом, мы научились делать это для целых чисел, но,
вообще говоря, хеш-функцию можно посчитать от чего угодно.
Почему?
Потому что в компьютере все представимо в виде числе, в виде бит,
например, двоичных чисел.
Давайте простой пример.
Это, конечно, не совсем правда, что я напишу, но как можно было бы сделать.
Например, у нас есть строка из букв
a b c a b
Нам нужно каким-то образом научиться превращать ее в число.
Что мы можем сделать?
Мы можем просто для каждой буквы взять ее порядковый номер в алфавите.
1 2 3 1 2.
Все это вместе объединенное будет
числом.
Вот оно наше число, а что делать с числом – мы уже знаем.
Точно так же можно придумать какие-то хеш-функции и для других объектов.
Например, для кортежей или для вещественных чисел.
В целом они, конечно же, чаще всего рассматриваются
просто как свое битовое представление.
Еще один способ: абсолютно для любого объекта легко придумать хеш-функцию.
Наша память компьютерная, пока что на нашем уровне абстракции,
представляет собой, по сути, один огромный, длинный список из байт.
И вот в этом списке где-то, в каком-то месте вашей памяти,
живет ваш объект абсолютно любой природы.
И у него есть адрес, где он находится в памяти.
Так давайте этот адрес и обозначим за число x.
Вот так мы получили, по сути, целое число,
индекс нашей глобальной памяти.
Естественно, здесь возникает такая проблема, что если объект изменяемый,
то у нас, в принципе, все может стать очень плохо.
Объект изменится, а его хеш-функция останется той же самой.
И мы не сможем, например,
быстро сравнить два объекта или как-то поменять его значение в списке.
Таким образом, что можно сказать?
Все неизменяемые объекты в Python имеют хеш, заранее посчитанный.
И когда мы хотим его, например,
положить в множество или сравнить два объекта, то сначала сравниваются их хеши.
И только в случае совпадения будут сравниваться все сложные объекты целиком.
Изменяемые объекты хеша не имеют и поэтому в множество попасть не могут.
И еще один очень маленький пример: это словарь.
Что такое словарь, я думаю, вы представляете.
Записывается это...
Реализуется руками почти так же.
Словарь – это сопоставление ключ-значения,
например слово и его перевод, или телефон и имя абонента.
У нас есть пара key,
value – «ключ» и «значение».
Например, ключом выступает номер телефона, а значением выступает имя абонента.
Тогда мы считаем хеш-функцию только от ключа.
Например, мы хотим позвонить в пожарную службу, у нас пожар.
Лучше бы, конечно, такого не было, но если случилось, то нужно звонить.
Что мы делаем?
У пожарной службы телефон 01.
Соответственно, мы в этот список
хеш посчитаем только от ключа, от телефона 1,
а добавим сюда пару — ключ и значение.
[БЕЗ СЛОВ] Например, это у нас может быть записано так.
То есть в словаре хеш-функция считается только от ключа,
а от значения наша хеш-функция никак не считается и это
просто дополнительные данные, которые приделаны к ключу.
Таким образом, в словаре хеш-функция считается только от ключа,
а значение вообще на нее никак не влияет, это просто дополнительные данные, которые
могут быть какими угодно: изменяемыми, неизменяемыми или вообще пустыми.
Но если они пустые, то, конечно же, нужно использовать множества.
Теперь, когда мы примерно поняли как это устроенно внутри,
мы можем перейти к практическому применению словарей и множеств.
[МУЗЫКА]
[МУЗЫКА]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
